ETOOBUSY 🚀 minimal blogging for the impatient
Cryptopals 32 - Break HMAC-SHA1 with a slightly less artificial timing leak
TL;DR
The challenge is amazing:
Reduce the sleep in your
insecure_compareuntil your previous solution breaks. (Try 5ms to start.)Now break it again.
My server has an endpoint to set a new delay, so we’ll start at 10 ms:
$ curl -X PUT -d 10 http://localhost:3000/drag-delay
set DRAG_DELAY to '0.01' s
Let’s see how it goes:
$ perl 31.pl
rock bottom: <0.00235080718994141>
1 expanding '' with time 10
2 expanding 'c' with time 0.0218231678009033
3 expanding 'cd' with time 0.0327532291412354
4 expanding '2' with time 0.0213112831115723
5 expanding 'cd4' with time 0.0415952205657959
6 expanding 'cd4a' with time 0.0521893501281738
7 expanding 'cd4e' with time 0.0515191555023193
8 expanding 'cd4a1' with time 0.0617702007293701
9 expanding 'cd4a1e' with time 0.0711753368377686
10 expanding 'cd4a1e7' with time 0.0827581882476807
11 expanding 'cd4a1e7a' with time 0.0915381908416748
12 expanding 'cd4a1e7a3' with time 0.10275936126709
13 expanding 'cd4a1e7a30' with time 0.113579273223877
14 expanding 'cd4a1e7a303' with time 0.123333215713501
15 expanding 'cd4a1e7a3032' with time 0.131584167480469
16 expanding 'cd4a1e7a3032a' with time 0.142828226089478
17 expanding 'cd4a1e7a3032a9' with time 0.153549194335938
18 expanding 'cd4a1e7a3032ab' with time 0.152954339981079
19 expanding 'cd4a1e7a3032ac' with time 0.152782201766968
20 expanding 'cd4a1e7a3032a98' with time 0.162707090377808
21 expanding 'cd4a1e7a3032a982' with time 0.171960115432739
22 expanding 'cd4a1e7a3032a9822' with time 0.182420253753662
23 expanding 'cd4a1e7a3032a9822c' with time 0.192055225372314
24 expanding 'cd4a1e7a3032a9822c6' with time 0.202383279800415
25 expanding 'cd4a1e7a3032a9822c6a' with time 0.212062120437622
26 expanding 'cd4a1e7a3032a9822c6a2' with time 0.222258329391479
27 expanding 'cd4a1e7a3032a9822c6a2b' with time 0.234071254730225
28 expanding 'cd4a1e7a3032a9822c6a23' with time 0.232309341430664
29 expanding 'cd4a1e7a3032a9822c6f' with time 0.211941242218018
30 expanding 'cd4a1e7a3032abf' with time 0.161456346511841
31 expanding 'cd4a1e7a3032a988' with time 0.171536207199097
32 expanding 'cd4a1e7a3032a98e' with time 0.171491146087646
33 expanding 'cd4a1e7a3032a9822c6a2be' with time 0.241381168365479
34 expanding 'cd4a1e7a3032a9822c6a2be1' with time 0.251925230026245
35 expanding 'cd4a1e7a3032a9822c6a2be13' with time 0.26183819770813
36 expanding 'cd4a1e7a3032a9822c6a2be13a' with time 0.272388219833374
37 expanding 'cd4a1e7a3032a9822c6a2be13af' with time 0.282279253005981
38 expanding 'cd4a1e7a3032a9822c6a2be13ad' with time 0.282169342041016
39 expanding 'cd4a1e7a3032a9822c6a2be13ad5' with time 0.292771339416504
40 expanding 'cd4a1e7a3032a9822c6a2be13ad54' with time 0.302766084671021
41 expanding 'cd4a1e7a3032a9822c6a2be13ad546' with time 0.312847375869751
42 expanding 'cd4a1e7a3032a9822c6a2be13ad54d' with time 0.312140226364136
43 expanding 'cd4a1e7a3032a9822c6a2be13ad54f' with time 0.312088966369629
44 expanding 'cd4a1e7a3032a9822c6a2be13ad546d' with time 0.321981191635132
45 expanding 'cd4a1e7a3032a9822c6a2be13ad546dc' with time 0.332399129867554
46 expanding 'cd4a1e7a3032a9822c6a2be13ad546dc5' with time 0.343223094940186
47 expanding 'cd4a1e7a3032a9822c6a2be13ad546dc5c' with time 0.359662294387817
48 expanding 'cd4a1e7a3032a9822c6a2be13ad546dc56' with time 0.352449178695679
49 expanding 'cd4a1e7a3032a9822c6a2be13ad546dc560' with time 0.363301038742065
50 expanding 'cd4a1e7a3032a9822c6a2be13ad546dc5f' with time 0.352289199829102
51 expanding 'cd4a1e7a3032a9822c6a2be13ad546dc5604' with time 0.372348308563232
52 expanding 'cd4a1e7a3032a9822cd' with time 0.201143026351929
53 expanding 'cd4a1e7a3032a9822c6a2be13d' with time 0.271499156951904
54 expanding 'cd4a1e7a3032a9822c6a2be13ad5465' with time 0.321747303009033
55 expanding 'cd4a1e7a3032a9822c6a2be13ad546dc5603' with time 0.371908187866211
56 expanding 'cd4a1e7a3032a9822c6a2be13ad546dc56038' with time 0.383743047714233
57 expanding 'cd4a1e7a3032a9822c6a2be13ad546dc56038e' with time 0.392742156982422
58 expanding 'cd4a1e7a3032a9822c6a2be13ad546dc56038e2' with time 0.408397197723389
cd4a1e7a3032a9822c6a2be13ad546dc56038e24
it took 275.352645158768 s
Some back-and-forth with dead ends, but they are easily sent to the back and the right path is eventually chosen.
OK, let’s move on to the suggested 5 ms. It will be a long ride, but time-wise we have comparable results with respect to 10 ms, because comparisons are faster and we can try more in a second:
$ curl -X PUT -d 5 http://localhost:3000/drag-delay
set DRAG_DELAY to '0.005' s
$ perl 31.pl
rock bottom: <0.00249004364013672>
1 expanding '' with time 10
2 expanding '5' with time 0.0207858085632324
3 expanding '7' with time 0.0203299522399902
4 expanding 'c' with time 0.0180199146270752
5 expanding '9' with time 0.0177700519561768
6 expanding '4' with time 0.0169291496276855
7 expanding '95' with time 0.0226109027862549
8 expanding '5e' with time 0.0201320648193359
9 expanding 'cc' with time 0.0200600624084473
...
28 expanding '3' with time 0.0112988948822021
29 expanding 'c0' with time 0.0165829658508301
30 expanding 'cc3' with time 0.0220019817352295
31 expanding 'cd5' with time 0.0218799114227295
32 expanding 'cd4a' with time 0.0272889137268066
33 expanding 'cd4a1' with time 0.0329890251159668
34 expanding 'cd4a1e' with time 0.0387699604034424
35 expanding 'cd4a1e5' with time 0.0443007946014404
36 expanding 'ca' with time 0.0163288116455078
37 expanding '955' with time 0.0217189788818359
38 expanding 'c0c' with time 0.0216929912567139
39 expanding '4f' with time 0.0162100791931152
40 expanding 'cd3' with time 0.0216000080108643
41 expanding '30' with time 0.016150951385498
...
101 expanding 'cd4d9' with time 0.0306041240692139
102 expanding 'cd4a1e7a3032a6' with time 0.0764930248260498
103 expanding 'cd4a1e7a3032a9822c6a' with time 0.107028007507324
104 expanding 'cd4a1e7a3032a9822c6a2' with time 0.113942861557007
105 expanding 'cd4a1e7a3032a9822c6a2b' with time 0.118875026702881
106 expanding 'cd4a1e7a3032a9822c6a2c' with time 0.118874073028564
107 expanding 'cd4a1e7a3032a9822c6a21' with time 0.117969751358032
108 expanding 'cd4a1e7a3032a94' with time 0.0815320014953613
109 expanding 'cd4a125' with time 0.0407388210296631
110 expanding '99' with time 0.015268087387085
111 expanding 'cd4a1e7a3e' with time 0.0559778213500977
112 expanding 'cab' with time 0.0203399658203125
113 expanding 'cd4a1e7a3032a9822c6a2be' with time 0.122022867202759
114 expanding 'cd4a1e7a3032a9822c6a2be1' with time 0.128488779067993
115 expanding 'cd4a1e7a3032a9822c6a2be13' with time 0.132316112518311
116 expanding 'cd4a1e7a3032a9822c6a2be13a' with time 0.137531042098999
117 expanding 'cd4a1e7a3032a98223' with time 0.0965938568115234
118 expanding 'cd4a1e7a3032a9822c6a2be13ad' with time 0.142346858978271
...
192 expanding 'cd4a1e7a3032a9822c6a2be13ad546dc56038' with time 0.19153904914856
193 expanding 'cd4a1e7a3032a9822c6a2be13ad546dc56038e' with time 0.199120998382568
194 expanding 'cd4a1e7a3032a9822c6a2be13ad546dc56038e2' with time 0.204922914505005
cd4a1e7a3032a9822c6a2be13ad546dc56038e24
it took 291.389113903046 s
Now let’s try 3 ms:
$ curl -X PUT -d 3 http://localhost:3000/drag-delay
set DRAG_DELAY to '0.003' s
$ perl 31.pl
rock bottom: <0.00194191932678223>
1 expanding '' with time 10
2 expanding 'c' with time 0.0129361152648926
3 expanding 'c4' with time 0.0167849063873291
4 expanding 'd' with time 0.0110640525817871
5 expanding 'ce' with time 0.0156021118164062
6 expanding 'cd' with time 0.0155830383300781
7 expanding 'a' with time 0.0103001594543457
8 expanding '9' with time 0.0102221965789795
9 expanding 'f' with time 0.00998806953430176
...
2703 expanding 'cad7d' with time 0.018348217010498
2704 expanding 'cd4ea47' with time 0.0244641304016113
2705 expanding 'cd4a18420' with time 0.0305790901184082
2706 expanding 'cd4a1e7a3032a73' with time 0.0489261150360107
2707 expanding 'cd4a1e7a3032a9825782' with time 0.0642142295837402
2708 expanding 'cd4a1e7a3032a9822c6a2be13ad546dc56' with time 0.10702109336853
2709 expanding 'cd4a1e7a3032a9822c6a2be13ad546dc560' with time 0.111745119094849
2710 expanding 'cd4a1e7a3032a9822c6a2be13ad546dc5603' with time 0.113998889923096
2711 expanding 'cd4a1e7a3032a9822c6a2be13ad546dc56038' with time 0.116994142532349
2712 expanding 'cd4a1e7a3032a9822c6a2be13ad546dc56038e' with time 0.120242118835449
2713 expanding 'cd4a1e7a3032a9822c6a2be13ad546dc56038e2' with time 0.123305082321167
cd4a1e7a3032a9822c6a2be13ad546dc56038e24
it took 1585.4443359375 s
It takes considerably more but it gets there in reasonable time anyway (about 25 minutes in the run above). There’s actually no real point where the solution breaks –no alternative is rules out, so technically speaking this solution is correct.
On the other hand, though, taking too much time would be as if it broke. There are a couple things we might do in this case:
- we didn’t really do any averaging, except for good candidates and only up to a certain point. It’s not even averaging, but taking the minimum. So that’s surely one way ahead to explore, with bigger repetition counts being justified by the quicker evaluation.
- We might want to do more precise measurements, e.g. by going to a lower level with C code.
- We might adopt a multi-level queuing approach in which an expansion updates all the way up to shorter codes, while still keeping them though. I’m not sure this would really help but it sort of might with avoiding expansions in depth of dead ends. I guess.
Stay safe and secure!