4 ms·

If primes derived from pi are not suspect, then that surely goes for primes derived from 1/pi, e, sqrt(2)... as well? What about bit order, byte order? The pro

by fdej 11y ago

If primes derived from pi are not suspect, then that surely goes for primes derived from 1/pi, e, sqrt(2)... as well? What about bit order, byte order? The problem is that there are lots of small choices involved in picking "nothing up my sleeve" numbers and deriving data from them. Each small choice may seem trivial in isolation, but taken together, the parameter space is so large that you can derive virtually anything from "nothing up my sleeve" numbers. Bernstein et al. made a point of exactly this in the paper https://bada55.cr.yp.to/bada55-20140722.pdf https://bada55.cr.yp.to/bada55-20140722.pdf by deriving the string "BADA55" from "nothing up my sleeve" numbers.

cperciva 11y ago
If primes derived from pi are not suspect, then that surely goes for primes derived from 1/pi, e, sqrt(2)... as well? If someone uses 1/pi, the first question they face is going to be "why not pi". If you need a series of values, sqrt(p) is reasonable, but if you're just looking for one value then using sqrt(17) is going to look suspicious. What about bit order, byte order? What about them? Primes don't have bit or byte orderings. They're just integers. If you say "I generated this prime by taking Pi, writing it as a series of bytes, permuting those bytes, and then interpreting those as an integer", people will be very suspicious.
- fdej 11y ago
  Check out the Wikipedia article https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number for some examples: ARIA uses 1/π (indeed, why not pi?) MD5 uses sin(n) (why not cos(n) or sqrt(n)?) SHA-1 and SHA-2 use square roots and cube roots of small primes (why not sin(n) or pi?) DFC uses e. NewDES uses the United States Declaration of Independence. RC5 uses both e and the golden ratio. BLAKE uses "a table of 16 constant words which are the leading 512 or 1024 bits of the fractional part of π". (Here you see how things like bit or byte order can give you more choices.)
  - deleted 11y ago
    [deleted]
tptacek 11y ago
But, come on. Here's the process they used: We begin with 17 natural constants: π, e, Euler gamma, √2, √3, √5, √7, log(2), (1 + √5)/2, ζ(3), ζ(5), sin(1), sin(2), cos(1), cos(2), tan(1), and tan(2). We extend this list by including reciprocals. We then convert to constants between 0 and 1 in three different ways: take the fractional part; divide by 256 and discard any minus sign; or take all bits starting from the most significant (i.e., divide by an appropriate power of 2), again discarding any minus sign. Removing duplicates produces 73 starting seeds. For the hash function, we are using the 10 variants of Keccak listed above. As length for each seed, we use either 20, 32, 48, 64, or 128 bytes, or the block size of the Keccak configuration (6 choices). The seed is either stored in big-endian or little-endian format (2 choices). In order to update the seed during the generation procedure, we are using a counter of length either 0 (i.e., the seed itself is incremented), 2, 3, 4, or 8 bytes (5 choices), either at the beginning or at the end of the seed (2 choices). We either truncate the seed to the right length or round it to the right length (2 choices); note that in many cases these are identical. Finally, we are using several different ways to update the counter between generation of a and b and to choose the order of generating a and b (8 choices). All in all, we have 73 · 10 · 6 · 2 · 5 · 2 · 2 · 8 = 1401600 possible configurations, mostly different, with a high probability to find a procedure that produces the desired vulnerability. They ended up using picky encoding of cos(1) and a counter that ticked 184 times, and they got a = 0x7144BA12CE8A0C3BEFA053EDBADA555A42391AC64F052376E041C7D4AF23195EBD 8D83625321D452E8A0C3BB0A048A26115704E45DCEB346A9F4BD9741D14D49. It's not like they simply got a=BADA55... from pi.
- fdej 11y ago
  There is so much variation in the methods that have already been used to derive "nothing up my sleeve" numbers that you could easily come up with 2^10 equally plausible methods. The 24 chosen bits for "BADA55" might be overkill; depending on the circumstances, being able to pick "A55" might be enough.
  - tptacek 11y ago
    I agree that the collection of all nothing-up-my-sleeve numbers anyone has ever used gives you a good starting point to find a 1/10000 curve flaw, but I'm not advocating for allowing cos(1), sqrt(2), 1/pi, &c. I'm saying: "use the leading digits of pi, or the first N digits that pass some security function if you need to be picky".

by fdej 11y ago

cperciva 11y ago

If primes derived from pi are not suspect, then that surely goes for primes derived from 1/pi, e, sqrt(2)... as well? If someone uses 1/pi, the first question they face is going to be "why not pi". If you need a series of values, sqrt(p) is reasonable, but if you're just looking for one value then using sqrt(17) is going to look suspicious. What about bit order, byte order? What about them? Primes don't have bit or byte orderings. They're just integers. If you say "I generated this prime by taking Pi, writing it as a series of bytes, permuting those bytes, and then interpreting those as an integer", people will be very suspicious.

fdej 11y ago
Check out the Wikipedia article https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number for some examples: ARIA uses 1/π (indeed, why not pi?) MD5 uses sin(n) (why not cos(n) or sqrt(n)?) SHA-1 and SHA-2 use square roots and cube roots of small primes (why not sin(n) or pi?) DFC uses e. NewDES uses the United States Declaration of Independence. RC5 uses both e and the golden ratio. BLAKE uses "a table of 16 constant words which are the leading 512 or 1024 bits of the fractional part of π". (Here you see how things like bit or byte order can give you more choices.)
- deleted 11y ago
  [deleted]

tptacek 11y ago

But, come on. Here's the process they used: We begin with 17 natural constants: π, e, Euler gamma, √2, √3, √5, √7, log(2), (1 + √5)/2, ζ(3), ζ(5), sin(1), sin(2), cos(1), cos(2), tan(1), and tan(2). We extend this list by including reciprocals. We then convert to constants between 0 and 1 in three different ways: take the fractional part; divide by 256 and discard any minus sign; or take all bits starting from the most significant (i.e., divide by an appropriate power of 2), again discarding any minus sign. Removing duplicates produces 73 starting seeds. For the hash function, we are using the 10 variants of Keccak listed above. As length for each seed, we use either 20, 32, 48, 64, or 128 bytes, or the block size of the Keccak configuration (6 choices). The seed is either stored in big-endian or little-endian format (2 choices). In order to update the seed during the generation procedure, we are using a counter of length either 0 (i.e., the seed itself is incremented), 2, 3, 4, or 8 bytes (5 choices), either at the beginning or at the end of the seed (2 choices). We either truncate the seed to the right length or round it to the right length (2 choices); note that in many cases these are identical. Finally, we are using several different ways to update the counter between generation of a and b and to choose the order of generating a and b (8 choices). All in all, we have 73 · 10 · 6 · 2 · 5 · 2 · 2 · 8 = 1401600 possible configurations, mostly different, with a high probability to find a procedure that produces the desired vulnerability. They ended up using picky encoding of cos(1) and a counter that ticked 184 times, and they got a = 0x7144BA12CE8A0C3BEFA053EDBADA555A42391AC64F052376E041C7D4AF23195EBD 8D83625321D452E8A0C3BB0A048A26115704E45DCEB346A9F4BD9741D14D49. It's not like they simply got a=BADA55... from pi.

fdej 11y ago
There is so much variation in the methods that have already been used to derive "nothing up my sleeve" numbers that you could easily come up with 2^10 equally plausible methods. The 24 chosen bits for "BADA55" might be overkill; depending on the circumstances, being able to pick "A55" might be enough.
- tptacek 11y ago
  I agree that the collection of all nothing-up-my-sleeve numbers anyone has ever used gives you a good starting point to find a 1/10000 curve flaw, but I'm not advocating for allowing cos(1), sqrt(2), 1/pi, &c. I'm saying: "use the leading digits of pi, or the first N digits that pass some security function if you need to be picky".