Ron was wrong, Whit is right

benfdc
benfdc
Community Member
I'm wondering how much 1Password users need to be concerned about the PRNG issues raised by the recent paper by Lenstra, Hughes, et al.

Comments

  • jpgoldberg
    jpgoldberg
    1Password Alumni
    Hi Ben,

    The short answer is that 1Password users have nothing to worry about. We follow best practices in getting our random numbers:

    random_number.png



    More seriously, since that paper came out, I started drafting a document describing the process, but it's not ready for public consumption yet. Anyway, we do use appropriate CSPRNGs (Cryptographically Secure Pseudo-random Number Generator) that are seeded (indirectly) through /dev/random.

    Now that that's out of the way, I'd like to point out that nobody needs to worry about what that paper reported. For those who don't know, a recent paper claimed that up to 2% of website site certificates are broken, and provide poor security.

    In sum there were three things that they said
    1. Lot's of certificates have RSA moduli that are less than 1024 bits (and so breakable using feasible attacks today)
    2. Lots of component primes were generated with broken PRNGs, and there are actual collisions among moduli out there
    3. RSA is inherently more vulnerable to the second problem than discrete logarithms or elliptical curves.

    Now their argument for point 3 is just silly. I spent a lot of time trying to make sense of it, as did others. It just doesn't fly. Also their point 3 is where they get their dramatic title "Ron was wrong, Whit was right".

    But let's look at 2, as that is where the most legitimate concern is. It turns out that when they shared their data with other researchers, a look at it showed that all of the bad public/private key pairs where on test, non-functional certificates anyway. That is, it turned out that all of the weak or broken certificates were things like self-signed certificates anyway. That is, they were not being used in ways in which there is any expectation that they would be trusted in the first place.

    Please take a look at Dan Kaminisky's summary, after he had a chance to study the original data.

    http://dankaminsky.c.../17/primalfear/

    The whole thing is a non-issue.

    This is not to say that there aren't serious problems with the trust models used for key authentication. But the particular paper muddies the discussion instead of shedding light on it.

    Cheers,

    -j
  • benfdc
    benfdc
    Community Member
    Well, the part about it being easy to break two RSA keys if you know that they share one modulus was certainly attention-getting.

    My main take-away from the reporting on that paper was that problems can arise when a PRNG is not seeded with sufficient entropy. This feeds into something that I have absolutely no feel for. I need to generate a password. I have three sliders--length, number of symbols, and number of numbers. I slide them around until I'm happy, while watching a dozen or more candidate passwords flash before my eyes.

    Is 1Password dipping into /dev/random (or CryptGenRandom or the like on 1P/Win) repeatedly during this process? If it is, have I just materially depleted the system entropy pool? How would I know? And would there be any practical implications whatsoever?
  • jpgoldberg
    jpgoldberg
    1Password Alumni
    The short answer is that the rate at which we pull random numbers from system tools doesn't make a dent in the system's ability to provide quality randomness.

    Ultimately the source is /dev/random, but it is managed through higher level tools.

    Because the entropy that you get from physical measures contain substantial biases, /dev/random isn't just a collection of those measures. What it actually does is hash those measures (along with the output of /dev/random) to create internal entropy pools. Data from those pools are then used to seed a cryptographically secure PRNG. Reseeding takes place at least once every half second.

    You would have to pull bits from /dev/random extremely quickly to ever worry about running it down. It only becomes an issue for people running statistical simulations, who need enormous amounts of statistically random numbers very quickly. Fortunately, those applications only require that the data meet certain statistical properties, but not need cryptographic security (unpredictability), so they can just seed a high quality PRNG without needed to slurp much from /dev/random.

    Cheers,

    -j
  • benfdc
    benfdc
    Community Member
    Thanks for the explanation, Jeff. But I'm still not clear on what happens when I'm generating a password and hit the refresh button to see a different suggestion. Is it deterministic (just turning a PRNG one more crank) or not? My process for generating a diceware-style passphrase with 1Password involves using the refresh button to "re-roll the dice" for the next word. If those rolls are not fully independent, then my passphrases may not be as strong as they seem.

    If (when?) a passphrase generator is added to 1Password, this particular concern will become moot, but I'd still be curious.
  • jpgoldberg
    jpgoldberg
    1Password Alumni
    Ben,

    You are asking the wrong question. The question "is it a deterministic sequences" has the answer "if you are drawing few then thousands of bits per second it is entirely non-deterministic, but if you are drawing faster then some small portions of the sequence may be kinda-sorta deterministic, but still fully appropriate for all cryptographic purposes."

    The question "is the randomness I get from 1Password's password generator secure enough to drive diceware password generation" then the answer is "yes, the randomness is more than adequate assuming that you appropriately address the fact that you are just getting strings".

    Really, you shouldn't be using the 1Password generator as you do. It's entropy is fine, but you are making things too complicated and you have a real chance of introducing error in your process of using the strings (not random numbers) that the Generator produces as inputs to something else.

    A great Diceware generator is available at xkpasswd.net. Obviously you don't want to use a tool online, but from there you can download the perl module used for this.

    If you simply want to get, say, 8 bytes of randomness on your Mac, just use the command

    openssl rand -hex 8
    


    in a Terminal window. That will give hexadecimal output. Suppose you get

    337a1597247a0d33

    To convert that to decimal you would use

    printf '%d\n' 0x337a1597247a0d33
    


    (Note that you have to add the '0x' before the number).

    That will get you

    3709300981989248307

    Note that the leading digit of that number will not be uniformly distributed between 1 and 9.

    Ben, I think it is great that you want to explore these kinds of things and tinker with them. But if you are really concerned about doing it right, don't roll your own. If your goal is to simply have fun with this stuff, then by all means continue.

    Cheers,

    -j
  • benfdc
    benfdc
    Community Member
    Jeff—

    I am a tinkerer, but I use the tools I know. Thanks for pointing me to openssl.

    I don't like your suggestion of converting hex to dec, though. I have a gut sense that none of the digits in a hex > dec conversion (or a hex > base 6 conversion, which strikes me as more logical than hex > dec) will be uniformly distributed. More physical constants start with a 1 than a 2, more start with a 2 than a 3, etc. The bias is most pronounced for the most significant digit, but it extends all the way down. It's a logarithm thing.

    I'm sure there's a rule of thumb for how many leading digits one has to throw away before this bias can be safely ignored, but I don't know it, and I'd rather just avoid the issue.

    Seems to me that one could could derive an unbiased series of "dice rolls" from [font=courier new,courier,monospace]openssl rand -hex n[/font] by converting the output string to octal and then tossing all zeros and sevens. Unless [font=courier new,courier,monospace]n[/font] were divisible by 3, you'd also have to toss the most significant octal digit.

    If one were to discard the dice metaphor and define the objective as randomly picking one word out of Reinhold's word list, just take 13 bits of output from openssl and toss any "roll" higher than 7,775.

    But if I were designing a diceware-ish passphrase generator for 1Password, I'd probably dig around for a suitable list of 8,192 words.

    Wouldn't you? :wink:

    —Ben
  • jpgoldberg
    jpgoldberg
    1Password Alumni
    edited February 2012
    benfdc wrote:

    I am a tinkerer, but I use the tools I know.

    That's great, Ben. Just as long as you know that you will be limited by the fact that you are not always using the appropriate tool for the job.


    I don't like your suggestion of converting hex to dec, though. I have a gut sense that none of the digits in a hex > dec conversion (or a hex > base 6 conversion, which strikes me as more logical than hex > dec) will be uniformly distributed.

    The base (and conversion between them) has doing to do with my point about the leading digit.


    More physical constants start with a 1 than a 2, more start with a 2 than a 3, etc. The bias is most pronounced for the most significant digit, but it extends all the way down. It's a logarithm thing.

    Benford's law was not the issue. My point about the leading digit was that the numbers that we would get would be uniformly drawn from 0 to 264 or 0 to 18446744073709551616. The leading digit of that will always be 0 or 1 if you keep to all of the significant digits.

    If one were to discard the dice metaphor and define the objective as randomly picking one word out of Reinhold's word list, just take 13 bits of output from openssl and toss any "roll" higher than 7,775.

    Yes. Note that this utility requires that you specify a number of bytes, so you would have to grab 16 bits, but that is the correct approach.

    But if I were designing a diceware-ish passphrase generator for 1Password, I'd probably dig around for a suitable list of 8,192 words.

    Wouldn't you?

    Yep!

    Cheers,

    -j
  • benfdc
    benfdc
    Community Member
    BTW, I can see how massaging octal digits out of openssl, or rolling actual dice and recording the results with pencil and paper, would be a more pure process than generating number sequences in 1Password. I can also see how either of those methods would have more geek cred. However, using 1Password strikes me as the least error-prone of the three, as well as the most convenient. Especially with the following refinement: create a pass phrase in a new login record rather than a new password record, saving after each roll. Now the rolls are recorded as password history!

    Ease-of-use contributes to security, and 1Password has ease-of-use in spades.

    The only advantage that I can see the perl module contributing would be automated word-lookup. If I were tasked with generating a whole batch of pass phrases at once, it might make sense. But I don't think I make a dozen in a year. I'm inclined to stick with 1Password.

    But I really do appreciate your insights, Jeff. Thanks!

    —Ben
  • benfdc
    benfdc
    Community Member
    jpgoldberg wrote:

    That's great, Ben. Just as long as you know that you will be limited by the fact that you are not always using the appropriate tool for the job.


    I guess I still don't grasp why it is that 1Password would not be an appropriate tool for generating random digits.

    jpgoldberg wrote:

    Benford's law was not the issue. My point about the leading digit was that the numbers that we would get would be uniformly drawn from 0 to 264 or 0 to 18446744073709551616. The leading digit of that will always be 0 or 1 if you keep to all of the significant digits.



    And my point is that the second digit in your conversion of 264 to base ten is twice as likely to be a 7 as it is a 9, that the third digit is somewhat more likely to be a 3 than a 5, and so on. I think of it as a quantized form of Benford's law.

    Converting from hex to octal won't produce this sort of bias.
  • jpgoldberg
    jpgoldberg
    1Password Alumni
    Ah. I didn't understand how you were using the strong password generator.

    If you are using the generated passwords as parts of a diceware-like scheme, then instead of generating four or five separate passwords, why don't you just generate one really long one and break it up into pieces? Or have I continued to misunderstand your process?

    Cheers,

    -j
  • benfdc
    benfdc
    Community Member
    jpgoldberg wrote:

    If you are using the generated passwords as parts of a diceware-like scheme, then instead of generating four or five separate passwords, why don't you just generate one really long one and break it up into pieces? Or have I continued to misunderstand your process?

    -j


    The digit slider on 1Password's random password generator tops out at ten, so one can get at most ten digits per roll. Checking the "avoid ambiguous characters" box knocks out three of the ten possible digits, but occurrences of a fourth must be manually discarded (I toss eights) in order to map the generator's output to the faces of a six-sided die. Four random ten-digit strings will usually yield six or seven diceware words.

    Lookup is easy b/c I saved Reinhold's word list into Evernote. Typing a five digit sequence into Evernote's search box invariably pulls up the corresponding diceware word.
This discussion has been closed.