Further progress on breaking RSA without factoring

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Further progress on breaking RSA without factoring

Gabriel Withington
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
Reply | Threaded
Open this post in threaded view
|

Re: Further progress on breaking RSA without factoring

At0mik
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


Reply | Threaded
Open this post in threaded view
|

Re: Further progress on breaking RSA without factoring

Theo de Raadt-2
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
>
>
>