random bits of randomness

[Peter Kurrasch]

Changing the subject of this thread, too....

On Tue, Apr 17, 2012 at 3:55 AM, ianG <ia...@iang.org> wrote:

> On 17/04/12 08:54 AM, Peter Kurrasch wrote:
>
>> I don't have much of a problem with added randomness--one may think of it
>> as extra fat that makes the whole system work better. However, since I'm
>> not most familiar with the mechanics of signing/issuing certs (more
>> experienced with the receiving end of certificate clutter) I feel like I'm
>> still missing something.
>>
>
> All [0] digital signatures are first done by hashing the message
> (certificate body) with a message digest like MD5, SHA1 and increasingly
> SHA2.
>
> Then, the public key signature is done by RSA (or variants) over the hash.
> So each digsig is a two-phase operation.
>
> More importantly, for this discussion, the signature can be attacked at
> two points - the hash *or* the RSA operation. Double trouble! Either one
> can cause chaos if weak.
>

For the RSA phase--got it. For the hashing phase, though, I'm still
confused. My understanding is you hash the entire certificate--main body
and extensions. If so, then placing the random bits in an extension would
be equally effective as putting them in the main body. If not (i.e. if
only the main body is hashed) then, well, it's obvious.

Thanks.

[ianG]

On 18/04/12 07:21 AM, Peter Kurrasch wrote:
> ... My understanding is you hash the entire certificate--main body

> and extensions. If so, then placing the random bits in an extension would
> be equally effective as putting them in the main body. If not (i.e. if
> only the main body is hashed) then, well, it's obvious.

Your understanding is the same as mine. I'm not sure why they want the
randomness in the main body not the extensions.

Anyone?

iang

[Kyle Hamilton]

On Tue, Apr 17, 2012 at 2:21 PM, Peter Kurrasch <fhw...@gmail.com> wrote:
> Changing the subject of this thread, too....

> For the RSA phase--got it.  For the hashing phase, though, I'm still

> confused.  My understanding is you hash the entire certificate--main body

> and extensions.  If so, then placing the random bits in an extension would
> be equally effective as putting them in the main body.  If not (i.e. if
> only the main body is hashed) then, well, it's obvious.

The signature in a certificate is calculated over the TBSCertificate member of the Certificate sequence. TBSCertficate is a sequence that begins with the version number and ends with the final certificate extension. Then, the signature algorithm OID (which must match the signature algorithm member) is the second member of the Certificate sequence, and finally the actual signature.

Signature algorithms are either 2-phase (e.g. digest + RSA) or 1-phase (DSA). This is why you've got only a single algorithm OID to describe both aspects.

-Kyle H

[ianG]

On 20/04/12 13:30 PM, Kyle Hamilton wrote:

>
>
> On Thu, Apr 19, 2012 at 7:54 PM, ianG <ia...@iang.org> wrote:
>>
>> Your understanding is the same as mine. I'm not sure why they want the
>> randomness in the main body not the extensions.
>>
>> Anyone?
>

> Digest length extension attacks. (i.e., you have the original V1/V2
> certificate fields, and then you can add anything you want to it to
> cause a digest collision.)

Doh! You mean ... x.509 does not identify its full packet?

So the whole security only works because the hash was providing the full
protection - for the entire packet :D Unbelievable!


> This can be addressed by using simultaneous
> SHA2-256/128. Honestly, this could as easily be
> MD2+MD4+MD5+SHA1+SHA2/128+SHA2/192+SHA2/256+SHA2/384+SHA2/512. There is
> no perfect security against digest collisions because of their
> fixed-length compression nature.


OK, I've heard this before, and I don't understand it. Now is as good a
chance to ask as any other.

People say that SHA2 is not vulnerable to length extension.

Is this because it is theoretically as vulnerable as any other hash, but
it is so long that it can't be crunched in the way that MD5 can/was?

Or is there some fundamental reason why SHA2 is not vulnerable?

(Ah, I think the light is glimmering. There is a cascade or avalanche
argument somewhere here...)

And, your description of simultaneous hashes - does this amount to
making a new hash algorithm like N(x) = md5(x) || sha256. E.g., invent
a bigger hash and hope it works where a smaller hash didn't?



iang

[Erwann Abalea]

Putting random data at the end does not protect you from a collision attack performed at the start of the data.

If you're clever enough to be able to build 2 different TBS hashing to the same digest, then random data added to the first TBS can be copied to the second one
and the digests will still be equal (altough different than what they were at first).

[Peter Kurrasch]

Maybe I'm still missing something because this doesn't make sense to me.

Since the hash is over the entire TBS how does placement of the random bits
within the TBS make them any less effective? It should be equally hard to
find the hash collision with the bits at the beginning, middle, or end.

I would add that the insertion of random bits is only intended to make it
harder to find the collision--it won't prevent collisions.

But like I said, I could be missing something.

[Erwann Abalea]

Le vendredi 20 avril 2012 19:14:08 UTC+2, Peter Kurrasch a écrit :
> Maybe I'm still missing something because this doesn't make sense to me.
>
> Since the hash is over the entire TBS how does placement of the random bits
> within the TBS make them any less effective? It should be equally hard to
> find the hash collision with the bits at the beginning, middle, or end.
>
> I would add that the insertion of random bits is only intended to make it
> harder to find the collision--it won't prevent collisions.

Consider an attacker able to build 2 TBS colliding under SHA1, name them TBS1 and TBS2. Thus, SHA1(TBS1) = SHA1(TBS2).

The request that'll give TBS1 is submitted, the certificate received, the signature block can be taken and used with TBS2 to have a valid certificate unknown to the CA.
The certificates are composed like this:
constantheader || TBS{1,2} || signature
"signature" is the signature of SHA1(TBS1), so it also applies to TBS2.

If the CA appends random data to TBS1 before signing it (an extension), then the certificate is basically like this:
constantheader || (TBS1 || random) || signature
"signature" is the signature of SHA1(TBS1||random).
Just take "random" and "signature", build
constantheader || (TBS2 || random) || signature
and it still works, because SHA1(TBS1)=SHA1(TBS2) implies SHA1(TBS1||x)=SHA1(TBS2||x) whatever x is.

What *could* work is having this extension placed not at the very last place, but still before any user-controlled extension, but I'm not sure.

[Erwann Abalea]

It seems my reply has been lost a few hours ago... I'm rewriting it, sorry if it gets duplicated.

Le vendredi 20 avril 2012 05:50:07 UTC+2, ianG a écrit :
> On 20/04/12 13:30 PM, Kyle Hamilton wrote:
> >
> > On Thu, Apr 19, 2012 at 7:54 PM, ianG <ia...@iang.org> wrote:
> >>
> >> Your understanding is the same as mine. I'm not sure why they want the
> >> randomness in the main body not the extensions.
> >>
> >> Anyone?
> >
> > Digest length extension attacks. (i.e., you have the original V1/V2
> > certificate fields, and then you can add anything you want to it to
> > cause a digest collision.)
>
> Doh! You mean ... x.509 does not identify its full packet?
>
> So the whole security only works because the hash was providing the full
> protection - for the entire packet :D Unbelievable!

Signature relies on collision resistant hash functions. That's not specific to X.509. If you have collisions, then you can't have secure signatures. That's it.
MD5 is not collision resistant, SHA1 won't be soon. Adding random data before user-controlled data is a way to raise the necessary computing to forge collisions.
So switch to SHA2 if possible, then SHA3 (even if SHA2 is still resistant).

> > This can be addressed by using simultaneous
> > SHA2-256/128. Honestly, this could as easily be
> > MD2+MD4+MD5+SHA1+SHA2/128+SHA2/192+SHA2/256+SHA2/384+SHA2/512. There is
> > no perfect security against digest collisions because of their
> > fixed-length compression nature.
>
> OK, I've heard this before, and I don't understand it. Now is as good a
> chance to ask as any other.
>
> People say that SHA2 is not vulnerable to length extension.
>
> Is this because it is theoretically as vulnerable as any other hash, but
> it is so long that it can't be crunched in the way that MD5 can/was?
>
> Or is there some fundamental reason why SHA2 is not vulnerable?

SHA2 is not vulnerable to length extension because it's not a pure Merkle-Damgard design (like MD5 and SHA1), but a wide-pipe design. The internal state is larger than the output (twice the size, in fact).

> And, your description of simultaneous hashes - does this amount to
> making a new hash algorithm like N(x) = md5(x) || sha256. E.g., invent
> a bigger hash and hope it works where a smaller hash didn't?

That's already used in SSL/TLSv1/TLSv1.1. Signatures are done on the 36 bytes concatenation of a MD5 and a SHA1 (same construction is used for the PRF).
TLSv1.2 uses SHA256 for signature, and as the PRF for some ciphersuites.

[Erwann Abalea]

Le vendredi 20 avril 2012 19:42:19 UTC+2, Erwann Abalea a écrit :
[...]

> and it still works, because SHA1(TBS1)=SHA1(TBS2) implies SHA1(TBS1||x)=SHA1(TBS2||x) whatever x is.
>
> What *could* work is having this extension placed not at the very last place, but still before any user-controlled extension, but I'm not sure.

Of course not. Silly me. That's written just above. "whatever x is".

[Erwann Abalea]

Le vendredi 20 avril 2012 05:50:07 UTC+2, ianG a écrit :

> On 20/04/12 13:30 PM, Kyle Hamilton wrote:
> >
> >
> > On Thu, Apr 19, 2012 at 7:54 PM, ianG <ia...@iang.org> wrote:
> >>
> >> Your understanding is the same as mine. I'm not sure why they want the
> >> randomness in the main body not the extensions.
> >>
> >> Anyone?
> >
> > Digest length extension attacks. (i.e., you have the original V1/V2
> > certificate fields, and then you can add anything you want to it to
> > cause a digest collision.)
>
> Doh! You mean ... x.509 does not identify its full packet?
>
> So the whole security only works because the hash was providing the full
> protection - for the entire packet :D Unbelievable!

The security of a signature relies on:
- collision resistance of the hash function used
- resistance of the private key crypto operation

MD5 isn't collision resistant, SHA1 is showing flaws (last paper I saw talked about collisions found on reduced-SHA1 versions -75 rounds instead of 80-). That's why SHA2 should be used when available, that's why the SHA3 competition has a sense (to have better hash designs, largely studied candidates).

Adding randomness *before* user-controlled data levels-up the computing complexity of collision forgery. Adding randomness *after* user-controlled data doesn't protect you, the harm is already done.

This isn't limited to X.509.

> > This can be addressed by using simultaneous
> > SHA2-256/128. Honestly, this could as easily be
> > MD2+MD4+MD5+SHA1+SHA2/128+SHA2/192+SHA2/256+SHA2/384+SHA2/512. There is
> > no perfect security against digest collisions because of their
> > fixed-length compression nature.
>
>
> OK, I've heard this before, and I don't understand it. Now is as good a
> chance to ask as any other.
>
> People say that SHA2 is not vulnerable to length extension.

Because it uses a wider internal state (wide-pipe instead of pure Merkle-Damgard).
On a standard Merkle-Damgard hash function (like MD5 and SHA1), the output of the function is equal to the last internal state. The last hashed block is padded with its length. Therefore, knowing only the hash H(m) of a message, without knowing m, you can easily calculate H(pad(m) || y) (pad() is the padding function used in H on the last block of the message).
SHA2 is a wide-pipe design, knowing H(m) doesn't allow you to calculate H(pad(m) || y), because H(m) isn't the last internal state of H.

[...]

> And, your description of simultaneous hashes - does this amount to
> making a new hash algorithm like N(x) = md5(x) || sha256. E.g., invent
> a bigger hash and hope it works where a smaller hash didn't?

That's how it's done with SSL/TLSv1/TLSv1.1. The PRF function, like the hash-for-signature function, is a combination of MD5+SHA1. This was changed to SHA256 in TLSv1.2.

[Kyle Hamilton]

On Thu, Apr 19, 2012 at 8:50 PM, ianG <ia...@iang.org> wrote:
> Doh!  You mean ... x.509 does not identify its full packet?

X.509 identifies its packet in the form of 'the DER sequence which makes up TBSCertificate'. It is rather impossible to calculate a digest over a second, precomputed digest and expect to be able to compare them.

It would theoretically be possible to create an extension which contained digests of the X.509v1 encoding of the non-extended certificate. This would be wonderful to see, but I don't think PSM or NSS would make this straightforward to implement. (Much less OpenSSL or BouncyCastle.)

>> This can be addressed by using simultaneous
>> SHA2-256/128. Honestly, this could as easily be
>> MD2+MD4+MD5+SHA1+SHA2/128+SHA2/192+SHA2/256+SHA2/384+SHA2/512. There is
>> no perfect security against digest collisions because of their
>> fixed-length compression nature.
>
> OK, I've heard this before, and I don't understand it.  Now is as good a
> chance to ask as any other.
>
> People say that SHA2 is not vulnerable to length extension.

I am told that SHA2 is vulnerable to length extension unless you calculate two separate digest states with different lengths. SHA2/512+256 would have the same protection against length extension as SHA2/256+128 under this theory.

I believe that length extension vulnerability is inherent to the fundamental concept of the digest. For any given fixed-length H, there are an infinite number of possible collisions. The potential utility of those collisions depends on the message format being used. (This is why X.509 used DER. There's supposedly only one encoding that works for any given datum. Of course, this doesn't call into account the idea that subjectPublicKeyInfo can be encoded multiple ways, particularly with ECC. Nice work, Certicom.)

> (Ah, I think the light is glimmering.  There is a cascade or avalanche
> argument somewhere here...)

I think it's more that the two systems are going to come up with wildly divergent values. This means that crunching multiple instances is automatically going to increase the amount of work necessary, such that if you find a collision on SHA2/128 that doesn't match the SHA2/256, you must find another collision on SHA2/128 before testing its potential collision on SHA2/256, and so on.

This is why I'm not okay with any single digest algorithm, and why my X.509 extension suite allows for any number of them to ensure that the data is indeed what was committed.

> And, your description of simultaneous hashes - does this amount to making a
> new hash algorithm like N(x) = md5(x) || sha256.  E.g., invent a bigger hash
> and hope it works where a smaller hash didn't?

On the crypto...@randombit.org list, a recent mail suggests that SHA2/256+128 is "provably secure against length extension attacks". I'm not entirely certain that this is true, but I conjecture that the combination provides approximately 360 to 370 bits of security. (I don't know that it's fully 256+128=384 bits, as there may be attacks against the same first few rounds.)

Theoretically, the upper bound on the amount of security with multiple digests cannot be more than the sum of the bits of security provided by each digest. MD5 is approximately 20 bits (calculable in near-real-time), SHA1 is approximately 70 bits (not yet calculable in real time). The sum is approximately 90 bits of security. As these are not the same digest family, I hypothesize that the attacks possible against one will not likely lead to a computation which would be useful in the other. (Please show me wrong, this is truly a hypothesis.)

The problem I have with { H = md5(x) ^ sha256(x) } (that's XOR, btw, not OR) is that all digests in the xor must be calculated. Even if someone believes that MD5 is an extinct algorithm, the algorithm must still be implemented and calculated in order to verify the XOR'ed result against the provided value to provide security. (This is already a problem in e.g. TLS/1.0 FIPS applications, and I perceive other potential problems with international policy requirements.)

I would like to see a counted digest at some point, one which integrates a rolling byte counter mod some 64-bit long prime into the digested data. I do not know if this would be helpful.

And finally, there are also the candidates for SHA3, which I have not yet examined.

I hope this helps. Next week I'm off email, hope to finish up the proof of concept on my extensions.

-Kyle H

[Peter Kurrasch]

Thanks for the description, Erwann. The scenario you describe is one I was
hoping someone could talk about since it differs from the scenario I
already understand--that where the attacker is attempting to compromise a
cert which has already been issued to someone else.

It seems the purpose served by the randomness here is to protect a
certificate signer/issuer from a "bad actor". I'm not sure I understand
why one would attempt this sort of attack. Perhaps an intermediate cert
authority might stand to gain financially in some way? I don't think an
end point cert (machine or user) would benefit from this type of attack,
would it?


In any case, you raise an interesting issue: A certificate signer/issuer
might not have full knowledge of all contents of a certificate that will be
deployed into the wild. The idea that some extensions will be added later
on is something I don't think most people realize or understand (I sure
didn't). Not sure how I feel about it.


Regarding your comment about "what could work" I didn't quite follow that
nor your update later, but I think what you describe will not work because
of ASN.1/DER encoding. In the byte stream you'd have to have the number of
bytes for all extensions appear before the first extension. And naturally,
that byte count would be part of the hash SHA1(TBS1). So, if the idea was
to have the cert owner add extensions later on it would be a problem if
that byte count needed updating, too.


Thanks.

On Fri, Apr 20, 2012 at 12:42 PM, Erwann Abalea <eab...@gmail.com> wrote:

> Le vendredi 20 avril 2012 19:14:08 UTC+2, Peter Kurrasch a écrit :

> > Maybe I'm still missing something because this doesn't make sense to me.
> >
> > Since the hash is over the entire TBS how does placement of the random
> bits
> > within the TBS make them any less effective? It should be equally hard
> to
> > find the hash collision with the bits at the beginning, middle, or end.
> >
> > I would add that the insertion of random bits is only intended to make it
> > harder to find the collision--it won't prevent collisions.
>

> Consider an attacker able to build 2 TBS colliding under SHA1, name them
> TBS1 and TBS2. Thus, SHA1(TBS1) = SHA1(TBS2).
>
> The request that'll give TBS1 is submitted, the certificate received, the
> signature block can be taken and used with TBS2 to have a valid certificate
> unknown to the CA.
> The certificates are composed like this:
> constantheader || TBS{1,2} || signature
> "signature" is the signature of SHA1(TBS1), so it also applies to TBS2.
>
> If the CA appends random data to TBS1 before signing it (an extension),
> then the certificate is basically like this:
> constantheader || (TBS1 || random) || signature
> "signature" is the signature of SHA1(TBS1||random).
> Just take "random" and "signature", build
> constantheader || (TBS2 || random) || signature

[Kyle Hamilton]

On Fri, Apr 20, 2012 at 10:14 AM, Peter Kurrasch <fhw...@gmail.com> wrote:
> Maybe I'm still missing something because this doesn't make sense to me.
>
> Since the hash is over the entire TBS how does placement of the random bits
> within the TBS make them any less effective?  It should be equally hard to
> find the hash collision with the bits at the beginning, middle, or end.

Because the user can truncate all of the extensions and have a v3 certificate with no extensions. The randomness makes it difficult to preselect a key to collide upon, but only if it's prior to the first legitimate place for the structure to end.

-Kyle H

[Erwann Abalea]

Le vendredi 20 avril 2012 23:56:03 UTC+2, Kyle Hamilton a écrit :
> On Thu, Apr 19, 2012 at 8:50 PM, ianG <ia...@iang.org> wrote:
> > Doh!  You mean ... x.509 does not identify its full packet?
>
> X.509 identifies its packet in the form of 'the DER sequence which makes up TBSCertificate'. It is rather impossible to calculate a digest over a second, precomputed digest and expect to be able to compare them.
>
> It would theoretically be possible to create an extension which contained digests of the X.509v1 encoding of the non-extended certificate. This would be wonderful to see, but I don't think PSM or NSS would make this straightforward to implement. (Much less OpenSSL or BouncyCastle.)

The attacker can hide this extension, by making it enclosed in another one.

[Erwann Abalea]

Le samedi 21 avril 2012 02:12:51 UTC+2, Peter Kurrasch a écrit :
> It seems the purpose served by the randomness here is to protect a
> certificate signer/issuer from a "bad actor". I'm not sure I understand
> why one would attempt this sort of attack. Perhaps an intermediate cert
> authority might stand to gain financially in some way? I don't think an
> end point cert (machine or user) would benefit from this type of attack,
> would it?

The attack described has already been performed, in 2008. TBS1 (the certificate that was requested and obtained) was a perfectly standard SSL server certificate. TBS2 (the certificate that was built so that TBS1's signature could apply to TBS2) was a CA certificate, but it could be any kind of certificate (OCSP, code signing, whatever).

Read http://www.win.tue.nl/hashclash/rogue-ca/, it's instructive. The use of an "englobing extension", in this case the netscapeComment, to hide any unwanted extension such as the proposed random data extension, is cool. Please note that the attacker is not constrained by properly-formed DER objects when forging collisions. Only the final result (the certificate) needs to be a valid object.

> In any case, you raise an interesting issue: A certificate signer/issuer
> might not have full knowledge of all contents of a certificate that will be
> deployed into the wild. The idea that some extensions will be added later
> on is something I don't think most people realize or understand (I sure
> didn't). Not sure how I feel about it.

This is possible if and only if the hash function is not collision resistant.

> Regarding your comment about "what could work" I didn't quite follow that
> nor your update later, but I think what you describe will not work because
> of ASN.1/DER encoding. In the byte stream you'd have to have the number of
> bytes for all extensions appear before the first extension. And naturally,
> that byte count would be part of the hash SHA1(TBS1). So, if the idea was
> to have the cert owner add extensions later on it would be a problem if
> that byte count needed updating, too.

In fact, wherever you put your random extension, it doesn't matter, you're not protected. The colliding data can be built before this extension appears (with the augmented Sequence size).

[Peter Kurrasch]

I think I'm starting to get the picture. As Erwann and George have kindly
explained, the point of the randomness is not to prevent a hash collision
per se. Rather, the point is to frustrate efforts on the part of an
attacker to find a collision that works. I hope that's a fair and accurate
statement...?

I also understand how trying to use an extension is a non-starter, so I'll
drop that line of discussion. However, that doesn't mean I'm totally happy
with the overloading of the serial number field. Specifically, I'm not
happy with saying simply to "add randomness to the serial number" because
that can frustrate optimization and validation efforts on the client side.

Allow me to explain:

1) When I (as the client software) receive a cert that I've seen before
(i.e. the entire cert is an identical match, by comparing thumbprints or
whatever) I know I can use whatever trust decisions I've made before. I
don't have to go through all the steps to re-validate the chain, the
contents, etc. (and let's ignore revocation stuff just for the purposes of
my example). The point I'm making is that there is a not-insignificant
speed-up that's possible.

2) When I receive a cert that doesn't match, I would like to check the
serial number to see if it's "newer" than the one I have. In such cases, I
know I need to do a full evaluation of the cert, it's contents, and the
authority chain. I'm concerned in this case that the cert I was using may
have been revoked. I'm concerned that the newer cert may or may not be a
fraud. For that matter, I'm concerned that the cert I was using was
fraudulent. But if everything checks out, I want to add the new cert to my
local cache but also keep the old one around so I know whether to trust it
the next time I encounter it.

3) When the cert doesn't match, I also would like to check the serial
number to see if it's an *older* version of a certificate. Perhaps I've
seen it before, which means there's a chance I could re-use the trust
decisions I made at the time. I'm also concerned that the older cert may
have been revoked but the server admin hasn't updated the site yet. And,
just like the "new cert" case, perhaps the cert I was using is in fact
fraudulent--I'd like to check that too. Bottom line is that there's a
chance for optimization if the old cert is in my local cache--and if it
isn't I want to add it for the next time I encounter it.


I hope the example is clear enough, but really it comes down to this: being
able to distinguish "newer" and "older" certs is useful--perhaps even
important.

I have thoughts on how we could accomplish both goals--frustrate attackers
and provide newer/older information--but I'll hold off getting into that
since this email is already in TL;DR territory. :-)

Thanks to all for the perspective thus far!

[ianG]

On 26/04/12 03:31 AM, Peter Kurrasch wrote:
> I think I'm starting to get the picture. As Erwann and George have kindly
> explained, the point of the randomness is not to prevent a hash collision
> per se. Rather, the point is to frustrate efforts on the part of an
> attacker to find a collision that works. I hope that's a fair and accurate
> statement...?

Well, the randomness is dealing with a particular attack by increasing
the difficulty.

Also, there is some confusion about the notion of "collision" which is
rather boring and benign and "pre-image" attack which is ... actually
dangerous. We have a real cert to hand - an image - so we are not
dealing with some random pair of collisions, but a pre-image attack.

> I also understand how trying to use an extension is a non-starter, so I'll
> drop that line of discussion. However, that doesn't mean I'm totally happy
> with the overloading of the serial number field. Specifically, I'm not
> happy with saying simply to "add randomness to the serial number" because
> that can frustrate optimization and validation efforts on the client side.

Have a close look at the pictures 3.4-5 in
http://www.win.tue.nl/hashclash/rogue-ca/ .

The issue here is that really, under the hood of SHA1 and MD5, the
algorithm is like a block mode. Now, there are some pathologies here.
Firstly, we only need to break perfectly one of those boxes to get
control of the entire hash. Or, we can break one box and then repair
the damage in the next. Conceptually.

Now factor in the structure of x.509. It has these characteristics:
changeable, replaceable junk at the end (addable extensions of little
value), while there is fixed and predictable value at the front. This
happens to align with the above - we hold everything up front constant
and then replace the end with what we want.

So the strategy is to place unpredictable, unreplaceable junk at the
front. Which seriously cramps the attack.

Now look at the graphic in 5.3. You'll see that in terms of
changeability before the fixed value fields, the serial number is it.

> Allow me to explain:
>
> 1) When I (as the client software) receive a cert that I've seen before
> (i.e. the entire cert is an identical match, by comparing thumbprints or
> whatever) I know I can use whatever trust decisions I've made before. I
> don't have to go through all the steps to re-validate the chain, the
> contents, etc. (and let's ignore revocation stuff just for the purposes of
> my example). The point I'm making is that there is a not-insignificant
> speed-up that's possible.

Yes, but your assumptions. You assume you can detect equivalency. But
there is no such claim made by the cert, so you are reduced to
hueristics of your own design. This introduces certain errors which
others are at liberty to use against you. Also, not to mention that you
used the word "trust" and that hasn't got a definition. So one trust
might be another, or it might not.

> 2) When I receive a cert that doesn't match, I would like to check the
> serial number to see if it's "newer" than the one I have. In such cases, I
> know I need to do a full evaluation of the cert, it's contents, and the
> authority chain. I'm concerned in this case that the cert I was using may
> have been revoked. I'm concerned that the newer cert may or may not be a
> fraud. For that matter, I'm concerned that the cert I was using was
> fraudulent. But if everything checks out, I want to add the new cert to my
> local cache but also keep the old one around so I know whether to trust it
> the next time I encounter it.

Yes, this is to assume that "serial" means serial, and/or that higher
numbers means "newer". This meaning or implication has been explicitly
withdrawn, enough already such that you can no longer rely upon it (CAs
have been doing this for some time...)

You should probably check the issue / expiry date information if you
want to form a view on "newer". But even then it isn't really reliable.
What you're after here is a "replaces" meaning in the sense that is
seen in protocols like DNS. But this sort of feature only makes sense
when newer information is better than older information. In the secure
browsing implementation of PKI, it never is, it's the same information -
the name, the reliance, the whatever.

Look again at why you're working on a concept of "newer". E.g., above
you say you are worried about revocation. Well, just check that resource :)

> 3) When the cert doesn't match, I also would like to check the serial
> number to see if it's an *older* version of a certificate. Perhaps I've
> seen it before, which means there's a chance I could re-use the trust
> decisions I made at the time. I'm also concerned that the older cert may
> have been revoked but the server admin hasn't updated the site yet. And,
> just like the "new cert" case, perhaps the cert I was using is in fact
> fraudulent--I'd like to check that too. Bottom line is that there's a
> chance for optimization if the old cert is in my local cache--and if it
> isn't I want to add it for the next time I encounter it.

There is such a thing as over-optimisation :) Perhaps you should just
take the hit. When someone starts dealing with a different cert,
perhaps this is a good time to re-check everything about that customer,
not try and squeeze the last few cycles out.

> I hope the example is clear enough, but really it comes down to this: being
> able to distinguish "newer" and "older" certs is useful--perhaps even
> important.
>
> I have thoughts on how we could accomplish both goals--frustrate attackers
> and provide newer/older information--but I'll hold off getting into that
> since this email is already in TL;DR territory. :-)

Remember, the claim rarely changes. You're not in possession of older
or newer information, but older or newer statements of the same information.

> Thanks to all for the perspective thus far!

It's been a bit of a trip. I've still not quite wrapped my head around
that Merkle-Damgård thing.


iang

[Erwann Abalea]

Le samedi 28 avril 2012 02:46:01 UTC+2, ianG a écrit :
> On 26/04/12 03:31 AM, Peter Kurrasch wrote:
> > I think I'm starting to get the picture. As Erwann and George have kindly
> > explained, the point of the randomness is not to prevent a hash collision
> > per se. Rather, the point is to frustrate efforts on the part of an
> > attacker to find a collision that works. I hope that's a fair and accurate
> > statement...?
>
> Well, the randomness is dealing with a particular attack by increasing
> the difficulty.
>
> Also, there is some confusion about the notion of "collision" which is
> rather boring and benign and "pre-image" attack which is ... actually
> dangerous. We have a real cert to hand - an image - so we are not
> dealing with some random pair of collisions, but a pre-image attack.

Collision is not benign at all, not in the signature business (which is what X.509 is about). Collision allows you to have several signatures for the cost of one, in the back of the signer.

Here, we're really dealing with collisions, collisions built by an attacker.
Using a hash function vulnerable to a pre-image attack would be catastrophic, even more than with a collision-vulnerable one.

[...]

> So the strategy is to place unpredictable, unreplaceable junk at the
> front. Which seriously cramps the attack.
>
> Now look at the graphic in 5.3. You'll see that in terms of
> changeability before the fixed value fields, the serial number is it.

The serial number is the best place to put the random data. But you can also place it in the subject name, if you can make sure it appears in the first block (in the sense of hash block size, which is 512 bytes for MD5 and SHA1). If you can't ensure this, then you can get screwed.

[...]

> > 2) When I receive a cert that doesn't match, I would like to check the
> > serial number to see if it's "newer" than the one I have. In such cases, I
> > know I need to do a full evaluation of the cert, it's contents, and the
> > authority chain. I'm concerned in this case that the cert I was using may
> > have been revoked. I'm concerned that the newer cert may or may not be a
> > fraud. For that matter, I'm concerned that the cert I was using was
> > fraudulent. But if everything checks out, I want to add the new cert to my
> > local cache but also keep the old one around so I know whether to trust it
> > the next time I encounter it.
>
> Yes, this is to assume that "serial" means serial, and/or that higher
> numbers means "newer". This meaning or implication has been explicitly
> withdrawn, enough already such that you can no longer rely upon it (CAs
> have been doing this for some time...)

It's also overloading what the serial number is.

For a manufactured product, as a customer, I can't assume that the serial number has any meaning. For some manufacturers it can have a structure (year, week, production unit, ...), for some others it may be a simple monotonic counter. Still as a customer, I don't need to know what this serial number means, I only need to know that this particular serial number is attached to this particular item. As the manufacturer, I of course need to map a serial number to a production center, maybe a design base, a model number, a date, a production line, etc, anything that could be useful to track down this item's construction.

That's the same in X.509. The serial number only needs to have a meaning for the certificate producer, not for the relying party.

[...]

> > 3) When the cert doesn't match, I also would like to check the serial
> > number to see if it's an *older* version of a certificate. Perhaps I've
> > seen it before, which means there's a chance I could re-use the trust
> > decisions I made at the time. I'm also concerned that the older cert may
> > have been revoked but the server admin hasn't updated the site yet. And,
> > just like the "new cert" case, perhaps the cert I was using is in fact
> > fraudulent--I'd like to check that too. Bottom line is that there's a
> > chance for optimization if the old cert is in my local cache--and if it
> > isn't I want to add it for the next time I encounter it.
>
> There is such a thing as over-optimisation :) Perhaps you should just
> take the hit. When someone starts dealing with a different cert,
> perhaps this is a good time to re-check everything about that customer,
> not try and squeeze the last few cycles out.

That would be a good decision.

In fact, even for Mr Kurrasch, the serial number doesn't need to be sequential. If it's different, his system checks if it already has seen it before. How is it checked? I'm guessing the serial number is stored in its "trust database". So the serial number here is used as a unique identifier. That's precisely what it is. A unique identifier among the CA. Nothing more.

[ianG]

(minor comments only, feel free to skip)

On 29/04/12 00:58 AM, Erwann Abalea wrote:
> Le samedi 28 avril 2012 02:46:01 UTC+2, ianG a écrit :

>> On 26/04/12 03:31 AM, Peter Kurrasch wrote:
>>> I think I'm starting to get the picture. As Erwann and George have kindly
>>> explained, the point of the randomness is not to prevent a hash collision
>>> per se. Rather, the point is to frustrate efforts on the part of an
>>> attacker to find a collision that works. I hope that's a fair and accurate
>>> statement...?
>>
>> Well, the randomness is dealing with a particular attack by increasing
>> the difficulty.
>>
>> Also, there is some confusion about the notion of "collision" which is
>> rather boring and benign and "pre-image" attack which is ... actually
>> dangerous. We have a real cert to hand - an image - so we are not
>> dealing with some random pair of collisions, but a pre-image attack.
>

> Collision is not benign at all,

http://en.wikipedia.org/wiki/Collision_attack

Hmm, ok, you're right! So this is a *prefix* -collision attack, not a
pre-image.

> not in the signature business (which is what X.509 is about).

Those in the signature business know never to let the attacker prepare
the text to be signed :)

> Collision allows you to have several signatures for the cost of one, in the back of the signer.

I see where the confusion comes from now, and I fear it will remains
so.... Was the prefix-collision label added after the RapidSSL attack?

> Here, we're really dealing with collisions, collisions built by an attacker.
> Using a hash function vulnerable to a pre-image attack would be catastrophic, even more than with a collision-vulnerable one.

Hmmm... I'm tempted to ask what the difference between a prefix and an
image is in this context. But I'm worried the answer is "bad engineering".


> [...]

>> So the strategy is to place unpredictable, unreplaceable junk at the
>> front. Which seriously cramps the attack.
>>
>> Now look at the graphic in 5.3. You'll see that in terms of
>> changeability before the fixed value fields, the serial number is it.
>

> The serial number is the best place to put the random data. But you can also place it in the subject name, if you can make sure it appears in the first block (in the sense of hash block size, which is 512 bytes for MD5 and SHA1). If you can't ensure this, then you can get screwed.

Yes, but can we fiddle with the subject name without impacting policy?

> [...]

>>> 2) When I receive a cert that doesn't match, I would like to check the
>>> serial number to see if it's "newer" than the one I have. In such cases, I
>>> know I need to do a full evaluation of the cert, it's contents, and the
>>> authority chain. I'm concerned in this case that the cert I was using may
>>> have been revoked. I'm concerned that the newer cert may or may not be a
>>> fraud. For that matter, I'm concerned that the cert I was using was
>>> fraudulent. But if everything checks out, I want to add the new cert to my
>>> local cache but also keep the old one around so I know whether to trust it
>>> the next time I encounter it.
>>
>> Yes, this is to assume that "serial" means serial, and/or that higher
>> numbers means "newer". This meaning or implication has been explicitly
>> withdrawn, enough already such that you can no longer rely upon it (CAs
>> have been doing this for some time...)
>

> It's also overloading what the serial number is.
>
> For a manufactured product, as a customer, I can't assume that the serial number has any meaning. For some manufacturers it can have a structure (year, week, production unit, ...), for some others it may be a simple monotonic counter. Still as a customer, I don't need to know what this serial number means, I only need to know that this particular serial number is attached to this particular item. As the manufacturer, I of course need to map a serial number to a production center, maybe a design base, a model number, a date, a production line, etc, anything that could be useful to track down this item's construction.
>
> That's the same in X.509. The serial number only needs to have a meaning for the certificate producer, not for the relying party.

Assuming a serial is serial is a reasonable assumption for a developer
to make. If that assumption wasn't wanted, then PKIX should change the
name to uniqueId and put a manufacturer's critical caveat on -- "users
keep mits off".

We're now overloading the serial to be not-serial and to be deliberately
unpredictable, so it no longer belongs to the CA anymore.

In other words, vendors as relying parties are telling CAs to put a
certain meaning perhaps better named as "entropy" in their serials.

All by way of showing how much of a joke this committee nonsense is.


> [...]

>>> 3) When the cert doesn't match, I also would like to check the serial
>>> number to see if it's an *older* version of a certificate. Perhaps I've
>>> seen it before, which means there's a chance I could re-use the trust
>>> decisions I made at the time. I'm also concerned that the older cert may
>>> have been revoked but the server admin hasn't updated the site yet. And,
>>> just like the "new cert" case, perhaps the cert I was using is in fact
>>> fraudulent--I'd like to check that too. Bottom line is that there's a
>>> chance for optimization if the old cert is in my local cache--and if it
>>> isn't I want to add it for the next time I encounter it.
>>
>> There is such a thing as over-optimisation :) Perhaps you should just
>> take the hit. When someone starts dealing with a different cert,
>> perhaps this is a good time to re-check everything about that customer,
>> not try and squeeze the last few cycles out.
>

> That would be a good decision.
>
> In fact, even for Mr Kurrasch, the serial number doesn't need to be sequential. If it's different, his system checks if it already has seen it before. How is it checked? I'm guessing the serial number is stored in its "trust database". So the serial number here is used as a unique identifier. That's precisely what it is. A unique identifier among the CA. Nothing more.

Exactly right. Once that confusion is cleared up, it is clear. Anyone
care to ask PKIX to fix it?

(Actually, as a developer one would go further and not trust the
uniqueness claimed by the serial. We are talking about security code
here... so certificates should be treated as suspect when anything
changes - re-evaluate. Which in engineering terms would suggest that
the cert be indexed using a hash ;-)




iang

[Erwann Abalea]

Le lundi 30 avril 2012 04:01:59 UTC+2, ianG a écrit :
> On 29/04/12 00:58 AM, Erwann Abalea wrote:
> > Le samedi 28 avril 2012 02:46:01 UTC+2, ianG a écrit :

[...]

> http://en.wikipedia.org/wiki/Collision_attack
>
> Hmm, ok, you're right! So this is a *prefix* -collision attack, not a
> pre-image.

> > not in the signature business (which is what X.509 is about).
>
> Those in the signature business know never to let the attacker prepare
> the text to be signed :)

They *should* know, yes ;)

> > Collision allows you to have several signatures for the cost of one, in the back of the signer.
>
> I see where the confusion comes from now, and I fear it will remains
> so.... Was the prefix-collision label added after the RapidSSL attack?

It was demonstrated before that. I think chosen-prefix collision attack was demonstrated in 2006 (can't find the paper). RapidSSL attack was performed in late 2008. The 2 years delay doesn't lower its impact, because the authors showed methods to generate an RSA key to ease the collision.

I think Opera was the first vendor to have requested some random data in the serial number for their root program. Then Microsoft, then Mozilla.

> > Here, we're really dealing with collisions, collisions built by an attacker.
> > Using a hash function vulnerable to a pre-image attack would be catastrophic, even more than with a collision-vulnerable one.
>
> Hmmm... I'm tempted to ask what the difference between a prefix and an
> image is in this context. But I'm worried the answer is "bad engineering".

Pre-image attack allows you, as an attacker, to take a signed object you're not concerned with, extract the signature (and hash), generate a new document that gives the same hash, and the signature will apply to it. The pre-image attack is the "generate a document given the hash" part; you obviously have a collision attack once you have a pre-image one.

Pre-image attacks are also bad for HMAC and other PRF constructions (such as OS PRNG, TLS PRF, or hardware random post-treatment).

> > [...]
> >> So the strategy is to place unpredictable, unreplaceable junk at the
> >> front. Which seriously cramps the attack.
> >>
> >> Now look at the graphic in 5.3. You'll see that in terms of
> >> changeability before the fixed value fields, the serial number is it.
> >
> > The serial number is the best place to put the random data. But you can also place it in the subject name, if you can make sure it appears in the first block (in the sense of hash block size, which is 512 bytes for MD5 and SHA1). If you can't ensure this, then you can get screwed.

A mistake in my statement, the hash block size of MD5 and SHA1 is 512 *bits*, not *bytes*.

> Yes, but can we fiddle with the subject name without impacting policy?

The policy is written by the CA, who's free to add a "personal" attribute in the subject name. Well, I guess.

> > [...]

> > That's the same in X.509. The serial number only needs to have a meaning for the certificate producer, not for the relying party.
>
> Assuming a serial is serial is a reasonable assumption for a developer
> to make. If that assumption wasn't wanted, then PKIX should change the
> name to uniqueId and put a manufacturer's critical caveat on -- "users
> keep mits off".

Changing name elements is Bad™, it breaks the uniqueness of XER representation (it has already been done with the nonRepudiation/contentCommitment bit, though).

> We're now overloading the serial to be not-serial and to be deliberately
> unpredictable, so it no longer belongs to the CA anymore.
>
> In other words, vendors as relying parties are telling CAs to put a
> certain meaning perhaps better named as "entropy" in their serials.

The serial must be random to the RP, it can still be deterministic for the CA, if necessary.

Looking at the various X.509 editions I have, here's what I find in the definitions:

-----
certificate serial number: An integer value, unique within the issuing authority, which is unambiguously associated with a certificate issued by that authority.
-----

This exact text is present at least since X.509v2, 1993 edition, and it hasn't changed since (I don't have the 1988 edition). No other constraint is imposed on it, no other meaning either. It can be random, it can be sequential, it can be anything, as long as it's an identifier of this certificate for this CA. RP is not considered here.

Compare this to the CRLNumber extension, introduced in 1997 (first edition of X.509v3):

-----
This CRL extension field conveys a monotonically increasing sequence number for each CRL issued by a given CRL issuer through a given CA directory attribute or CRL distribution point. It allows a CRL user to detect whether CRLs issued prior to the one being processed were also seen and processed.
-----

Different.

> > [...]

> (Actually, as a developer one would go further and not trust the
> uniqueness claimed by the serial. We are talking about security code
> here... so certificates should be treated as suspect when anything
> changes - re-evaluate. Which in engineering terms would suggest that
> the cert be indexed using a hash ;-)

With a collision-resistant hash function, of course.

[Peter Kurrasch]

Before I respond below let me add a little background. My perspective
is from the embedded software realm where resources and capabilities and
options are limited compared to a "more ideal" environment, such as the
desktop computer where I'm using Firefox and Thunderbird! That said I
think that ideas and solutions which would help the embedded space will
also help the broader Mozilla space--to say nothing of the Boot-to-Gecko
efforts.

So, with that said....

>> The serial number is the best place to put the random data.

Agreed.

>> But you can also place it in the subject name, if you can make sure
>> it appears in the first block (in the sense of hash block size, which
>> is 512 bytes for MD5 and SHA1). If you can't ensure this, then you
>> can get screwed.

For what it's worth I would say the validity dates are fair game, too.
They might not be great options and there are good reasons to choose
the serial number field over the dates, but as far as I'm concerned they
can be "repurposed" as they say. (Surely, most people on this list
would agree defining a validity period down to a precise second is
overkill, no? How about hour? Day?)

> Yes, but can we fiddle with the subject name without impacting policy?

I would strongly discourage that practice! Technically speaking it is
possible, yes, but I think it must be considered only as a last resort.
While in theory a software implementation is not supposed to impose
limits on something like this, the unfortunate reality is that many
embedded systems do have a maximum length they can realistically
support. I'd hate to see that space used up by something like random
data when other options are available.

>>>> 2) When I receive a cert that doesn't match, I would like to check the
>>>> serial number to see if it's "newer" than the one I have. In such
>>>> cases, I
>>>> know I need to do a full evaluation of the cert, it's contents, and
>>>> the
>>>> authority chain. I'm concerned in this case that the cert I was
>>>> using may
>>>> have been revoked. I'm concerned that the newer cert may or may
>>>> not be a
>>>> fraud. For that matter, I'm concerned that the cert I was using was
>>>> fraudulent. But if everything checks out, I want to add the new
>>>> cert to my
>>>> local cache but also keep the old one around so I know whether to
>>>> trust it
>>>> the next time I encounter it.
>>> Yes, this is to assume that "serial" means serial, and/or that higher
>>> numbers means "newer". This meaning or implication has been explicitly
>>> withdrawn, enough already such that you can no longer rely upon it (CAs
>>> have been doing this for some time...)

>> It's also overloading what the serial number is.
>>
>> For a manufactured product, as a customer, I can't assume that the
>> serial number has any meaning. For some manufacturers it can have a
>> structure (year, week, production unit, ...), for some others it may
>> be a simple monotonic counter. Still as a customer, I don't need to
>> know what this serial number means, I only need to know that this
>> particular serial number is attached to this particular item. As the
>> manufacturer, I of course need to map a serial number to a production
>> center, maybe a design base, a model number, a date, a production
>> line, etc, anything that could be useful to track down this item's
>> construction.
>>

>> That's the same in X.509. The serial number only needs to have a
>> meaning for the certificate producer, not for the relying party.

I think we might be in agreement here...but I can't tell for sure. If
we were to change the name, hypothetically speaking, from "serial
number" to "production code" in the X.509 cert, I could accept
that...provided we come to an agreement on the coding format.

The slight issue I have with what you say is that I see 2 different
consumers of certificates. Obviously, one is the end-user who, by and
large, will have no interest in making any sense of the serial
number/production code. Just because my car has a VIN number doesn't
mean I really care about it.

The other user is the security software that receives and interprets the
cert. In some cases the software could choose to make sense of such a
code. To use the VIN example, my insurance company is interested in
understanding the VIN code so that they can set my rates higher if I
have a 6-cylinder engine vs a 4-cylinder. And they could tell if I lied
about the make and model....

So, I think it's okay to at least define a code/format even though it
will be meaningless junk to most people. I don't think it would be a
controversial idea to the CAs since I've seen many certs out there
already that appear to combine sequencing and entropy.

>>>> 3) When the cert doesn't match, I also would like to check the serial
>>>> number to see if it's an *older* version of a certificate. Perhaps
>>>> I've
>>>> seen it before, which means there's a chance I could re-use the trust
>>>> decisions I made at the time. I'm also concerned that the older
>>>> cert may
>>>> have been revoked but the server admin hasn't updated the site
>>>> yet. And,
>>>> just like the "new cert" case, perhaps the cert I was using is in fact
>>>> fraudulent--I'd like to check that too. Bottom line is that there's a
>>>> chance for optimization if the old cert is in my local cache--and
>>>> if it
>>>> isn't I want to add it for the next time I encounter it.
>>> There is such a thing as over-optimisation :) Perhaps you should just
>>> take the hit. When someone starts dealing with a different cert,
>>> perhaps this is a good time to re-check everything about that customer,
>>> not try and squeeze the last few cycles out.

>> That would be a good decision.

In a Mozilla-style product I agree. In the embedded world, doing all
the checks is not going to be realistic in all cases for a variety of
reasons. And that's why I would like to do "some" checks instead of,
literally, none.

>> In fact, even for Mr Kurrasch, the serial number doesn't need to be
>> sequential. If it's different, his system checks if it already has
>> seen it before. How is it checked? I'm guessing the serial number is
>> stored in its "trust database". So the serial number here is used as
>> a unique identifier. That's precisely what it is. A unique identifier
>> among the CA. Nothing more.
> Exactly right. Once that confusion is cleared up, it is clear.
> Anyone care to ask PKIX to fix it?

Silly IanG...that's why we have a CABForum! :-)

> (Actually, as a developer one would go further and not trust the
> uniqueness claimed by the serial. We are talking about security code
> here... so certificates should be treated as suspect when anything
> changes - re-evaluate. Which in engineering terms would suggest that
> the cert be indexed using a hash ;-)

Actually, the serial number alone does not establish uniqueness even for
2 certs with the same subject/issuer pair! I don't have an exact
example in front of me now, but I'm pretty sure the MD2-signed and the
SHA1-signed certs for Verisign's PPCA3(?) from 1996(?) have the same
serial number (probably just a "1"). I know there are other examples, too.

[Kyle Hamilton]

On Wed, Apr 25, 2012 at 10:31 AM, Peter Kurrasch <fhw...@gmail.com> wrote:
> 2) When I receive a cert that doesn't match, I would like to check the
> serial number to see if it's "newer" than the one I have.  In such cases, I
> know I need to do a full evaluation of the cert, it's contents, and the
> authority chain.  I'm concerned in this case that the cert I was using may
> have been revoked.  I'm concerned that the newer cert may or may not be a
> fraud.  For that matter, I'm concerned that the cert I was using was
> fraudulent.  But if everything checks out, I want to add the new cert to my
> local cache but also keep the old one around so I know whether to trust it
> the next time I encounter it.

The serial number is not the best place to see if it's "newer", only that it is "different". "Newer" is appropriate with NotBefore and NotAfter, and is subject to the Issuer's CPS and CP.

> 3) When the cert doesn't match, I also would like to check the serial
> number to see if it's an *older* version of a certificate.  Perhaps I've
> seen it before, which means there's a chance I could re-use the trust
> decisions I made at the time.  I'm also concerned that the older cert may
> have been revoked but the server admin hasn't updated the site yet.  And,
> just like the "new cert" case, perhaps the cert I was using is in fact
> fraudulent--I'd like to check that too.  Bottom line is that there's a
> chance for optimization if the old cert is in my local cache--and if it
> isn't I want to add it for the next time I encounter it.

Again, NotBefore and NotAfter. Also, be aware that PKIs do have the option to issue multiple certificates for multiple keys for the same principal with the same DN with overlapping validity periods. Instead of relying on a One True "Valid" Certificate Per Principal, there is a set of potentially valid certificates for the single principal which may differ only in their subjectPublicKeyInfo and Validity.

Personally, I wish the CAs would make CABF a Single Unified PKI For Authoritative Identity. Nobody in the CA industry wants to centralize the policy authority like that, they're all worried about being able to provide differentiated services, and being able to push their own agendas to the detriment of all others, all customers, and all relying parties.

And as much as I hate to say it, Mozilla is complicit in this fracturing of the space that is supposed to have one and only one purpose: ensure that state identity is bound to the holder of the private key reflected in the sPKI.

> I hope the example is clear enough, but really it comes down to this: being
> able to distinguish "newer" and "older" certs is useful--perhaps even
> important.

This is why NotBefore and NotAfter exist. Requiring that serial numbers be monotonically increasing is something that CAs fought against, because they didn't like the idea of disclosing how many customers they have/certificates they've issued. (Also, neither X.509 nor PKIX require monotonic or increasing serial numbers, only that they are unique per-Issuer. It is not okay to rely on any semantic which is not explicitly within the normative references of the standards, no matter that the title of the field may suggest something different.)

The idea of One True Anything is harmful. The idea of One True Certificate is even more harmful. How about Two or Three True Certficates, from different Issuers, so that if trust in one of those Issuers must be withdrawn the other(s) have the opportunity to still be valid?

-Kyle H

[Kyle Hamilton]

On Wed, May 2, 2012 at 11:30 PM, Peter Kurrasch <fhw...@gmail.com> wrote:
> Before I respond below let me add a little background.  My perspective is
> from the embedded software realm where resources and capabilities and
> options are limited compared to a "more ideal" environment, such as the
> desktop computer where I'm using Firefox and Thunderbird!  That said I think
> that ideas and solutions which would help the embedded space will also help
> the broader Mozilla space--to say nothing of the Boot-to-Gecko efforts.

In the embedded software realm, you pretty much have to re-perform all checks anyway, due to RAM and persistent data storage constraints.

>
> So, with that said....
[...]

> I think we might be in agreement here...but I can't tell for sure.  If we
> were to change the name, hypothetically speaking, from "serial number" to
> "production code" in the X.509 cert, I could accept that...provided we come
> to an agreement on the coding format.

The coding format is already agreed on, by PKIX. A positive integer value up to 20 bytes long. (This is, in fact, an additional requirement on top of X.509, which has no requirement that it be a positive value.)

If you want to change it, you will need to go to PKIX, which will probably kick you up to ITU (as it did me, with my attempt to provide an extended CRL format with v4).

> The slight issue I have with what you say is that I see 2 different
> consumers of certificates.  Obviously, one is the end-user who, by and
> large, will have no interest in making any sense of the serial
> number/production code.  Just because my car has a VIN number doesn't mean I
> really care about it.
>
> The other user is the security software that receives and interprets the
> cert.  In some cases the software could choose to make sense of such a code.
>  To use the VIN example, my insurance company is interested in understanding
> the VIN code so that they can set my rates higher if I have a 6-cylinder
> engine vs a 4-cylinder.  And they could tell if I lied about the make and
> model....

It is also worth noting that VIN is specified by international treaty. PKIX is not.

> So, I think it's okay to at least define a code/format even though it will
> be meaningless junk to most people.  I don't think it would be a
> controversial idea to the CAs since I've seen many certs out there already
> that appear to combine sequencing and entropy.

The problem I see is that it would require such things as reprogramming and opening their sealed HSMs.

> In a Mozilla-style product I agree.  In the embedded world, doing all the
> checks is not going to be realistic in all cases for a variety of reasons.
>  And that's why I would like to do "some" checks instead of, literally,
> none.

Then store the serial number and its result in a prime-sized hash table, and verify if it's already been seen.

You're not going to change the rest of the world. (Trust me, I've been trying.) The only thing you can do is use the semantics which do exist to do the things that you need to do.

This is the bane of all ITU X.500-series protocols. They overspecify policy in the technical standards, and then underspecify what the real world needs to get work done.

>> Exactly right.  Once that confusion is cleared up, it is clear.  Anyone
>> care to ask PKIX to fix it?
>
> Silly IanG...that's why we have a CABForum!  :-)

PayPal has stated that they do not wish CABForum to issue technical standards.

I think CABForum's only place is issuing policy standards which might involve technical encoding issues. (Which means, Mr. Kurrasch, that I think they could implement something like 20 bits of entropy in their serial number formats-- if they wanted to enforce that all existing HSMs be scrapped, new keys generated and distributed, and so on.)

> Actually, the serial number alone does not establish uniqueness even for 2
> certs with the same subject/issuer pair!  I don't have an exact example in
> front of me now, but I'm pretty sure the MD2-signed and the SHA1-signed
> certs for Verisign's PPCA3(?) from 1996(?) have the same serial number
> (probably just a "1").  I know there are other examples, too.

NSS fails on that. In fact, it will absolutely prevent the same serial number from the same Issuer with any different data from even having the opportunity to see the website asserting the second instance. This is strict conformance with X.509, as quoted by Mr Abalea.

-Kyle H

[Peter Kurrasch]

The trouble with notbefore/notafter is that they are not consistently
modified. In my observations the serial number field would always get
updated (with a "different" value if you want to call it that) whereas
the notbefore date might be left alone to reflect a "first day of issue"
type of meaning. This was observed with some root certs as well
as intermediates. End certs may very well have their dates updated on
each issuance, but I really couldn't say.

Look, the whole point of this has been to see if there is any consensus
among other "trust system policy implementers" when it comes to handling
non-compliant certificates. I think there is a middle ground between
full, proper security measures and "bypass all security checks to make
it work" (which is what I frequently encounter). It may interest some
in this forum to know that I've actually had to change my own security
implementation purely because of bugs in other people's products.

Anyway, this has gone on long enough and isn't going anywhere, so I'm
content to drop the matter. I'm glad we had the discussion though.