Detect user-installed roots more efficiently on Android.

Detect user-installed roots more efficiently on Android.

This makes assumptions about how Android stores system certificates on disk;
KeyStore's API is not sufficient to look up a trust anchor by subject and key.

BUG=361166
Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=270275

[davidben, 2014-04-08 21:54:59]

Diff is against https://codereview.chromium.org/228883003/.

It's a little unfortunate that this effectively undos what Android goes through
to avoid parsing certificates from disk each time with TrustedCertificateIndex
and such.

Perhaps we still want that in-memory HashSet now to cache this stuff? I'll see
how the performance compares.

[Ryan Sleevi, 2014-04-09 17:55:49]

I'm gonna ask Kenny to take a look at this, to see if he's happy.

[davidben, 2014-04-21 16:58:49]

On 2014/04/09 17:55:49, Ryan Sleevi wrote:
> I'm gonna ask Kenny to take a look at this, to see if he's happy.

kroot: friendly ping

[Kenny Root (Google), 2014-04-21 17:35:03]

On 2014/04/21 16:58:49, David Benjamin wrote:
> On 2014/04/09 17:55:49, Ryan Sleevi wrote:
> > I'm gonna ask Kenny to take a look at this, to see if he's happy.
> 
> kroot: friendly ping

LGTM. Makes me cry a litte, but LGTM.

[davidben, 2014-05-05 20:37:44]

On 2014/04/21 17:35:03, Kenny Root (Google) wrote:
> On 2014/04/21 16:58:49, David Benjamin wrote:
> > On 2014/04/09 17:55:49, Ryan Sleevi wrote:
> > > I'm gonna ask Kenny to take a look at this, to see if he's happy.
> > 
> > kroot: friendly ping
> 
> LGTM. Makes me cry a litte, but LGTM.

Alright, a local reference leak and lots of build system hammering on
net_perftests later, some numbers. This is verifying the current www.google.com
cert chain and quic_test.example.com.crt. Each done 200 times in a loop.

Without patch:
Cert_verify_google_chain	4174.94	ms
Cert_verify_google_chain	4095.07	ms
Cert_verify_google_chain	3909.72	ms
Cert_verify_google_chain	4229.02	ms
  Median: 20.6750 ms per iteration
Cert_verify_test_root	3507.83	ms
Cert_verify_test_root	3406.87	ms
Cert_verify_test_root	3549.31	ms
Cert_verify_test_root	3440.78	ms
  Median: 17.3715 ms per iteration

With patch:
Cert_verify_google_chain	5149.73	ms
Cert_verify_google_chain	5297.88	ms
Cert_verify_google_chain	5361.39	ms
Cert_verify_google_chain	5163.16	ms
  Median: 26.1190 ms per iteration
Cert_verify_test_root	3275.63	ms
Cert_verify_test_root	3503.71	ms
Cert_verify_test_root	3639.25	ms
Cert_verify_test_root	3537.46	ms
  Median: 17.6029 ms per iteration

With patch + in-memory cache:
Cert_verify_google_chain	4149.43	ms
Cert_verify_google_chain	4081.46	ms
Cert_verify_google_chain	3885.36	ms
Cert_verify_google_chain	4210.84	ms
  Median: 20.5772 ms per iteration
Cert_verify_test_root	3566.89	ms
Cert_verify_test_root	3538.9	ms
Cert_verify_test_root	3720.92	ms
Cert_verify_test_root	3389.5	ms
  Median: 17.7645 ms per iteration

Caveats: this runs them in a loop in a single process, so it doesn't do a good
job of capturing initialization costs and there's a fair number of in-memory
caches involved here. I also realized afterwards that the test runner is
probably running the second test right after the first, so the second set of
numbers don't account for the global initialization cost at all.

It looks like the overhead for a non-system root isn't very significant. The
overhead for a system root is somewhat more; a bit under 6ms per verification.
I'm guessing this comes from parsing the certificate; at 200 iterations, it's
probably not actually going to disk most of the time. Adding an in-memory cache
mitigates this overhead.

So the question is whether this overhead is acceptable or if we should add the
in-memory cache. That means we pay for the overhead once per root per startup. I
don't think we can avoid paying the cost the first time we see each root;
TrustedCertificateIndex isn't on the path for any of the KeyStore methods, as
far as I can tell, so we can't get at the existing in-memory cache to avoid
re-parsing.

The other question is whether I should try to land the net_perftests stuff. It
would require we keep newgooglechain.pem up-to-date. It's actually expired right
now. But I don't know how to hook that up to the rest of perf infrastructure or
if net_perftests is even hooked up.

[davidben, 2014-05-05 20:45:19]

On 2014/05/05 20:37:44, David Benjamin wrote:
> I also realized afterwards that the test runner is
> probably running the second test right after the first, so the second set of
> numbers don't account for the global initialization cost at all.

This doesn't appear to be source of the 3ms difference between the two tests.
Perhaps some difference between the signature algorithms in the chains
themselves or the KeyStores used to store their respective roots. I only did two
runs of just the second test, but the without patch median then is 17.5884 ms
per iteration.

[Ryan Sleevi, 2014-05-06 22:28:03]

net_perftests isn't hooked up anywhere.

This LGTM (with in-memory cache). If this gets fixed upstream, presumably we can
disable the in-memory cache for that release and later, right?

https://codereview.chromium.org/228293012/diff/70001/net/android/java/src/org...
File net/android/java/src/org/chromium/net/X509Util.java (right):

https://codereview.chromium.org/228293012/diff/70001/net/android/java/src/org...
net/android/java/src/org/chromium/net/X509Util.java:152: * trust anchor is a
system trust anchor or user-installed. The KeyStore API along is not
typo: alone

https://codereview.chromium.org/228293012/diff/70001/net/android/java/src/org...
net/android/java/src/org/chromium/net/X509Util.java:322: // Android hashes a
principal as the first four bytes of its MD5 digest, encoded in
List the specific versions. Should we fail in some way (compile, raise an error)
if a new Android version is encountered and this isn't verified?

https://codereview.chromium.org/228293012/diff/70001/net/android/java/src/org...
net/android/java/src/org/chromium/net/X509Util.java:338: // find an anchor name.
List bug and if it's been fixed upstream.

https://codereview.chromium.org/228293012/diff/70001/net/android/java/src/org...
net/android/java/src/org/chromium/net/X509Util.java:355: break;
Just to confirm, Android doesn't allow gaps here, does it?

Some tools that use OpenSSL's directory trust store look for hash.* on disk, and
then iterate through those. Other tools ensure that there's never a gap (eg:
like c_rehash).

OpenSSL doesn't allow gaps (see
https://github.com/openssl/openssl/blob/master/crypto/x509/by_dir.c#L398 ), I
just wanted to make sure that behaviour was preserved.

[Yaron, 2014-05-07 02:07:03]

lgtm

[davidben, 2014-05-07 16:47:58]

> This LGTM (with in-memory cache). If this gets fixed upstream, presumably we
can
> disable the in-memory cache for that release and later, right?

Not really. :-/ KeyStore.getCertificateAlias (implemented with
TrustedCertificateStore) will work once upstream changes trickle down (linked to
AOSP CL in comments), but that just lets us avoid the hashing and loop in
isKnownRoot ourselves. KeyStore.getCertificateAlias is still going to have to
decode all the certificates unless the in-memory cache moves to that layer.
Right now Android's own in-memory cache, TrustedCertificateIndex, is in
TrustManagerImpl (implementation of X509TrustManager), so checkServerTrusted
gets to pass through it, but not anything we do on top of that.

> net_perftests isn't hooked up anywhere.

Alright. Well, I'll try to land the stuff that makes it at least run on Android
without actually making anything it run it yet, so we can repeat these tests
later if needbe. It'll be something.

https://codereview.chromium.org/228293012/diff/70001/net/android/java/src/org...
File net/android/java/src/org/chromium/net/X509Util.java (right):

https://codereview.chromium.org/228293012/diff/70001/net/android/java/src/org...
net/android/java/src/org/chromium/net/X509Util.java:152: * trust anchor is a
system trust anchor or user-installed. The KeyStore API along is not
On 2014/05/06 22:28:04, Ryan Sleevi wrote:
> typo: alone

Done.

https://codereview.chromium.org/228293012/diff/70001/net/android/java/src/org...
net/android/java/src/org/chromium/net/X509Util.java:322: // Android hashes a
principal as the first four bytes of its MD5 digest, encoded in
On 2014/05/06 22:28:04, Ryan Sleevi wrote:
> List the specific versions. Should we fail in some way (compile, raise an
error)
> if a new Android version is encountered and this isn't verified?

We'll end up reporting false for everything, which is the conservative option.
CertVerifyProcTest.TestKnownRoot will break, so we should be able to find out.

Added list of versions.

https://codereview.chromium.org/228293012/diff/70001/net/android/java/src/org...
net/android/java/src/org/chromium/net/X509Util.java:338: // find an anchor name.
On 2014/05/06 22:28:04, Ryan Sleevi wrote:
> List bug and if it's been fixed upstream.

Linked to https://android-review.googlesource.com/#/c/91605/

https://codereview.chromium.org/228293012/diff/70001/net/android/java/src/org...
net/android/java/src/org/chromium/net/X509Util.java:355: break;
On 2014/05/06 22:28:04, Ryan Sleevi wrote:
> Just to confirm, Android doesn't allow gaps here, does it?
> 
> Some tools that use OpenSSL's directory trust store look for hash.* on disk,
and
> then iterate through those. Other tools ensure that there's never a gap (eg:
> like c_rehash).
> 
> OpenSSL doesn't allow gaps (see
> https://github.com/openssl/openssl/blob/master/crypto/x509/by_dir.c#L398 ), I
> just wanted to make sure that behaviour was preserved.

Correct. If it needs a gap, it puts in an empty tombstone file for the user
directory and puts a separate "deleted" marker elsewhere for the system
directory.

[davidben, 2014-05-13 21:59:12]

The CQ bit was checked by davidben@chromium.org

[commit-bot: I haz the power, 2014-05-13 22:04:56]

CQ is trying da patch. Follow status at
 https://chromium-status.appspot.com/cq/davidben@chromium.org/228293012/90001

[commit-bot: I haz the power, 2014-05-14 00:51:15]

Change committed as 270275