Prev: Public & Private Key
Next: Encryption & Authentication
From: Ilmari Karonen on 20 Dec 2009 14:19
On 2009-12-20, Res <res(a)pk.com> wrote:
>
> While googling around for diffie-hellman related threads in sci.crypt,
> I came across this rather old post.
>
> http://groups.google.com/group/sci.crypt/msg/438469a0c163d6e6

I'm obviously missing something about the system he describes (how
does the key generator learn Y, for example?), but it doesn't seem to
offer even the security he claims it does (specifically, preventing
the creation of unauthorized key generators).

Specifically, whatever goes on before that, as the last step he has
the program compute a license key L and compare it with the one
entered by the user. So it seems to me that creating an unauthorized
key generator ought to be trivial: just extract the part that computes
L from the program and modify it so that it prints out the result
rather than checking that the user entered it correctly.

--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
From: Res on 20 Dec 2009 23:26

"Ilmari Karonen" <usenet2(a)vyznev.invalid> wrote in message
news:slrnhisu69.o3t.usenet2(a)melkki.cs.helsinki.fi...
> On 2009-12-20, Res <res(a)pk.com> wrote:
>>
>> While googling around for diffie-hellman related threads in sci.crypt,
>> I came across this rather old post.
>>
>> http://groups.google.com/group/sci.crypt/msg/438469a0c163d6e6
>
> I'm obviously missing something about the system he describes (how
> does the key generator learn Y, for example?), but it doesn't seem to
> offer even the security he claims it does (specifically, preventing
> the creation of unauthorized key generators).

His step 1
>>>>>>>>>>>>>>>>>>>>>>>>>
1. Expecting the consumer to type in more than 20 characters for a
licensing string was not in the cards. It wasn't going to happen.
It was, however, possible to have the consumer type in various other
licensing info (his name, the serial number, the number of users
authorized for this installation, etc.).
<<<<<<<<<<<<<<<<<<<<<<<<<

So maybe the consumer types in his licensing info & y is based on this
licensing info. I think the software vendor knows this information.
So he can feed it into the key generator & calculate Y= 2**y mod P
from that.

>
> Specifically, whatever goes on before that, as the last step he has
> the program compute a license key L and compare it with the one
> entered by the user. So it seems to me that creating an unauthorized
> key generator ought to be trivial: just extract the part that computes
> L from the program and modify it so that it prints out the result
> rather than checking that the user entered it correctly.

I think that's patching not cracking. He does mention this in step 7.

In general, how do I analyze how much time it would take to break
his system & generate a key - assuming he is using a 2048 byte
Sophie Germain prime & the license key generator's private key
is embedded in the program & hence possibly breakable.



From: Joseph Ashwood on 21 Dec 2009 06:39
"Pink" <pink(a)nvald.com> wrote in message
news:hgj562$6um$1(a)news.datemas.de...
> i.e. an eavesdropper knows g, P, Alice & Bob's each's generated public
> key. He also knows the encrypted text.
> Now what will he do in 90 seconds (of a program) to get the shared secret?
> He has to guess either a or b to get to the shared secret, right?

Actually he computes the shared secret. DH is based on the Discrete
Logarithm Problem (DLP). DLP is:
Given what we have called G, P, and A (Alice's Public Key) compute a such
that A = G^a mod P.
Computing a can be performed far faster than brute force (guessing). The
best integer algorithms are variations of the number field sieve which are
actually surprisingly fast. You can actually find several implementations
and explainations with a Google search,
http://www.alpertron.com.ar/DILOG.HTM is the one that did the 10 byte
version in about 90 seconds.
Joe

From: Res on 22 Dec 2009 04:51

"Joseph Ashwood" <ashwood(a)msn.com> wrote in message
news:AuJXm.67970$Wd1.11338(a)newsfe15.iad...
> "Pink" <pink(a)nvald.com> wrote in message
> news:hgj562$6um$1(a)news.datemas.de...
>> i.e. an eavesdropper knows g, P, Alice & Bob's each's generated public
>> key. He also knows the encrypted text.
>> Now what will he do in 90 seconds (of a program) to get the shared
>> secret?
>> He has to guess either a or b to get to the shared secret, right?
>
> Actually he computes the shared secret. DH is based on the Discrete
> Logarithm Problem (DLP). DLP is:
> Given what we have called G, P, and A (Alice's Public Key) compute a such
> that A = G^a mod P.
> Computing a can be performed far faster than brute force (guessing). The
> best integer algorithms are variations of the number field sieve which are
> actually surprisingly fast. You can actually find several implementations
> and explainations with a Google search,
> http://www.alpertron.com.ar/DILOG.HTM is the one that did the 10 byte
> version in about 90 seconds.
> Joe


Thanks again, Joseph - I have sort of understood the discrete logarithm
problem now.
Thank you again.

I don't understand the alpertron applet's terminology
It uses the following 5 words.

Base, Power, Mod
Exp, Period.

For A = G^a mod P

Here, I think
A would be the Power.
G would be the Base
P would be the Mod
Exp would be 'a' - which we need to compute.
I don't get what's Period in the Applet.

I am trying to use the applet to break some DH numbers
I generated.

My Generator G = 2
My 10 byte Prime P = 1500450271
My Random Number 'a' = 740441303
My A = 2^276794800 mod 276794800 = 276794800

In the Applet, I enter
Base = 2
Power = 276794800
Mod = 1500450271

Now I click on "Find Discrete Logarithm", I get
Exp 240291213
Period 250075045
This just takes a fraction of a second.

But how does this lead to 'a'?



From: Gordon Burditt on 25 Dec 2009 00:33
>1. Expecting the consumer to type in more than 20 characters for a
> licensing string was not in the cards. It wasn't going to happen.
> It was, however, possible to have the consumer type in various other
> licensing info (his name, the serial number, the number of users
> authorized for this installation, etc.).

You mean I'm not going to be able to get users to type in my license
key format (example follows):

Il|1I-1l|!l-||1!I-l1l|l-lI|!|-1|I|1-!||I!-|Ill|-!Il!!-|I!11
Ill1l-I|1ll-11!|l-1l!I|-!1|1!-|!!I1-|IlII-!Il!!-|1lI!-|ll!!
11!I|-l||||-|ll1l-l1!!!-1!l||-ll1!|-|l|Il-1lI!!-Il|!I-!1II1
1!lII-1lll1-!I!Il-1I1!!-!!|lI-l|1!l-|l|I1-|!lI1-!|1II-IIlI!
l!III-Il1!I-II!||-l!I1I-1!|1!-11!!l-!||!|-|1!Il-|I!Il-I1|l1
1ll1I-11l!l-|1Il|-I!||!-1l|!!-1IlIl-l1I!1-I!l!l-!III1-1ll!1
1!l|l-|1l!I-||I|!-!l1||-llI|l-1!!l!-!l1|1-I|1!I-1!|!l-l1!||
|111|-!1|II-I1!1!-l!l|1-!!!!I-l111|-!!I1l-|!Il!-l!!||-l!l|I
I!|II-IlIII-IIII1-!|lI!-1lI|!-1III|-I|l1|-l1I|!-l1!l1-!I|1I
l|!|!-I!|II-1l|I!-l1!!|-1|!!!-!1!I1-|1Il!-!|I|1-I!!1|-1l!l|

First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: Public & Private Key
Next: Encryption & Authentication