Reputation
755
Next privilege 1,000 Rep.
See votes, expandable usercard
Badges
5 9
Newest
 Critic
Impact
~12k people reached

  • 0 posts edited
  • 1 helpful flag
  • 11 votes cast
Feb
5
awarded  Critic
Feb
5
comment Why do “nothing up my sleeve numbers” have low entropy?
@PaulUszak H = -Σpᵢ log pᵢ is an exact formula the entropy of random strings generated with probabilities pᵢ. If you have many random strings generated with a total entropy of N bits, it will be impossible (in aggregate) to losslessly compress such data with less than N bits. This does mean that H is an estimate or upper bound on the entropy; it means this calculated entropy sets a lower-bound on the size of losslessly compressed data (in aggregate). Furthermore, 11.9 bits is not less than 7.3. See: en.wikipedia.org/wiki/…
Jan
25
awarded  Commentator
Jan
25
comment Why do “nothing up my sleeve numbers” have low entropy?
@PaulUszak - Simply generate say N=100,000 random 50 digit passwords and write them to a text file. Try any method of encoding or compression (that doesn't have knowledge of some phenomenon underlying the randomness of how the 50-digit passwords were generated; e.g., no access to PRNG seeds). If you can encode 100k such passwords in less than 166*N = 16,609,640 bits (about 2.07 MB), then you've shown it's an overestimate. As quick check, applying standard compression (which adds things like checksums), I can compress such a file to about 2.15 MB (bzip2) which is 172 bits/pw.
Jan
25
comment Why do “nothing up my sleeve numbers” have low entropy?
@PaulUszak - I never said Shannon entropy and Kolmogorov complexity are equivalent concepts, they aren't. I said they are related concepts (which they are see for example: en.wikipedia.org/wiki/Kolmogorov_complexity#Relation_to_entropy or homepages.cwi.nl/~paulv/papers/info.pdf or www-isl.stanford.edu/~cover/papers/transIT/0331leun.pdf ). Second, I have read Shannon's 1948 paper and see his theorem 2 defining entropy as H = -Σpᵢ log pᵢ . This isn't an approximation or upper bound and if it was a gross overestimate, prove it.
Jan
14
comment Why do “nothing up my sleeve numbers” have low entropy?
The formula for Shannon entropy is S = - Σ p_i log (p_i) where you iterate over all possibilities. E.g., if you have a 1 digit password where all 10 digits were chosen uniformly p_i = 1/10 for all i (from 0 to 9), then S = - 10 * (1/10 lg (1/10)) = lg 10 ~ 3.322. Similarly for 2-digit there are N=100 possibilities, each with prob p=1/100, so S = lg 100 = 2*lg 10 ~ 6.644. Thus, for 50 digit passwords, each password is chosen at p=10^-50 and there are 10^50 of them, so the Shannon entropy of generating a random 50 digit password is exactly S = 50*lg 10 (which is approximately 166.096).
Jan
14
comment Why do “nothing up my sleeve numbers” have low entropy?
@PaulUszak - If I need to send someone a trillion 0s, you don't say the entropy is a trillion bits. You merely agree on an appropriate compression scheme for that type of data, say a digit and how many times to repeat that digit. Then it ends up being under 100 bits (~40 to store a trillion, plus the digit (maybe 8 bit) to repeat and some overhead to indicate the compression scheme, separators, end of transmission). Similarly, if you needed to send the first digits of pi efficiently, you could use a compression scheme that transmits a formula for pi and the number of digits to calculate.
Dec
13
comment What is a good algorithm to scramble data in a 2-D grid
@JoshKurien By not particularly secure, I'm stating that if you have a scrambled message, it may be possible to unscramble it (by searching for valid english words and letter counts) as well as modify the scramble message. (E.g., if the message was ATTACK AT DUSK scrambled to CTA TSAK*K DATU* someone can put it in an anagram finder and decipher the message, figure out what permutations could have been used to recover the key (unique up to repeated letters) and then change the message.)
Dec
12
answered What is a good algorithm to scramble data in a 2-D grid
Dec
8
revised What is the lowest level of mathematics required in order to understand how encryption algorithms work?
Dead link.
Oct
25
revised Is md5(x)&md5(y&x) secure?
added 2 characters in body
Oct
25
revised Is md5(x)&md5(y&x) secure?
added 2 characters in body
Oct
24
answered Is md5(x)&md5(y&x) secure?
Jan
28
awarded  Yearling
Sep
24
awarded  Autobiographer
Jul
8
awarded  Good Answer
May
16
answered Why do “nothing up my sleeve numbers” have low entropy?
Apr
30
awarded  Citizen Patrol
Apr
28
revised x509 CA trust question
added 37 characters in body
Apr
28
answered x509 CA trust question