Subject: Some entropy calculations with secret/huffman interaction

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 27 Nov 2013 12:40:14 +0200

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

---

From: Martin Thomson <[email-masked]>
Date: Wed, 27 Nov 2013 09:08:04 -0800

On 27 November 2013 02:40, Ilari Liusvaara <[email-masked]> wrote:
> The secret

Have we worked out yet how to determine if something is secret or not
algorithmically?

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 27 Nov 2013 21:00:48 +0200

> Have we worked out yet how to determine if something is secret or not

No, I just wanted to calculate how bad the entropy loss is.

Also, doing Huffman on anything that looks like base64 probably isn't a good
idea.

Hexadecimal stuff (escpecially with lowercase a-f) does compress
(average ~30%; Hmm... I wonder how badly those leak...).

-Ilari

---

From: Roberto Peon <[email-masked]>
Date: Wed, 27 Nov 2013 11:20:39 -0800

The paper I linked to some time ago has one analysis of this.
-=R