TSYS Application for SHA-1 Issuance - Counter-cryptanalysis

[Andrew R. Whalley]

Greetings,

I have run the tool provided by dr.ir. Marc Stevens [1] on the
tbsCertificates provided by Symantec [2]

And see no evidence of collisions:

$ ./sha1dcsum_partialcoll *.tbs
6ead26663275c388662dfdbc23ff0a76cdcf74dc ssl1.tsysacquiring.net.1.tbs
3365793f36c197047b2f595c0f85c67b807c765f ssl1.tsysacquiring.net.2.tbs
3c47155a5d9880a6893925e1c4479f914b3b9ffe ssl1.vitalps.net.1.tbs
d130d1a8c51bce7323ba984b2f6298d0750405f4 ssl1.vitalps.net.2.tbs
c9eb52c30bfaaaba5a1e060723e3c9e4b25f7b1e ssl2.vitalps.net.1.tbs
3698794f1cabc3036380cc2adbc2805393098c45 ssl2.vitalps.net.2.tbs
e7233e69a89b6b7568f790482b73f635d2464a95 ssl3.vitalps.net.1.tbs
9c7bbae0fc9b08c5304908bd956c5b4b37c4e1c7 ssl3.vitalps.net.2.tbs

I'd be interested to know if anybody else replicates this.

Marc - I believe that the tool as posted doesn't give assurance to the full
80 bit security level. If that's true do you have an estimate of the
security level it does provide?

Many thanks,

Andrew

[1] see https://marc-stevens.nl/research/ &
https://svn.marc-stevens.nl/collisiondetection/
[2] https://cabforum.org/pipermail/public/2016-July/007999.html

[Erwann Abalea]

Le mardi 19 juillet 2016 22:05:13 UTC+2, Andrew Whalley a écrit :
> Greetings,
>
> I have run the tool provided by dr.ir. Marc Stevens [1] on the
> tbsCertificates provided by Symantec [2]
>
> And see no evidence of collisions:
>
> $ ./sha1dcsum_partialcoll *.tbs
> 6ead26663275c388662dfdbc23ff0a76cdcf74dc ssl1.tsysacquiring.net.1.tbs
> 3365793f36c197047b2f595c0f85c67b807c765f ssl1.tsysacquiring.net.2.tbs
> 3c47155a5d9880a6893925e1c4479f914b3b9ffe ssl1.vitalps.net.1.tbs
> d130d1a8c51bce7323ba984b2f6298d0750405f4 ssl1.vitalps.net.2.tbs
> c9eb52c30bfaaaba5a1e060723e3c9e4b25f7b1e ssl2.vitalps.net.1.tbs
> 3698794f1cabc3036380cc2adbc2805393098c45 ssl2.vitalps.net.2.tbs
> e7233e69a89b6b7568f790482b73f635d2464a95 ssl3.vitalps.net.1.tbs
> 9c7bbae0fc9b08c5304908bd956c5b4b37c4e1c7 ssl3.vitalps.net.2.tbs
>
> I'd be interested to know if anybody else replicates this.

For whatever the result means, I do replicate it, using the trunk version.

[Marc Stevens]

Dear Andrew,

I have created an extended version of my collision detection library [1] that,
instead of a small selection of best disturbance vectors for SHA-1 collision attacks,
simply tests all disturbance vectors within the two classes (see p125 of [2]).

This should rule out *all* cryptanalytic collision attacks that
can be build from *any* disturbance vector mentioned in the literature (and more).

I have run it over the initial set of 8 certs given by TSYS and the latest set of 7 certs,
no collision attacks were detected.
Note that these results are only valid IF the hash-then-sign SHA1-RSA signatures for these certs use the exact SHA-1 hashes below.
I have not checked whether there is any further X.509/ASN1 encapsulation of the ToBeSignedPart in these files
that should have been removed before checking.

[stevens TSYS1]$ time ../detectcoll_allDVs *.tbs
sha1 6ead26663275c388662dfdbc23ff0a76cdcf74dc ssl1.tsysacquiring.net.1.tbs
sha1 3365793f36c197047b2f595c0f85c67b807c765f ssl1.tsysacquiring.net.2.tbs
sha1 3c47155a5d9880a6893925e1c4479f914b3b9ffe ssl1.vitalps.net.1.tbs
sha1 d130d1a8c51bce7323ba984b2f6298d0750405f4 ssl1.vitalps.net.2.tbs
sha1 c9eb52c30bfaaaba5a1e060723e3c9e4b25f7b1e ssl2.vitalps.net.1.tbs
sha1 3698794f1cabc3036380cc2adbc2805393098c45 ssl2.vitalps.net.2.tbs
sha1 e7233e69a89b6b7568f790482b73f635d2464a95 ssl3.vitalps.net.1.tbs
sha1 9c7bbae0fc9b08c5304908bd956c5b4b37c4e1c7 ssl3.vitalps.net.2.tbs
Checked 5120 disturbance vectors

real 0m0.134s
user 0m0.132s
sys 0m0.002s

[stevens TSYS2]$ time ../detectcoll_allDVs *.der
sha1 f75716390925b752b403a7bbf6acb349de9d8d09 ssl1.tsys.1.txt.der
sha1 683c27025922c33c5dffb0c378368f09cd68acab ssl1.tsys.2.txt.der
sha1 6740101673f95f50d97da18ce5d5d5d6e9bfe4b0 ssl1.vitalps.1.txt.der
sha1 a4e0b6159b89f505d12b786a5562e808a7857786 ssl1.vitalps.2.txt.der
sha1 24df6cf6d89a33f5262924169ff1a26ae69d49e8 ssl2.vitalps.1.txt.der
sha1 57f51b7558805a953505426ee6757606bc13609d ssl2.vitalps.2.txt.der
sha1 6d56564822a633f643f73b812ef0f86637af047d ssl3.vitalps.1.txt.der
Checked 5120 disturbance vectors

real 0m0.137s
user 0m0.137s
sys 0m0.000s

Note that despite one fewer cert processing the second set takes a bit longer
because the overall length is longer:
[stevens TSYS1]$ cat *.tbs | wc -c
8468
[stevens TSYS2]$ cat *.der | wc -c
9334

Best regards,
Marc Stevens

[1] see https://marc-stevens.nl/research/#software
[1] https://marc-stevens.nl/research/papers/phdthesis.pdf

On 2016-07-19 22:04, Andrew R. Whalley wrote:
> Greetings,
>

> I have run the tool provided by dr.ir <http://dr.ir>. Marc Stevens [1] on the tbsCertificates provided by Symantec [2]

>
> And see no evidence of collisions:
>
> $ ./sha1dcsum_partialcoll *.tbs
> 6ead26663275c388662dfdbc23ff0a76cdcf74dc ssl1.tsysacquiring.net.1.tbs
> 3365793f36c197047b2f595c0f85c67b807c765f ssl1.tsysacquiring.net.2.tbs
> 3c47155a5d9880a6893925e1c4479f914b3b9ffe ssl1.vitalps.net.1.tbs
> d130d1a8c51bce7323ba984b2f6298d0750405f4 ssl1.vitalps.net.2.tbs
> c9eb52c30bfaaaba5a1e060723e3c9e4b25f7b1e ssl2.vitalps.net.1.tbs
> 3698794f1cabc3036380cc2adbc2805393098c45 ssl2.vitalps.net.2.tbs
> e7233e69a89b6b7568f790482b73f635d2464a95 ssl3.vitalps.net.1.tbs
> 9c7bbae0fc9b08c5304908bd956c5b4b37c4e1c7 ssl3.vitalps.net.2.tbs
>
> I'd be interested to know if anybody else replicates this.
>

[Rick Andrews]

Marc, it's been pointed out in the CABF list [1] that the analysis you did on the second set of seven was on the original certificates, on which we based new TBSCertificates. Your analysis wasn't done on the new TBSCertificates. The new TBSCertificates differ from the original certificates only in serial number and date fields.

[1] https://cabforum.org/pipermail/public/2016-July/008147.html

[Marc Stevens]

Dear all,

It has been pointed out to me that the second set I checked are actually old certificates instead of the TBSparts.
As I mention below, the counter-cryptanalysis is only valid for the exact TBS part that has those hashes.

Therefore, I have redone my analysis on the TBS parts of the second set:
[stevens TSYS2]$ time ../detectcoll_allDVs *.tbs
sha1 d0e91ceed6faf88ebb3489bc5a55b12d3659fa72 ssl1.tsys.1.tbs
sha1 c88c5eb29a1981af757c357b58823fc6ca1b4533 ssl1.tsys.2.tbs
sha1 1b335f20ef2e42c4749e2dd9cccaccab74030493 ssl1.vitalps.1.tbs
sha1 61fe7aeec2bbd2499ccba62e4e7e90c969c0bad4 ssl1.vitalps.2.tbs
sha1 784d225138ef8bc3e027099626f0fe4c32e1f91b ssl2.vitalps.1.tbs
sha1 75b7210f19cb2ccff69f6db2fca6132455313586 ssl2.vitalps.2.tbs
sha1 d8c2359f440c14afbc806274b8809b3208f41311 ssl3.vitalps.1.tbs
Checked 5120 disturbance vectors

real 0m0.122s
user 0m0.120s
sys 0m0.002s

Again, no collision attacks were detected.

Best regards,
Marc Stevens

> On 2016-07-19 22:04, Andrew R. Whalley wrote:
>> Greetings,
>>

>> I have run the tool provided by dr.ir <http://dr.ir>. Marc Stevens [1] on the tbsCertificates provided by Symantec [2]