Some entropy calculations with secret/huffman interaction

While listening to the WG session, I got an idea to do this...

Assume the attacker knows the following:
- The secret is uniformly distributed octet string.
- The secret is base64url-encoded into header value.
- The length of the secret in bits.
- The length of resulting huffman encoding in bytes.

How many bits of entropy remain for each possible length?

And what is the averaged entropy over all possible
lengths?

64-bit secret (Request):
------------------------
6 20.19199414876733680059
7 46.64687948661354493108
8 56.98749885866029244623
9 61.62744539464671025493
10 63.11088950960139590728
11 61.96163192011884967139
12 58.00645476643778783231
13 50.08191234017700498867
14 31.72385276787911739505
avg 62.41617665246761276074

96-bit secret (Request):
------------------------
8 0
9 44.13485786373522027127
10 68.53494233127694582611
11 81.46289060476724156858
12 88.68374787727161740325
13 92.80990956641200973535
14 94.68243670426483876908
15 94.60658941811714050151
16 92.62578083741492859466
17 88.55608502811716360606
18 81.84863177996826480793
19 70.90855908719015663547
20 50.49943652753935948242
avg 94.17596215534539775585

Note: There's only one 8-byte compression, for string
consisting of 16 'e's.

128-bit secret (Request):
-------------------------
12 39.24760525294356461825
13 72.36635733141138826241
14 93.83063265080035244246
15 106.99704327892100181563
16 115.40268444963343608531
17 120.96789306025790780244
18 124.48316671185992862539
19 126.31430167922088654207
20 126.63326624963038811830
21 125.49592484637583818895
22 122.86417302644117017288
23 118.59391023860229590905
24 112.37641517399136181542
25 103.56131881436399992515
26 90.56280817542185283740
27 69.60773708452847347604
28 34.56122826925156588889
avg 125.98134545302275936204

192-bit secret (Request):
-------------------------
16 0
17 53.27390608497442209818
18 90.21884025554900115031
19 118.22568594025898781136
20 139.04992869034866173956
21 154.07291714234402380153
22 164.98972999307377676821
23 173.14756366881205246836
24 179.31264972985656454647
25 183.90846914044925573221
26 187.18275955653481940082
27 189.28597553275778298635
28 190.30840755854392152048
29 190.29840479627394145797
30 189.27093297810558068441
31 187.21013746686075248281
32 184.06687115621718176771
33 179.75011709887259614484
34 174.10838742951329359975
35 166.89102448967177051771
36 157.66342615287204550702
37 145.61242341055086377325
38 129.20850137239770245427
39 106.30185641456871887076
40 74.30190985468164778700
avg 189.71722420573498562585

Note: There's only one 16-byte compression, for string
consisting of 32 'e's.

256-bit secret (Request):
-------------------------
22 26.62623406867115985455
23 75.24455393018717917564
24 112.97485118960713429124
25 143.53464656495924463874
26 168.19642503396674329760
27 187.73375374615690321216
28 202.98942874617603758340
29 214.95573318836056461829
30 224.49495569975378624123
31 232.19442795108241487594
32 238.42712793212867401140
33 243.43380246659473218080
34 247.37505181725880048886
35 250.36074462664965862383
36 252.46670304479018073063
37 253.74441466305609761385
38 254.22676743874394456788
39 253.93135420109401669971
40 252.86213578238779774817
41 251.00982335680046760592
42 248.35105160569217751667
43 244.84615074448345570392
44 240.43498501382835196105
45 235.02975836671933268173
46 228.50260170247030540265
47 220.66352120024634627821
48 211.21967879037224681807
49 199.69939327789813417985
50 185.33051515859057654154
51 166.97813444077957017478
52 143.34442038220903677290
53 112.92608887404534205090
54 72.47203276851982724139
avg 253.51659533736393818417

64-bit secret (Response):
-------------------------
6 31.17739724066724275526
7 47.69594155139853796444
8 56.56700508508883597328
9 61.28007857904726594657
10 63.05146386483452092857
11 62.25257456258461322994
12 58.74712123321996075861
13 51.72459252101838882225
14 38.14998274071737581893
avg 62.39177895991127005015

96-bit secret (Response):
-------------------------
8 25.35940001153849890351
9 54.53081228438279450676
10 70.72524658674308599044
11 81.22325575127362330322
12 88.10415885704045856129
13 92.36834223552776813657
14 94.50659180258895757484
15 94.73603503142225861131
16 93.08858326164795642692
17 89.41917596294113781261
18 83.32923785828014983835
19 73.87751486496902136802
20 58.44772131121954073996
avg 94.15892289608697415737

128-bit secret (Response):
--------------------------
12 56.91742078188564780885
13 79.34898558417476154394
14 94.73917181610500710377
15 105.83159432255150526060
16 113.90275540182879686272
17 119.67988813049831311718
18 123.58825448870190853971
19 125.87519791880246100073
20 126.67458209898304559114
21 126.03745006161372642498
22 123.94241087960705248819
23 120.28956341989485108666
24 114.87232169455939965885
25 107.30424457664655806432
26 96.82663938430911089206
27 81.73946813365123420407
28 57.35173294251805985563
avg 125.96431034754263079378

192-bit secret (Response):
--------------------------
16 50.71880002307699780703
17 87.43281764927647509802
18 111.18634820118630939943
19 129.34471218987789047948
20 143.74970363094778748529
21 155.33755339718680826233
22 164.70153690195775073547
23 172.24712986531009603432
24 178.25685792586364862991
25 182.92842101338372777915
26 186.39972986024000366793
27 188.76522077219704003909
28 190.08614638645303833725
29 190.39670763399982095676
30 189.70717316837163753112
31 188.00452631463879336851
32 185.25062720874983750491
33 181.37723867758741521605
34 176.27627887529340240688
35 169.78178631375195185988
36 161.63604378578463465853
37 151.42309227026754211667
38 138.43215381692567597079
39 121.36872971786442061668
40 97.60080050140538539915
avg 189.69928944779795605977

256-bit secret (Response):
--------------------------
22 89.47543298038626555663
23 120.82057943200163430790
24 144.60775937183319344888
25 163.97282821139411706145
26 180.14835455674487005719
27 193.82395989171599480693
28 205.45647612825914157937
29 215.37567721149624069934
30 223.82881395236964666717
31 231.00393256886544251728
32 237.04479799724335334578
33 242.06150453788937175145
34 246.13822036934838335990
35 249.33880828300835824580
36 251.71084508429990525055
37 253.28843443068675006230
38 254.09410042249522170062
39 254.13995620509346490306
40 253.42826203472357432991
41 251.95141565003066865580
42 249.69134582760540114427
43 246.61819522472314168149
44 242.68806167161322643845
45 237.83938488691874129331
46 231.98725755549020599686
47 225.01439042875855213762
48 216.75644886664734279399
49 206.97759250096002726307
50 195.32861711009197218334
51 181.27413155442507341267
52 163.96222932785561437240
53 141.94292369305944072722
54 112.09631973433562325173
avg 253.49609310025203086168


(Also, this shows that trying to huffman sectret tokens is a bad idea,
for reasons unrelated to security).

-Ilari

Received on Wednesday, 27 November 2013 10:40:47 UTC