5 ms·

Sigh The issue here is that we need a trusted source of "nothing up my sleeve" numbers: https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number https://en.wi

Sigh The issue here is that we need a trusted source of "nothing up my sleeve" numbers: https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number This is why the RFC 3526 groups use primes derived from Pi: https://tools.ietf.org/html/rfc3526 https://tools.ietf.org/html/rfc3526 I'm sure that it would be difficult to tamper with the results of lotteries held all over the world. But it's even harder to tamper with the value of Pi.

baby 11y ago
Problem, pi is not unpredictable.
- cperciva 11y ago
  It doesn't need to be. The group you're using is part of the cryptosystem, not part of the key.
  - baby 11y ago
    And the cryptosystem might be backdoored by the way you choose the constants. (they are way too many constants to choose from)
    - tptacek 11y ago
      It really isn't backdoored, though. Bada55 made a legit point that curves shouldn't be required to derive from simple math constants, but it does less of a good job showing that math constants are themselves necessarily untrustworthy. You'd need an awfully funky looking set of constants to get the degree of freedom bada55 proposes.
    - cperciva 11y ago
      Right. Hence "nothing up my sleeve" numbers. It's hard to fit a backdoor into Pi.
      - baby 11y ago
        Why did you choose Pi? And not e? (see what I'm doing?)
        tptacek 11y ago
        Because pi is the simplest constant that has already been used as a magic constant in other cryptographic algorithms. Next question?
        baby 11y ago
        That's completely not true. Example sha-1: > The constant values used are chosen to be nothing up my sleeve numbers: the four round constants k are 230 times the square roots of 2, 3, 5 and 10. The first four starting values for h0 through h3 are the same with the MD5 algorithm, and the fifth (for h4) is similar.
        tptacek 11y ago
        230 times the square roots of 2, 3, 5 and 10 versus the first N digits of Pi, minus the leading 3 (what Blowfish used).
        baby 11y ago
        other examples: https://news.ycombinator.com/item?id=11161841 https://news.ycombinator.com/item?id=11161841
        tptacek 11y ago
        Look at the BLAKE example there: it's simply the leading digits of pi. The rest of the examples seem like they prove my point. 1/pi? sin(n)? First N primes? Cubes of first N primes? I agree! Super sketchy! Why would you use any of those? Just use pi.
        11y ago
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]
kevhito 11y ago
Sigh. This is incorrect. Pi does not give the "nothing up my sleveve" property, because if I have a desired bit sequence in mind, I can find it in Pi, then retroactively claim that because it comes from Pi it wasn't "up my sleeve". Specifically, the methodology of transforming the its of Pi into the desired key was "up my sleeve". What the authors propose here is much better. The methodology and protocol for transforming the seed digits is agreed to ("committed") ahead of time, before the digits are known, and only later are the numbers generated.
- tptacek 11y ago
  Isn't this circular reasoning? If you do that, you have another constant to justify: the offset into pi you used. Go find BADA55 in Pi, and relay back to us what the offset is.† You don't need lotteries to break this logjam. You just demand the minimal parameters that satisfy the security a/o performance considerations for your problem. LaMacchia and Costello did this for NUMS without even needing recourse to constants: they just start with the target security level, find the minimal prime for that security level, and then the minimal suitable (given, for instance, SafeCurves) d for an Edwards curve. † My friend Peter found it: http://pi.nersc.gov/cgi-bin/pi.cgi?word=BADA55&format=hex http://pi.nersc.gov/cgi-bin/pi.cgi?word=BADA55&format=hex --- so: justify the binary offset "2733181964". :)
- bradleyjg 11y ago
  The IETF (or whomever) could pre-specify a nothing up my sleeve number algorithm. For example they could choose Pi and say that the following are the official NUMSN for each order of magnitude: 1, 41, 592, 6535, 89793, 238462, 6433832, ... and if a number is needed with a specific property (e.g. 40 digits and prime) than the nearest number to a NUMSN is the official NUMSN for that purpose. Then any future standard that used a constant they claimed was a NUMSN but wasn't complaint with RFC 31415: Procedures of Generating Constants would be suspicious.
- cyphar 11y ago
  > Sigh. This is incorrect. Pi does not give the "nothing up my sleeve" property, because if I have a desired bit sequence in mind, I can find it in Pi, then retroactively claim that because it comes from Pi it wasn't "up my sleeve". Specifically, the methodology of transforming the its of Pi into the desired key was "up my sleeve". Pi has not been proven to be normal, so you can't be completely sure that you could always find any particularly long (backdoored) sequence.
deleted 11y ago
[deleted]
ris 11y ago
I suspect the reasoning is thus: Pi & friends are all well and good when all you're doing is filling out a few initial bitfield states in a pipeline, but when you're designing a highly complicated process by which to deterministically produce a safe but "random" curve, the process of designing that process itself is going to have some unjustified choices in it. The meta-algorithm, if you like, could have been designed to produce a specific result given the input pi. Publishing & rigidly defining the method before choosing the seed would seem to alleviate all possibility of foul play.
- semi-extrinsic 11y ago
  >Publishing & rigidly defining the method before choosing the seed would seem to alleviate all possibility of foul play. Except, how do you know the seed was not secretly chosen first? There are probably ways around that again, but this rabbit hole is deep.
  - ris 11y ago
    I can't imagine many things harder than secretly rigging >30 worldwide lotteries.
MCRed 11y ago
Could the selection of primes derived from Pi be optimized to find weaker ones vs. stronger ones? eg: calculate a very large set of them and then pick the ones that are weakest and then publish that as a standard (of course you wouldn't let on that you had chosen the weakest, you could pick an arbitrary function that gets you the weak ones which would then look really good because pi is objective and that function is objective.)

baby 11y ago

Problem, pi is not unpredictable.

cperciva 11y ago
It doesn't need to be. The group you're using is part of the cryptosystem, not part of the key.
- baby 11y ago
  And the cryptosystem might be backdoored by the way you choose the constants. (they are way too many constants to choose from)
  - tptacek 11y ago
    It really isn't backdoored, though. Bada55 made a legit point that curves shouldn't be required to derive from simple math constants, but it does less of a good job showing that math constants are themselves necessarily untrustworthy. You'd need an awfully funky looking set of constants to get the degree of freedom bada55 proposes.
  - cperciva 11y ago
    Right. Hence "nothing up my sleeve" numbers. It's hard to fit a backdoor into Pi.
    - baby 11y ago
      Why did you choose Pi? And not e? (see what I'm doing?)
      - tptacek 11y ago
        Because pi is the simplest constant that has already been used as a magic constant in other cryptographic algorithms. Next question?
        baby 11y ago
        That's completely not true. Example sha-1: > The constant values used are chosen to be nothing up my sleeve numbers: the four round constants k are 230 times the square roots of 2, 3, 5 and 10. The first four starting values for h0 through h3 are the same with the MD5 algorithm, and the fifth (for h4) is similar.
        tptacek 11y ago
        230 times the square roots of 2, 3, 5 and 10 versus the first N digits of Pi, minus the leading 3 (what Blowfish used).
        baby 11y ago
        other examples: https://news.ycombinator.com/item?id=11161841 https://news.ycombinator.com/item?id=11161841
        tptacek 11y ago
        Look at the BLAKE example there: it's simply the leading digits of pi. The rest of the examples seem like they prove my point. 1/pi? sin(n)? First N primes? Cubes of first N primes? I agree! Super sketchy! Why would you use any of those? Just use pi.
        11y ago

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]

kevhito 11y ago

Sigh. This is incorrect. Pi does not give the "nothing up my sleveve" property, because if I have a desired bit sequence in mind, I can find it in Pi, then retroactively claim that because it comes from Pi it wasn't "up my sleeve". Specifically, the methodology of transforming the its of Pi into the desired key was "up my sleeve". What the authors propose here is much better. The methodology and protocol for transforming the seed digits is agreed to ("committed") ahead of time, before the digits are known, and only later are the numbers generated.

tptacek 11y ago
Isn't this circular reasoning? If you do that, you have another constant to justify: the offset into pi you used. Go find BADA55 in Pi, and relay back to us what the offset is.† You don't need lotteries to break this logjam. You just demand the minimal parameters that satisfy the security a/o performance considerations for your problem. LaMacchia and Costello did this for NUMS without even needing recourse to constants: they just start with the target security level, find the minimal prime for that security level, and then the minimal suitable (given, for instance, SafeCurves) d for an Edwards curve. † My friend Peter found it: http://pi.nersc.gov/cgi-bin/pi.cgi?word=BADA55&format=hex http://pi.nersc.gov/cgi-bin/pi.cgi?word=BADA55&format=hex --- so: justify the binary offset "2733181964". :)
bradleyjg 11y ago
The IETF (or whomever) could pre-specify a nothing up my sleeve number algorithm. For example they could choose Pi and say that the following are the official NUMSN for each order of magnitude: 1, 41, 592, 6535, 89793, 238462, 6433832, ... and if a number is needed with a specific property (e.g. 40 digits and prime) than the nearest number to a NUMSN is the official NUMSN for that purpose. Then any future standard that used a constant they claimed was a NUMSN but wasn't complaint with RFC 31415: Procedures of Generating Constants would be suspicious.
cyphar 11y ago
> Sigh. This is incorrect. Pi does not give the "nothing up my sleeve" property, because if I have a desired bit sequence in mind, I can find it in Pi, then retroactively claim that because it comes from Pi it wasn't "up my sleeve". Specifically, the methodology of transforming the its of Pi into the desired key was "up my sleeve". Pi has not been proven to be normal, so you can't be completely sure that you could always find any particularly long (backdoored) sequence.

deleted 11y ago

[deleted]

ris 11y ago

I suspect the reasoning is thus: Pi & friends are all well and good when all you're doing is filling out a few initial bitfield states in a pipeline, but when you're designing a highly complicated process by which to deterministically produce a safe but "random" curve, the process of designing that process itself is going to have some unjustified choices in it. The meta-algorithm, if you like, could have been designed to produce a specific result given the input pi. Publishing & rigidly defining the method before choosing the seed would seem to alleviate all possibility of foul play.

semi-extrinsic 11y ago
>Publishing & rigidly defining the method before choosing the seed would seem to alleviate all possibility of foul play. Except, how do you know the seed was not secretly chosen first? There are probably ways around that again, but this rabbit hole is deep.
- ris 11y ago
  I can't imagine many things harder than secretly rigging >30 worldwide lotteries.

MCRed 11y ago

Could the selection of primes derived from Pi be optimized to find weaker ones vs. stronger ones? eg: calculate a very large set of them and then pick the ones that are weakest and then publish that as a standard (of course you wouldn't let on that you had chosen the weakest, you could pick an arbitrary function that gets you the weak ones which would then look really good because pi is objective and that function is objective.)