Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] Re: ...factorizer to break RSA...

Expand Messages
  • Paul Leyland
    ... Easier said than done. First, you have to get Arjen s database. Once you have it, finding factors through GCDs is a non-trivial task. That is the limit
    Message 1 of 18 , Feb 15, 2012
    View Source
    • 0 Attachment
      On Wed, 2012-02-15 at 02:26 +0000, djbroadhurst wrote:
      >
      > --- In primenumbers@yahoogroups.com,
      > "WarrenS" <warren.wds@...> wrote:
      >
      > > http://eprint.iacr.org/2012/064.pdf
      >
      > "among the 4.7 million distinct 1024-bit RSA
      > moduli that we had originally collected, more
      > than 12500 have a single prime factor in common"
      >
      > Hint to hackers: take GCDs with Arjen's database.

      Easier said than done. First, you have to get Arjen's database. Once
      you have it, finding factors through GCDs is a non-trivial task. That
      is the limit to the help which I am prepared to give.

      In case you haven't already done so, read the Acknowledgements
      paragraph.

      Paul
    • Phil Carmody
      ... Presumably you get it from the same places that Arjen got it? ... I think I can do it in about the cost of about a dozen half-gigabyte GCDs. Looking at
      Message 2 of 18 , Feb 15, 2012
      View Source
      • 0 Attachment
        --- On Wed, 2/15/12, Paul Leyland <paul@...> wrote:
        > On Wed, 2012-02-15 at 02:26 +0000, djbroadhurst wrote:
        > > --- In primenumbers@yahoogroups.com,
        > > "WarrenS" <warren.wds@...> wrote:
        > > >  http://eprint.iacr.org/2012/064.pdf
        > >
        > > "among the 4.7 million distinct 1024-bit RSA
        > > moduli that we had originally collected, more
        > > than 12500 have a single prime factor in common"
        > >
        > > Hint to hackers: take GCDs with Arjen's database.
        >
        > Easier said than done.  First, you have to get Arjen's database.

        Presumably you get it from the same places that Arjen got it?

        > Once you have it, finding factors through GCDs is a non-trivial
        > task.  That is the limit to the help which I am prepared to give.

        I think I can do it in about the cost of about a dozen half-gigabyte GCDs.
        Looking at some GMP benchmarks and extrapolating, that should be doable in way less than a day. I wouldn't be surprised if DJB (the UIUC one, not the Open one) didn't document such an algorithm some time in the nineties or noughties, as it's very close to some of the other combine-and-conquer techniques he was looking at.

        > In case you haven't already done so, read the Acknowledgements
        > paragraph.

        Yeah, I spotted that, and was about to drop you a private email as I was intrested in what the title of the paper referred to. So I'll do that here and now instead!

        Phil
      • Paul Leyland
        ... That s one way. It s also consistent with my statement that it s easier said than done. ... If you think you can do it, you can easily verify whether you
        Message 3 of 18 , Feb 15, 2012
        View Source
        • 0 Attachment
          On Wed, 2012-02-15 at 15:09 +0000, Phil Carmody wrote:
          > > Easier said than done. First, you have to get Arjen's database.
          >
          > Presumably you get it from the same places that Arjen got it?

          That's one way. It's also consistent with my statement that it's easier
          said than done.

          > > Once you have it, finding factors through GCDs is a non-trivial
          > > task. That is the limit to the help which I am prepared to give.
          >
          > I think I can do it in about the cost of about a dozen half-gigabyte
          > GCDs.

          If you think you can do it, you can easily verify whether you can do it
          in practice. The paper gives statistics on how many keys were found,
          the distribution of key lengths and the distribution of keys which share
          at least one prime. A few hours with a good random number generator
          should enable you to produce a synthetic data set with the same
          properties as the keys found in the wild. Once you've got your data go
          ahead and find the factorizations, then report back on how hard it was.

          Paul
        • djbroadhurst
          ... I suggest that Ron = R.L. Rivest Whit = W. Diffie but I am not sure if they had a direct argument? David
          Message 4 of 18 , Feb 15, 2012
          View Source
          • 0 Attachment
            --- In primenumbers@yahoogroups.com,
            Phil Carmody <thefatphil@...> wrote:

            > I was interested in what the title of the paper referred to

            I suggest that
            Ron = R.L. Rivest
            Whit = W. Diffie
            but I am not sure if they had a direct argument?

            David
          • djbroadhurst
            ... R[SA] is not keen on D[H], but more relaxed about D[VW]: http://www.rsa.com/rsalabs/node.asp?id=2248 ... or Station-to-Station (STS) protocol, was
            Message 5 of 18 , Feb 15, 2012
            View Source
            • 0 Attachment
              --- In primenumbers@yahoogroups.com,
              "djbroadhurst" <d.broadhurst@...> wrote:

              > > I was interested in what the title of the paper referred to
              > I suggest that
              > Ron = R.L. Rivest
              > Whit = W. Diffie
              > but I am not sure if they had a direct argument?

              R[SA] is not keen on D[H], but more relaxed about D[VW]:

              http://www.rsa.com/rsalabs/node.asp?id=2248

              >> The authenticated Diffie-Hellman key agreement protocol,
              or Station-to-Station (STS) protocol, was developed by
              Diffie, van Oorschot, and Wiener in 1992 [DVW92] to
              defeat the man-in-the-middle attack on the
              Diffie-Hellman key agreement protocol.<<

              David
            • djbroadhurst
              ... https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0503&L=nmbrthry&P=R684 give a lot a help, by publicly certifying semi-primality. Might Paul care to try to
              Message 6 of 18 , Feb 15, 2012
              View Source
              • 0 Attachment
                --- In primenumbers@yahoogroups.com,
                Paul Leyland <paul@...> wrote:

                > That is the limit to the help which I am prepared to give.

                https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0503&L=nmbrthry&P=R684
                give a lot a help, by publicly certifying semi-primality.
                Might Paul care to try to use that help to determine the factors?

                David (who never encrypts, as a matter of firm principle)

                "He who receives an idea from me, receives instruction
                himself without lessening mine; as he who lights his
                taper at mine, receives light without darkening me."
                Thomas Jefferson (1743-1826)
              • Phil Carmody
                ... All hail the great godess Obscurity, saving the day once again! ... Well, I don t have a machine with multiple gigabytes of RAM, which would be necessary
                Message 7 of 18 , Feb 15, 2012
                View Source
                • 0 Attachment
                  --- On Wed, 2/15/12, Paul Leyland <paul@...> wrote:
                  > Phil Carmody wrote:
                  > > > Easier said than done.  First, you have to get Arjen's database.
                  > >
                  > > Presumably you get it from the same places that Arjen got it?
                  >
                  > That's one way.  It's also consistent with my statement
                  > that it's easier said than done.

                  All hail the great godess Obscurity, saving the day once again!

                  > > > Once you have it, finding factors through GCDs is a non-trivial
                  > > > task.  That is the limit to the help which I am prepared to give.
                  > >
                  > > I think I can do it in about the cost of about a dozen half-gigabyte
                  > > GCDs.
                  >
                  > If you think you can do it, you can easily verify whether you can do it
                  > in practice.  The paper gives statistics on how many keys were found,
                  > the distribution of key lengths and the distribution of keys which share
                  > at least one prime. A few hours with a good random number generator
                  > should enable you to produce a synthetic data set with the same
                  > properties as the keys found in the wild.  Once you've got your data go
                  > ahead and find the factorizations, then report back on how hard it was.

                  Well, I don't have a machine with multiple gigabytes of RAM, which would be necessary for the GCDs I have in mind. But what's wrong with just modelling the problem?

                  Do you agree that if the number of keys massively dominates the number of common factors, that the amount of work once you have the product of all common factors is negligible compared to the work required to generate the product of all common factors?

                  The algorithm I have in mind is asymptotically faster than the following, but this is trivial. Do agree that this finds the product of all common primes:

                  Number all keys K_0 .. K_{N-1}
                  For b in [0..ceil(lg(N))]
                  Build products L and R such that
                  L = prod {i=0..N-1} (K_i if i has bit b set, else 1)
                  R = ditto, test flipped
                  Compute G_b = GCD(L, R).

                  Asymptotically, the GCD and the multiplications should be similar in cost,
                  and the arguments are large enough that deviations from the asyptotes are relatively minor.

                  Pari/GP on this old crate can do GCDs as follows.
                  1M digits 6.5s
                  2M digits 15.5s (factor ~2.4)
                  4M digits 37.2s (factor ~2.35)
                  8M digits 98.3s (factor ~2.32)
                  16M digits 205s (factor ~2.3)
                  Assuming pessimistically that the exponent is 2.3, that can be extrapolated (we're already out of L3, so there shouldn't be any surprising jumps) to 30000s for a gigadigit GCD.

                  The tree multiplication can similarly be done in approximately (I calculated the time for 1 layer, and multiplied by the depth. Asuming you code for the non-linear access times of the memory heirarchy, this is a clear over-estimate.)
                  1M digits 8s
                  2M digits 18.9s (factor ~2.36)
                  4M digits 44.2s (factor ~2.34)
                  8M digits 99s (factor ~2.24)
                  16M digits 218s (factor ~2.2)
                  Assuming again pessimisatically that the exponent is 2.2, extrapolation again gives us about 24000s for gigadigit product generation.

                  That's clearly less than a day per bit, and there are probably machines which are between 5 and 10 times faster than this machine. I think also that the George's GIMPS bignum library would dominate GMP for most of the operations. So this phase (generating the product of all and only duplicated factors) is no more than 3 days work on a single core. And of course the above is embarassingly parallel.

                  And that's the "naive" version of what I have in mind. Some of the multiplcations are redundant, for example, and with only a small constant memory increase (add another gig for this size problem) would reduce the mul cost by a factor of 2. A bit more RAM, and the stage after this, extracting the individual factors and identifying which key they come from becomes trivial, cheaper than one 'b' step above.

                  Are there any estimations above that you disagree with? (Or do you think any two keys are not getting GCD-ed with each other in the above process?)

                  And is the title of the paper also shrouded in obscurity that you're sworn not to reveal, or was that just an oversight in your attempt to swiftly assert that the algorithm I hadn't even yet told you about could never work? Does it just refer to the fact that the *R*SA with multiple prime secrets is "wrong" compared the single prime secred of *D*H?

                  Phil
                • djbroadhurst
                  ... Paul Leyland quite correctly remarked that Arjen s database is private. However, the GCD idea seems to work OK:
                  Message 8 of 18 , Feb 15, 2012
                  View Source
                  • 0 Attachment
                    --- In primenumbers@yahoogroups.com,
                    "djbroadhurst" <d.broadhurst@...> wrote:

                    > Hint to hackers: take GCDs with Arjen's database.

                    Paul Leyland quite correctly remarked that Arjen's database
                    is private. However, the GCD idea seems to work OK:

                    https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs

                    > We were able to factor 0.4% of the RSA keys in our SSL scan.
                    > We did this by computing the greatest common divisor (GCD) of
                    > all pairs of moduli from RSA public keys on the Internet.
                    > We identified 1724 common factors which allowed us to factor
                    > 24,816 SSL keys, and 301 common factors which allowed us to
                    > factor 2422 SSH host keys.

                    David (with thanks to Peter Kosinar, for the info)
                  • Paul Leyland
                    ... Two things. 1) Never ascribe to malice that which is adequately explained by incompetence. 2) I never said your algorithm couldn t work, only that it might
                    Message 9 of 18 , Feb 15, 2012
                    View Source
                    • 0 Attachment
                      On Wed, 2012-02-15 at 18:26 +0000, Phil Carmody wrote:

                      > And is the title of the paper also shrouded in obscurity that you're
                      > sworn not to reveal, or was that just an oversight in your attempt to
                      > swiftly assert that the algorithm I hadn't even yet told you about
                      > could never work?

                      Two things.

                      1) Never ascribe to malice that which is adequately explained by
                      incompetence.

                      2) I never said your algorithm couldn't work, only that it might not be
                      as easy to implement and run as it is to assert that you have an
                      algorith,

                      > Does it just refer to the fact that the *R*SA with multiple prime
                      > secrets is "wrong" compared the single prime secred of *D*H?

                      Yup.

                      Paul
                    • Paul Leyland
                      ... Give that man a {coconut,cigar,token prize of your choice}.
                      Message 10 of 18 , Feb 15, 2012
                      View Source
                      • 0 Attachment
                        On Wed, 2012-02-15 at 17:20 +0000, djbroadhurst wrote:
                        >
                        > --- In primenumbers@yahoogroups.com,
                        > Phil Carmody <thefatphil@...> wrote:
                        >
                        > > I was interested in what the title of the paper referred to
                        >
                        > I suggest that
                        > Ron = R.L. Rivest
                        > Whit = W. Diffie
                        > but I am not sure if they had a direct argument?

                        Give that man a {coconut,cigar,token prize of your choice}.
                      • djbroadhurst
                        ... I think that Phil might be recalling this paper: http://cr.yp.to/lineartime/dcba-20040404.pdf David (the Open DJB :-)
                        Message 11 of 18 , Feb 15, 2012
                        View Source
                        • 0 Attachment
                          --- In primenumbers@yahoogroups.com,
                          Phil Carmody <thefatphil@...> wrote:

                          > I wouldn't be surprised if DJB
                          > (the UIUC one, not the Open one)
                          > didn't document such an algorithm

                          I think that Phil might be recalling this paper:
                          http://cr.yp.to/lineartime/dcba-20040404.pdf

                          David (the Open DJB :-)
                        • Phil Carmody
                          ... Using an algorithm from (other) DJB. I said that might be the case, didn t I? Aparently I d only need to do ~400Mdigit GCDs rather than giga-digit ones,
                          Message 12 of 18 , Feb 15, 2012
                          View Source
                          • 0 Attachment
                            --- On Wed, 2/15/12, djbroadhurst <d.broadhurst@...> wrote:
                            > However, the GCD idea seems to work OK:
                            >
                            > https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs

                            Using an algorithm from (other) DJB. I said that might be the case, didn't I?

                            Aparently I'd only need to do ~400Mdigit GCDs rather than giga-digit ones, and less than half the RAM. That drops the estimation to about a day. Which is in remarkable agreement with that team's results. Most remarkable as it's a distinct algorithm from DJB's. It might be worth actually implementing, to see how the two compare to each other. To have apparently the same Big-Oh and similar constant to a DJB algorithm just from a back-of-a-fag-packet algorithm doesn't happen every day.

                            Phil
                          • djbroadhurst
                            ... Bang on, good Sir! ... Fortune favours the unsecretive :-) David (the Open DJB)
                            Message 13 of 18 , Feb 15, 2012
                            View Source
                            • 0 Attachment
                              --- In primenumbers@yahoogroups.com,
                              Phil Carmody <thefatphil@...> wrote:

                              > Using an algorithm from (other) DJB.
                              > I said that might be the case, didn't I?

                              Bang on, good Sir!

                              > To have apparently the same Big-Oh and similar constant
                              > to a DJB algorithm just from a back-of-a-fag-packet algorithm
                              > doesn't happen every day.

                              Fortune favours the unsecretive :-)

                              David (the Open DJB)
                            • Phil Carmody
                              ... I was trying to give as little away as possible, as clearly Lenstra et al. didn t want too much made public about the technique they used, and whilst I m
                              Message 14 of 18 , Feb 15, 2012
                              View Source
                              • 0 Attachment
                                --- On Wed, 2/15/12, Paul Leyland <paul@...> wrote:
                                > Phil Carmody wrote:
                                > > And is the title of the paper also shrouded in obscurity that you're
                                > > sworn not to reveal, or was that just an oversight in your attempt to
                                > > swiftly assert that the algorithm I hadn't even yet told you about
                                > > could never work?
                                >
                                > Two things.
                                >
                                > 1) Never ascribe to malice that which is adequately explained by
                                > incompetence.
                                >
                                > 2) I never said your algorithm couldn't work, only that it might not be
                                > as easy to implement and run as it is to assert that you have an
                                > algorithm

                                I was trying to give as little away as possible, as clearly Lenstra et al. didn't want too much made public about the technique they used, and whilst I'm under no obligation to honour that I thought I'd play along. Anyone who could implement such an algorithm would probably recognize its ingredients, and vice versa. When such things get questioned, my steepest gradient it to simply leak parts of the algorithm I had in mind, obviously.

                                It would have been quicker, but far less fun, to run off to my archive of DJB papers, and hunt out the relevant "essentially linear time" paper. So in some ways I'm glad I had to concretise the ideas. When I first had them, they were just so obviously workable, I didn't bother with anything apart from 1-significant-figure guestimations (as you can tell from the factor of 2.5 in my estimation of the size of the input), I'm quite pleased how close they appear to be to potential reality.

                                > > Does it just refer to the fact that the *R*SA with multiple prime
                                > > secrets is "wrong" compared the single prime secred of *D*H?
                                >
                                > Yup.

                                OK, thanks for that. It was not clear as if there was some rump or coffee (or wine?) session comment that had historically been made between the pair (or to a third party) that I wasn't aware of. If the above is the full story, then I think it's unfair to say that "Ron is wrong", as the mathematics and the algorithmics of composite secrets are still bulletproof. It's just that some people (apparently not too many, fortunately) simple can't implement the algorithm correctly. I believe it's even specified that two times as much apparent entropy must be fed into the system as the length of the primes extracted from it. Clearly nothing like that has been honoured in the failing cases. (Can anyone say "15 bits of entropy"?)

                                Phil
                              • djbroadhurst
                                ... It s a poor title for what purports to be a serious article (on insufficient entropy). Try to imagine Pauli using the title Izzy hat geirrt; Bert hat
                                Message 15 of 18 , Feb 15, 2012
                                View Source
                                • 0 Attachment
                                  --- In primenumbers@yahoogroups.com,
                                  Paul Leyland <paul@...> wrote:

                                  > > I suggest that
                                  > > Ron = R.L. Rivest
                                  > > Whit = W. Diffie
                                  > > but I am not sure if they had a direct argument?
                                  >
                                  > Give that man a {coconut,cigar,token prize of your choice}.

                                  It's a poor title for what purports to be a
                                  serious article (on insufficient entropy).

                                  Try to imagine Pauli using the title
                                  "Izzy hat geirrt; Bert hat recht" in
                                  Encyklopädie der Mathematischen Wissenschaften,
                                  Vol. 5, 539-775 (1921).

                                  David
                                • Phil Carmody
                                  ... My method s obvious enough that I m sure it must have occured to Dan, and therefore I m pretty sure there must be something like a log log N of leverage in
                                  Message 16 of 18 , Feb 15, 2012
                                  View Source
                                  • 0 Attachment
                                    --- On Wed, 2/15/12, djbroadhurst <d.broadhurst@...> wrote:
                                    > Phil Carmody <thefatphil@...> wrote:
                                    > > Using an algorithm from (other) DJB.
                                    > > I said that might be the case, didn't I?
                                    >
                                    > Bang on, good Sir!
                                    >
                                    > > To have apparently the same Big-Oh and similar constant
                                    >
                                    > > to a DJB algorithm just from a back-of-a-fag-packet algorithm
                                    > > doesn't happen every day.
                                    >
                                    > Fortune favours the unsecretive :-)

                                    My method's obvious enough that I'm sure it must have occured to Dan, and therefore I'm pretty sure there must be something like a log log N of leverage in his method that makes it win in the long run. (That would be a factor of 20-ish at these sizes, and not to be sniffed at.) However, I will confess to not having read his paper for about 6 years, including today.

                                    Phil
                                  Your message has been successfully submitted and would be delivered to recipients shortly.