The common complaint that I've received about my attack is that it doesn't
work on real keys in real time on my laptop. Now, this is a silly bar to set. The real question is what happens on a fast computer. (If I can break a 1024 bit key in 1000 years on my computer, this is a significant improvement over current methods and will put keys at risk on a supercomputer. I don't have 1000 years or a supercomputer.) But I take the point and I've been working on it. And I think I've got it. What we're looking for is a loop exponent 'k' for message 'm' and semiprime 'n' such that m^k % n = 1. In order for this to be true m^k - 1 = a*n for some integer 'a'. And if we can stick to m=2 for a moment then 2^k - 1 is going to be of a known form - a binary number with every digit equal to 1. Which means that if we can find an integer 'a' such that a*n is all 1s in binary then we can easily find 'k'. And this is actually really straightforward. In fact, ignoring the nasty underflow problem Perl has with their bignum arbitrary precision package which gives faulty values for really small values of 'n', I'm able to quickly find the smallest loop exponent for 2 and a given semiprime. And it takes 'k' operations. (I've attached my proof of concept code. It's messy and uncommented but it works for values that don't fail due to underflow). I haven't tried to extend this to other messages yet but it seems like it could be straightforward - m^k - 1 expressed in base 'm' will always be a string of digits which equal m-1. It's easy to find the values in binary, in other bases it will be given by a*b % m = m-1 (or something like that). But even if this approach is somehow unusable in other bases, it gives the minimum loop exponent for m=2 and that is worth quite a lot. The loop exponent for 2 can then be fed into my original search to scale the exponents and greatly accelerate things. And the loop exponent will also work for lots of other messages. So I'm still working on this but I'm getting close to making this run very fast. Which was really my bigger point all along. It's not that I thought I found the fastest method, I simply saw the existence of a vulnerability which allowed for decryption without factoring as a point for serious concern. The concern being that somebody could look at what I had done so far and come up with a really fast method to break keys. Which might be exactly where I am. Let me know if your people have any thoughts or questions. Thanks! Gabriel backfill.pl (1K) Download Attachment |
Dear Grabriel,
To be honest, I didn't have the motivation to understand the attack. However, the way you handle the disclosure bothers me. Instead of spamming in a "bug" openbsd mailing list and Reddit, do the following: 1) contact a "crypto mathematician expert" from the closest university/google/.../etc and convince him that you are right; 2) he will certainly help you write a research paper and submit to a well known crypto conference; 3) wait for other experts around the world to find flaws in your reasoning. If it occurs that you are right, people will react. Sincerely, Radu On 02/02/2018 09:25 PM, Gabriel Withington wrote: > The common complaint that I've received about my attack is that it doesn't > work on real keys in real time on my laptop. Now, this is a silly bar to > set. The real question is what happens on a fast computer. (If I can break > a 1024 bit key in 1000 years on my computer, this is a significant > improvement over current methods and will put keys at risk on a > supercomputer. I don't have 1000 years or a supercomputer.) > > But I take the point and I've been working on it. And I think I've got it. > > What we're looking for is a loop exponent 'k' for message 'm' and semiprime > 'n' such that m^k % n = 1. In order for this to be true m^k - 1 = a*n for > some integer 'a'. And if we can stick to m=2 for a moment then 2^k - 1 is > going to be of a known form - a binary number with every digit equal to 1. > Which means that if we can find an integer 'a' such that a*n is all 1s in > binary then we can easily find 'k'. And this is actually really > straightforward. > > In fact, ignoring the nasty underflow problem Perl has with their bignum > arbitrary precision package which gives faulty values for really small > values of 'n', I'm able to quickly find the smallest loop exponent for 2 > and a given semiprime. And it takes 'k' operations. (I've attached my proof > of concept code. It's messy and uncommented but it works for values that > don't fail due to underflow). > > I haven't tried to extend this to other messages yet but it seems like it > could be straightforward - m^k - 1 expressed in base 'm' will always be a > string of digits which equal m-1. It's easy to find the values in binary, > in other bases it will be given by a*b % m = m-1 (or something like that). > > But even if this approach is somehow unusable in other bases, it gives the > minimum loop exponent for m=2 and that is worth quite a lot. The loop > exponent for 2 can then be fed into my original search to scale the > exponents and greatly accelerate things. And the loop exponent will also > work for lots of other messages. > > So I'm still working on this but I'm getting close to making this run very > fast. Which was really my bigger point all along. It's not that I thought I > found the fastest method, I simply saw the existence of a vulnerability > which allowed for decryption without factoring as a point for serious > concern. The concern being that somebody could look at what I had done so > far and come up with a really fast method to break keys. Which might be > exactly where I am. > > Let me know if your people have any thoughts or questions. > > Thanks! > Gabriel |
In reply to this post by Gabriel Withington
Radu -
Oh the righteous indignation of public discussion! Stomp stomp. Do you feel better? Go have a teary elsewhere. >Dear Grabriel, > >To be honest, I didn't have the motivation to understand the attack. >However, the way you handle the disclosure bothers me. >Instead of spamming in a "bug" openbsd mailing list and Reddit, do the >following: >1) contact a "crypto mathematician expert" from the closest >university/google/.../etc and convince him that you are right; >2) he will certainly help you write a research paper and submit to a >well known crypto conference; >3) wait for other experts around the world to find flaws in your reasoning. >If it occurs that you are right, people will react. > >Sincerely, >Radu > >On 02/02/2018 09:25 PM, Gabriel Withington wrote: >> The common complaint that I've received about my attack is that it doesn't >> work on real keys in real time on my laptop. Now, this is a silly bar to >> set. The real question is what happens on a fast computer. (If I can break >> a 1024 bit key in 1000 years on my computer, this is a significant >> improvement over current methods and will put keys at risk on a >> supercomputer. I don't have 1000 years or a supercomputer.) >> >> But I take the point and I've been working on it. And I think I've got it. >> >> What we're looking for is a loop exponent 'k' for message 'm' and semiprime >> 'n' such that m^k % n = 1. In order for this to be true m^k - 1 = a*n for >> some integer 'a'. And if we can stick to m=2 for a moment then 2^k - 1 is >> going to be of a known form - a binary number with every digit equal to 1. >> Which means that if we can find an integer 'a' such that a*n is all 1s in >> binary then we can easily find 'k'. And this is actually really >> straightforward. >> >> In fact, ignoring the nasty underflow problem Perl has with their bignum >> arbitrary precision package which gives faulty values for really small >> values of 'n', I'm able to quickly find the smallest loop exponent for 2 >> and a given semiprime. And it takes 'k' operations. (I've attached my proof >> of concept code. It's messy and uncommented but it works for values that >> don't fail due to underflow). >> >> I haven't tried to extend this to other messages yet but it seems like it >> could be straightforward - m^k - 1 expressed in base 'm' will always be a >> string of digits which equal m-1. It's easy to find the values in binary, >> in other bases it will be given by a*b % m = m-1 (or something like that). >> >> But even if this approach is somehow unusable in other bases, it gives the >> minimum loop exponent for m=2 and that is worth quite a lot. The loop >> exponent for 2 can then be fed into my original search to scale the >> exponents and greatly accelerate things. And the loop exponent will also >> work for lots of other messages. >> >> So I'm still working on this but I'm getting close to making this run very >> fast. Which was really my bigger point all along. It's not that I thought I >> found the fastest method, I simply saw the existence of a vulnerability >> which allowed for decryption without factoring as a point for serious >> concern. The concern being that somebody could look at what I had done so >> far and come up with a really fast method to break keys. Which might be >> exactly where I am. >> >> Let me know if your people have any thoughts or questions. >> >> Thanks! >> Gabriel > > > |
Free forum by Nabble | Edit this page |