Diffie Hellman Question
Res
I am trying to use Diffie Helman to solve an authenticated communication
problem rather than an encryption problem.
Bob needs to send some instructions to Alice.
The instructions are very important for Alice so that she can figure out
what to do next. However, first she has to make sure that the instructions
really came from Bob. They cannot use regular forms of authentication &
hence
I am trying to use DH to solve this issue.
Taking a basic algorithm to clarify terms so that further explanation is
clear.
Alice & Bob are going to use a prime (P) & a base (G).
Alice generates Secret Key a & Bob generates Secret key b
Alice sends Bob A = (G^a) mod P
Bob sends Alice B = (G^b) mod P
Alice computes S = (B^a) mod P
Bob computes S = (A^b) mod P
Bob takes instructions "Please do task XYZ at time TT with MM"
Bob encrypts this using S & sends it to Alice.
Now, in my use case,
- Mallory intercepting Bob's B or Alice A when they are sent to each
other & subtituting it with a different one is not a problem for me. This
is fully prevented by other ways - i.e. Mallory cannot substitute anything
during the initial phase.
- Bob & Alice do not mutually authenticate each other - this is not possible
for me. So integrity of the message is very important for me. Currently, I
solve this
by decrypting the message at Alice end's & make sure it follows a particular
pattern. I do not want Mallory to be able to change the message to
"Please do task XYZ at time T1 with N" or "Please do task ABC at time TT
with MM".
- Ideally Mallory should not be able to decrypt & read the instructions -
but for
me that this relatively less important than Mallory substituting it with his
own instructions.
- My maximum session duration is somewhere between a few minutes to 1 day.
i.e. Alice & Bob do the initial DH thing but the actual instructions may be
sent
by Bob to Alice upto 24 hours after they arrive at the session key.
- Only 1 instruction is sent per session (the plain text instruction may be
20-30
characters long).
Considering these use cases - how should go about chosing the size/lengths
of
P, G, a & b.
1) The Wikipedia page on DH says G need to be large at all - it's usually 2
or 5.
I am assuming the 2 or 5 here refers to the actual number G rather than the
length
of the number G.
Considering this, can Alice & Bob both pre-agree that they will always use 5
as G
till the end of time - any disadvantages in this over everything agreeing
upon a new
value of G.
2) Can P also be hardcoded at both Alice & Bob's end or is it better to use
a new P
each time? If I have to do a new P each time, what is the way to figure out
how long
P should be? I would like P to be as short as possible without compromising
security
heavily if I cannot hardcode P at both ends.
3) How long should a & b be? What are the considerations here for my
usecase.
If anyone can help with these questions it would be great.
Joseph Ashwood
news:hgdjc3$1f4$1...@news.eternal-september.org...
> Not a cryptography expert, so please bear with me.
Not a problem.
> - Bob & Alice do not mutually authenticate each other - this is not
> possible
> for me. So integrity of the message is very important for me. Currently, I
> solve this
> by decrypting the message at Alice end's & make sure it follows a
> particular
> pattern. I do not want Mallory to be able to change the message to
> "Please do task XYZ at time T1 with N" or "Please do task ABC at time TT
> with MM".
Bad idea. What prevents Mallory from repeating instructions? Many other
issues, I'll just cover the fix later.
> Considering these use cases - how should go about chosing the size/lengths
> of
> P, G, a & b.
>
> 1) The Wikipedia page on DH says G need to be large at all - it's usually
> 2 or 5.
> I am assuming the 2 or 5 here refers to the actual number G rather than
> the length
> of the number G.
> Considering this, can Alice & Bob both pre-agree that they will always use
> 5 as G
> till the end of time - any disadvantages in this over everything agreeing
> upon a new
> value of G.
There's nothing gained in changing G, as long as it is a generator the
difficulty is the same. If G isn't a generator then the system is very weak.
Just make sure it's a generator.
> 2) Can P also be hardcoded at both Alice & Bob's end or is it better to
> use a new P
> each time?
A single P of 2048 bits is good for a long time.
> 3) How long should a & b be? What are the considerations here for my
> usecase.
a & b should be long enough that they are harder to figure out then to solve
the discrete logarithm. Since you're not an expert, go with half the length
of P.
Now about the way it should be implemented, you're actually using the
incomplete tool. You want DSA with ElGamal.
Since your instructions are only 30 characters long, I'll be using the
shared value directly instead of building a symmetric key from it. If your
instructions grow in length change this immediately.
Bob and Alice exchange long term public keys Alice_Pub.{A,P,G,Q}
Bob_Pub.{B,P,G,Q}
BOB:
INST = {Time & Date, Instruction to Alice}
K = Random number, same length as Alice_Pub.P
X = Alice_Pub.A^K mod Alice_Pub.P
STK = Alice_Pub.G^K mod Alice_Pub.P
C = INST XOR X
R&S = DSA(SHA-512, INST, Bob_Priv} This is the step that requires Q
Bob sends to Alice { Alice_Pub.A, Alice_Pub.P, C, STK, R&S }
Alice
Verify that Alice_Pub.A and Alice_Pub.P are correct
X = STK^Alice_Priv mod Alice_Pub.P
INST = C XOR X
Verified = DSA-Verify(SHA-512, INST, Bob_Pub)
If Verified = TRUE then verify INST.Time&Date is now+/-1 hour
This only requires one-way communication, and semi-synchronized clocks. For
a reference on this, it is similar to S/MIME. DSA is described several
places I like the NIST description but that's personal preference, the
SHA-512 version is not widely described, just substitute SHA-512 for SHA-1,
Q needs to be 512 bits long.
Joe
Res
Some more questions below.
"Joseph Ashwood" <ash...@msn.com> wrote in message
news:uAHWm.396$8e4...@newsfe03.iad...
> "Res" <r...@pk.com> wrote in message
> news:hgdjc3$1f4$1...@news.eternal-september.org...
>> Not a cryptography expert, so please bear with me.
>
> Not a problem.
>
>> - Bob & Alice do not mutually authenticate each other - this is not
>> possible
>> for me. So integrity of the message is very important for me. Currently,
>> I solve this
>> by decrypting the message at Alice end's & make sure it follows a
>> particular
>> pattern. I do not want Mallory to be able to change the message to
>> "Please do task XYZ at time T1 with N" or "Please do task ABC at time TT
>> with MM".
>
> Bad idea. What prevents Mallory from repeating instructions?
Repeating is an not really an issue in my use case because of a couple
of things
- Alice recieves instructions from Bob only when she requests them.
- Alice does some basic validation on the instructions.
- The instructions contain time TT. So repeating instructions at a later
time
essentially will ensure that Alice's validation fails.
> Many other issues, I'll just cover the fix later.
>
>
>> Considering these use cases - how should go about chosing the
>> size/lengths of
>> P, G, a & b.
>>
>> 1) The Wikipedia page on DH says G need to be large at all - it's usually
>> 2 or 5.
>> I am assuming the 2 or 5 here refers to the actual number G rather than
>> the length
>> of the number G.
>> Considering this, can Alice & Bob both pre-agree that they will always
>> use 5 as G
>> till the end of time - any disadvantages in this over everything agreeing
>> upon a new
>> value of G.
>
> There's nothing gained in changing G, as long as it is a generator the
> difficulty is the same. If G isn't a generator then the system is very
> weak. Just make sure it's a generator.
Yes. Will do.
>
>> 2) Can P also be hardcoded at both Alice & Bob's end or is it better to
>> use a new P
>> each time?
>
> A single P of 2048 bits is good for a long time.
This is a huge pain point for me.
I have a maximum of somewhere around 8 to 10 bytes which can be
transferred from Alice to Bob (as a request). Hence my request is
essentially
going to be Alice transmitting her calculated
(g ** Random Number) mod Prime.
This means that the Prime cannot be a huge number like you suggest.
Even if I use some compression on the calculated value, the initial
calculated value
cannot be very big. This means that I have to use the smallest prime I can.
Considering my use case that I am not so bothered about the instruction
being
cracked, what is the smallest prime I can use.
>> 3) How long should a & b be? What are the considerations here for my
>> usecase.
>
> a & b should be long enough that they are harder to figure out then to
> solve the discrete logarithm. Since you're not an expert, go with half the
> length of P.
The length of a & b is not a big bother for me. Considering that the length
of
Alice's calculated value needs to be small & it's length mainly depends on
the
length of the Prime rather than a, b & g, I am ok with using bigger a, b &
g's.
Can using a bigger a, b or g offset the compromise of having a smaller
length of
P.
Peter Pearson
> "Joseph Ashwood" <ash...@msn.com> wrote in message
> news:uAHWm.396$8e4...@newsfe03.iad...
>>
>
> This is a huge pain point for me.
>
> I have a maximum of somewhere around 8 to 10 bytes which can be
> transferred from Alice to Bob (as a request). Hence my request is
> essentially
> going to be Alice transmitting her calculated
> (g ** Random Number) mod Prime.
> This means that the Prime cannot be a huge number like you suggest.
By using the equivalent elliptic-curve system, you can get
the sizes of the quantities down to 400 bits or so. If you're
really limited to 10 bytes, I don't believe any public-key
system will save you.
I'm sorry to say the unwelcome guild-member thing, but if
it's important that this system be secure against an
intelligent and resourceful adversary, you really need the
committed involvement of someone well experienced in the
field. There are too many subtle mistakes to make, too
many unconscious assumptions, for a casual design approach
to stand any good chance of success.
--
To email me, substitute nowhere->spamcop, invalid->net.
Res
"Peter Pearson" <ppea...@nowhere.invalid> wrote in message
news:7p2lnb...@mid.individual.net...
> On Fri, 18 Dec 2009 17:01:45 +0530, Res <r...@pk.com> wrote:
>> "Joseph Ashwood" <ash...@msn.com> wrote in message
>> news:uAHWm.396$8e4...@newsfe03.iad...
>>>
>>> A single P of 2048 bits is good for a long time.
>>
>> This is a huge pain point for me.
>>
>> I have a maximum of somewhere around 8 to 10 bytes which can be
>> transferred from Alice to Bob (as a request). Hence my request is
>> essentially
>> going to be Alice transmitting her calculated
>> (g ** Random Number) mod Prime.
>> This means that the Prime cannot be a huge number like you suggest.
>
> By using the equivalent elliptic-curve system, you can get
> the sizes of the quantities down to 400 bits or so. If you're
> really limited to 10 bytes, I don't believe any public-key
> system will save you.
Peter, I am really not using DH for secure communication here.
Hence my question whether a smaller prime number will do?
I am not really worried about whether my message can be deciphered.
My big concern is whether Mallory can craft a message to send to
Alice - my understanding is that even I take a prime which much
smaller, I can prevent - I am just trying to validate that.
Anyway, I will look with elliptic-curve system.
Joseph Ashwood
>>> use a new P
>>> each time?
>>
>> A single P of 2048 bits is good for a long time.
>
> This is a huge pain point for me.
>
> I have a maximum of somewhere around 8 to 10 bytes which can be
> transferred from Alice to Bob (as a request). Hence my request is
> essentially
> going to be Alice transmitting her calculated
> (g ** Random Number) mod Prime.
Alice's public key only needs to be transferred once, new each time is
generally not necessary. A simple "The time is now XXXX, processing ready"
message is fine, Bob can just store the public key. Choosing a new private
key without changing parameters doesn't actually do much, but a strong P is
good for billions of billions of uses.
> This means that the Prime cannot be a huge number like you suggest.
> Even if I use some compression on the calculated value, the initial
> calculated value
> cannot be very big. This means that I have to use the smallest prime I
> can.
> Considering my use case that I am not so bothered about the instruction
> being
> cracked, what is the smallest prime I can use.
The largest publicly done discrete log was 613 bits, so if you're willing to
be at the absolute limit 614 bits, that will probably be "secure" for a few
minutes. A better solution would be to move to ECDH (Elliptic Curve Diffie
Hellman) and ECDSA where you can barely be secure at 160 bits (20 bytes),
256 bit to be safe. The 256 bit signature will then take up 512 bits, the
short term key another 512 bits, using SHA-256. This is about the best that
can be done securely. Anything smaller is weak. Using integers a quick check
says the 10 byte version is only about 90 seconds, the elliptic curve maybe
5 minutes, neither is anything approaching secure. Even 16 bytes of ellitpic
curve is only a day or so.
>>> 3) How long should a & b be? What are the considerations here for my
>>> usecase.
>>
>> a & b should be long enough that they are harder to figure out then to
>> solve the discrete logarithm. Since you're not an expert, go with half
>> the
>> length of P.
>
> The length of a & b is not a big bother for me. Considering that the
> length of
> Alice's calculated value needs to be small & it's length mainly depends on
> the
> length of the Prime rather than a, b & g, I am ok with using bigger a, b &
> g's.
> Can using a bigger a, b or g offset the compromise of having a smaller
> length of
> P.
It can't. The values of a,b & g are largely irrelevant to the difficulty in
breaking the security. Only increasing P, or moving to ECC/ECDH will have
any real effect.
Joe
Paul Rubin
> Peter, I am really not using DH for secure communication here.
> Hence my question whether a smaller prime number will do?
It will not do. The security comes from the large size of the prime.
Why do you want to use DH at all? Why not a shared secret key? The
benefit of public key is when there are a large number of communicating
parties, or when strangers want to talk to each other. If it's just two
parties and they know each other, then use secret keys.
Pink
"Paul Rubin" <no.e...@nospam.invalid> wrote in message
news:7xr5qrb...@ruckus.brouhaha.com...
It's not just 2 parties. There is only one Bob in my example, but a large
number
of Alice's he sends instructions to.
Pink
"Paul Rubin" <no.e...@nospam.invalid> wrote in message
news:7xr5qrb...@ruckus.brouhaha.com...
It's not just 2 parties. There is only one Bob in my example, but a large
number of Alices he sends instructions to.
Pink
"Peter Pearson" <ppea...@nowhere.invalid> wrote in message
news:7p2lnb...@mid.individual.net...
Peter, I am programmer without much background in cryptography, but
trying to learn more.
There are existing systems where I am which aren't really secure - they
mostly use glorified XOR cryptography. Their security lies in the auditing
capability. And security is just so that a casual person will not break it.
Just as a learning exercise, I am looking at these systems &
the existing constraints & thinking of ways to make it even 10% more
secure. My ideas or solutions aren't really going to be implemented. Just
doing this in my spare time as an exercise to learn a bit more.
Pink
> "Joseph Ashwood" <ashw...@msn.com> wrote in message be at the absolute
> limit 614 bits, that will probably be "secure" for a few minutes. A better
> solution would be to move to ECDH (Elliptic Curve Diffie Hellman) and
> ECDSA where you can barely be secure at 160 bits (20 bytes), 256 bit to be
> safe. The 256 bit signature will then take up 512 bits, the short term key
> another 512 bits, using SHA-256. This is about the best that can be done
> securely. Anything smaller is weak. Using integers a quick check says the
> 10 byte version is only about 90 seconds, the elliptic curve maybe 5
> minutes, neither is anything approaching secure. Even 16 bytes of ellitpic
> curve is only a day or so.
Ok - got it.
Just out of curiousity, what will be the form of attack to crack this?
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?
This is the part of cryptattack I am not able to understanding - how does
the
attack happen - understanding this will probably help me to analyze security
of a solution better.
Pink
Paul Rubin
> It's not just 2 parties. There is only one Bob in my example, but a large
> number of Alices he sends instructions to.
The same reasoning applies. Public key is good for solving the "N**2
problem" when there are many Alices -and- many Bobs. If there's just
one Bob, then you can still use shared secrets. Will each Alice get
their own instructions? If yes, use a key derivation function like
PBKDF2 to generate a key for each Alice from a single master key held by
Bob.
Can you describe the actual application? That often can help identify
any additional requiremens.
unruh
Those Alices therefor each need a public private key pair, with Bob
needing all of those public keys. Just as he would need all of the
Alices' private keys if he used a private key facility. The sender uses
the public key, the recipient the private.
>
>
unruh
>
>> "Joseph Ashwood" <ashw...@msn.com> wrote in message be at the absolute
>> limit 614 bits, that will probably be "secure" for a few minutes. A better
>> solution would be to move to ECDH (Elliptic Curve Diffie Hellman) and
>> ECDSA where you can barely be secure at 160 bits (20 bytes), 256 bit to be
>> safe. The 256 bit signature will then take up 512 bits, the short term key
>> another 512 bits, using SHA-256. This is about the best that can be done
>> securely. Anything smaller is weak. Using integers a quick check says the
>> 10 byte version is only about 90 seconds, the elliptic curve maybe 5
>> minutes, neither is anything approaching secure. Even 16 bytes of ellitpic
>> curve is only a day or so.
>
> Ok - got it.
> Just out of curiousity, what will be the form of attack to crack this?
>
> 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?
Factoring a 10 byte number does not take that long, so RSA could fall by
factoring. And he does not need a message. Just the public key, and can
find the private key so that he can read the text at the same speed that
Bob can.
> This is the part of cryptattack I am not able to understanding - how does
> the
> attack happen - understanding this will probably help me to analyze security
> of a solution better.
The attack on eiach crypto system is different. The public key systems
require no encrypted text. There is enough info in the public key to
determine if the attack works. (After all Eve the attacker can encrypt
anything she wants with the public key, and thus any attack that can be
launched with an encrypted message can also be launched without) Thus
the private key can be found long before the message is sent.
In the case of RSA, the number N can be factored, and then d, the
private exponent can be easily determined from the knowledge of the
factors, and of the public exponent.
>
>
Ilmari Karonen
>
> Those Alices therefor each need a public private key pair, with Bob
> needing all of those public keys. Just as he would need all of the
> Alices' private keys if he used a private key facility. The sender uses
> the public key, the recipient the private.
For encryption, yes. However, while I haven't followed the thread
quite from the beginning, I seem to recall the original poster saying
they care more about preventing attackers from sending forged
instructions than about preventing them from reading legitimate ones.
If that's indeed the case, what he really needs is a digital
signature, not encryption. And for that, only Bob needs a private
key.
But given the extreme space constraints, I second the recommendation
to consider symmetric crypto. A single master key held by Bob and
used to derive individual keys for each Alice eliminates the need for
Bob to hold a huge number of keys while preventing an attacker from
finding out the master key just by compromising a single Alice.
Note the you don't really need anything like PBKDF2 to do this; a
perfectly fine way to derive the individual keys is K_i := E_K(i),
where K is the master key, E_K a block cipher keyed by K and i an
identifier for a particular Alice.
The identifiers can be anything that fits in a single cipher block:
sequential numbers will work just fine. Then use the derived key K_i
to (encrypt and) MAC the instructions sent to Alice i, truncating the
MAC if you (absolutely) have to. Alice herself knows i and K_i, but
not K, and thus can confirm the authenticity of the instructions but
can't compromise Bob or send false commands to any other Alice.
--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
Res
to me. My understanding of few of the concepts have improved
(still have a long way to go!!).
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
Not really related to my use case, but a few similiarities & hence got
me interested - he also is looking at a not-huge string for the license
key. But I have a few questions related to his post, if anyone
can help, that would be great.
- It looks like in his case also, the generator(g) & the prime(P) are
hard-wired into the app.
- In his case, the [(g**b) mod P] is also hard-wired into the application -
will this reduce the security in a case - I would assume not, since this is
a public key. Looking at his usecase, it doesn't look like he has any
restrictions on the length of P like me - since he is truncating the license
key anyway, he can have a big P - 2048 bit one like Joseph Ashwood
suggested.
- He is using the capabilities string padded with zeroes as the program's
private key - i.e. he is using at as 'a' to generate his public key [(g**a)
mod P]. But it looks like anyone can guess his 'a' because it's not really
random - it's based on known capabilities strings. How does this affect
the security?
- How exactly can one derive a private key from a capabilities string - I
assume it could be something like adding up the ascii values of each
character of the string - or am I misunderstanding something here?
- Joseph gave some respresentive numbers as to how much time
it would take to break my original algorithm - 90 seconds, 5 minutes,
1 day etc. Likewise, what kind of time to break Eric Lee Green's
algorithm?
Ilmari Karonen
>
> 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.
Res
"Ilmari Karonen" <use...@vyznev.invalid> wrote in message
news:slrnhisu69....@melkki.cs.helsinki.fi...
> On 2009-12-20, Res <r...@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.
Joseph Ashwood
news:hgj562$6um$1...@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
Ilmari Karonen
> "Ilmari Karonen" <use...@vyznev.invalid> wrote in message
> news:slrnhisu69....@melkki.cs.helsinki.fi...
>> On 2009-12-20, Res <r...@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).
>
> 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.
That's possible -- even likely. But if that's how it works, I'm not
sure what's the point of using DH there. (Of course, I'm not sure
what the point of using DH there is anyway, so maybe I am missing
something.) Surely an equivalent level of security could be achieved
simply by using a (truncated) MAC of the user-provided info as the
license key.
>> 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.
No, patching would mean modifying the program so that it runs without
the correct license key. This is always possible (except perhaps on
some strongly locked-down "trusted computing" type platforms, assuming
the platform itself hasn't been cracked), but has the disadvantage
that upgrading the patched program to a new official version may make
it stop working.
The method I described is more like reverse engineering. The cracker
just needs to figure out how the program computes the correct license
key and make his key generator do the same thing -- after that, he can
generate any number of valid keys that will work with the official,
unpatched software.
(Now, the way to really stop this would be to use digital signatures:
embed a public key in the program, use the private key to sign the
information provided by the user and make the signature be the license
key. The program then checks that the license key is a valid
signature for the user info. Alas, I'm not aware of any digital
signature scheme that wouldn't be trivially insecure if used to
generate signatures of only about 100 bits, which is about what 20
alphanumeric characters amount to. Mind you, if such a scheme does
exist, I'd be glad to hear of it -- I'm hardly an expert here.)
Res
"Ilmari Karonen" <use...@vyznev.invalid> wrote in message
> On 2009-12-21, Res <r...@pk.com> wrote:
>> "Ilmari Karonen" <use...@vyznev.invalid> wrote in message
>> news:slrnhisu69....@melkki.cs.helsinki.fi...
>>> On 2009-12-20, Res <r...@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).
> [snip]
>>
>> 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.
>
> That's possible -- even likely. But if that's how it works, I'm not
> sure what's the point of using DH there. (Of course, I'm not sure
> what the point of using DH there is anyway, so maybe I am missing
> something.) Surely an equivalent level of security could be achieved
> simply by using a (truncated) MAC of the user-provided info as the
> license key.
MAC would require a shared key, right? I think he is trying to avoid
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.
>
> No, patching would mean modifying the program so that it runs without
> the correct license key. This is always possible (except perhaps on
> some strongly locked-down "trusted computing" type platforms, assuming
> the platform itself hasn't been cracked), but has the disadvantage
> that upgrading the patched program to a new official version may make
> it stop working.
>
> The method I described is more like reverse engineering. The cracker
> just needs to figure out how the program computes the correct license
> key and make his key generator do the same thing -- after that, he can
> generate any number of valid keys that will work with the official,
> unpatched software.
>
> (Now, the way to really stop this would be to use digital signatures:
> embed a public key in the program, use the private key to sign the
> information provided by the user and make the signature be the license
> key. The program then checks that the license key is a valid
> signature for the user info.
I think he is doing exactly that. Only thing instead of using a RSA kind
of public key encryption, he is using DH to generate his public key &
private keys. He mentions why he isn't using RSA.
>Alas, I'm not aware of any digital
> signature scheme that wouldn't be trivially insecure if used to
> generate signatures of only about 100 bits, which is about what 20
> alphanumeric characters amount to.
I am not sure he is generating only a 10 bit value. I think he is generating
a longer one & truncating it.
I find his use interesting.
Hence posted the following questions about it.
http://groups.google.com/group/sci.crypt/msg/5312a90db14a3a69
------------------------------------------------------
- It looks like in his case also, the generator(g) & the prime(P) are
hard-wired into the app.
- In his case, the [(g**b) mod P] is also hard-wired into the application -
will this reduce the security in a case - I would assume not, since this is
a public key. Looking at his usecase, it doesn't look like he has any
restrictions on the length of P like me - since he is truncating the license
key anyway, he can have a big P - 2048 bit one like Joseph Ashwood
suggested.
- He is using the capabilities string padded with zeroes as the program's
private key - i.e. he is using at as 'a' to generate his public key [(g**a)
mod P]. But it looks like an yone can guess his 'a' because it's not really
random - it's based on known capabilities strings. How does this affect
the security?
- How exactly can one derive a private key from a capabilities string - I
assume it could be something like adding up the ascii values of each
character of the string - or am I misunderstanding something here?
- Joseph gave some respresentive numbers as to how much time
it would take to break my original algorithm - 90 seconds, 5 minutes,
1 day etc. Likewise, what kind of time to break Eric Lee Green's
algorithm?
---------------------------------------------------------
Res
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'?
Gordon Burditt
> 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|
Joseph Ashwood
> 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.
That is correct, the second half of the page explains the terminology
choices.
> 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
Less than 4 bytes, but it is prime, so the calculations will work.
> My Random Number 'a' = 740441303
> My A = 2^276794800 mod 276794800 = 276794800
Equation for A isn't correct, but the final value for A is, probably just a
typo.
>
> 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'?
G^exp = G^a mod P, so exp and a are functionally the same. The period matter
in this because k*period+exp = a for some integer k, in this case k=2.
This happens because of additional subgroups of P which can be complicated
to figure out completely.
Joe
Res
> "Res" <r...@pk.com> wrote in message
> news:hgq4rk$8k0$1...@news.eternal-september.org...
>> 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.
>
> That is correct, the second half of the page explains the terminology
> choices.
I couldn't find it - doesn't matter.
>
>> 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
>
> Less than 4 bytes, but it is prime, so the calculations will work.
Meant to write 10 digit prime.
>> My Random Number 'a' = 740441303
>> My A = 2^276794800 mod 276794800 = 276794800
>
> Equation for A isn't correct, but the final value for A is, probably just
> a typo.
Yes - copy/paste error.
>> 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'?
>
> G^exp = G^a mod P, so exp and a are functionally the same. The period
> matter in this because k*period+exp = a for some integer k, in this case
> k=2.
Super. That worked. Thanks very much for your detailed explanation!!!
Res
http://groups.google.com/group/sci.crypt/msg/438469a0c163d6e6
- It looks like in his case also, the generator(g) & the prime(P) are
hard-wired into the app.
- In his case, the [(g**b) mod P] is also hard-wired into the application -
will this reduce the security in a case - I would assume not, since this is
a public key. Looking at his usecase, it doesn't look like he has any
restrictions on the length of P like me - since he is truncating the license
key anyway, he can have a big P - 2048 bit one like Joseph Ashwood
suggested.
- He is using the capabilities string padded with zeroes as the program's
private key - i.e. he is using at as 'a' to generate his public key [(g**a)
mod P]. But it looks like anyone can guess his 'a' because it's not really
random - it's based on known capabilities strings. How does this affect
the security?
- How exactly can one derive a private key from a capabilities string - I
assume it could be something like adding up the ascii values of each
character of the string - or am I misunderstanding something here?
- Joseph gave some respresentive numbers as to how much time
it would take to break my original algorithm - 90 seconds, 5 minutes,
1 day etc. Likewise, what kind of time to break Eric Lee Green's
algorithm assuming different sizes of the prime?
Joseph Ashwood
> Anyone else have a chance to look at this?
>
>
> http://groups.google.com/group/sci.crypt/msg/438469a0c163d6e6
>
> http://bit.ly/5oCFtq
>
> - It looks like in his case also, the generator(g) & the prime(P) are
> hard-wired into the app.
>
> - In his case, the [(g**b) mod P] is also hard-wired into the
> application -
> will this reduce the security in a case - I would assume not, since this
> is
> a public key.
It prevents rolling over the key, but this is always a complex problem to
solve anyway. In terms of security at any given time, it doesn't change it.
> - Joseph gave some respresentive numbers as to how much time
> it would take to break my original algorithm - 90 seconds, 5 minutes,
> 1 day etc. Likewise, what kind of time to break Eric Lee Green's
> algorithm assuming different sizes of the prime?
Same times, its still the same algorithm. The only change would be that if
the entropy of client private key is too low it may be guessable, but for
the use case it won't matter. There is also the matter of if the final value
is too small, probably also not a concern. For your situation it won't work
though because you're transferring different data, so shortcutting a single
transfer won't make things more possible.
It does however bring up a few suggestions for your case. As someone
observed (sorry I deleted your message already) there's really very little
reason for you to use public key cryptography, but I'll keep it for
sympathy. I will also explicitly state right now that this is not the
strongest possible encryption, has a few assumptions to keep an eye on (hash
functions), I also assume that the time portion we discussed before is
strong.
Assume both sides have the public key for the other.
Both sides compute the shared secret SS.
R is a stored counter
message is M
one time key OTK = SHA-512(SS | R) // | is append
EncKey = first 256 bits of SHA-512(OTK | "Encryption Key")
MACKey = first 256 bits of SHA-512(OTK | "Authentication Key")
MAC = AES256-OMAC(MACKey, M) //AES256-OMAC(Key, Data)
Encrypted = AES256-CBC(EncKey, MAC, M) //AES256-CBC(Key, IV, Data)
Transfer = {R, MAC, Encrypted}
R++
Alice's side should be fairly obvious but Alice checks R for validity
(should be one over the last one, account for dropped messages as needed),
computes OTK, EncKey, MACKey, decrypts to get M, checks MAC. Since R only
needs to never repeat it should be fairly easy for you to determine the
length necessary. This will have 128 bits + length( R ) overhead, which is
about the minimum possible, securely.
The choice of CBC instead of CTR is fairly non-obvious. I chose it because
of two concerns. It concerns me that various EncKeys are not guarenteed
fully independent, and for CTR to be secure would require that. The second
concern is that IV is not carefully chosen so while the calculations are
believed to be exceedingly complex I'm not convinced it will be properly
covered by CTRs abilities, CTR requires a few considerations on the IV,
normally these are easily achieved, but reducing the transfer space as much
as possible doesn't allow for control over the IV, CBC has lower
requirements on the IV so it makes more sense. Using CBC also allows the
system to absorb a few mistakes in R where CTR would collapse quickly.
As I said earlier you need to keep an eye on the hash, SHA-512 is a
conservative choice, but any valid cryptographic questions about the
security of SHA-512 and you should abandon it for the current greatest.
There are also some concerns about AES, related keys have security issues,
while the keys are independent enough, progress against AES will also
require moving to a different cipher. These kinds of problems crop up any
time it is necessary to bring some aspect of the system to the absolute
minimum.
The public key cryptography can be removed, although this can cause problems
with key rollover situations. This works because no numbers change, the
shared secret SS is always the same. If you can afford the computation time
I'd recommend keeping it, there are subtle advantages that it gives you.
Joe
Jake
> "Res" <r...@pk.com> wrote in message
> news:hhv6ri$pks$1...@news.eternal-september.org...
>> Anyone else have a chance to look at this?
>>
>>
>> http://groups.google.com/group/sci.crypt/msg/438469a0c163d6e6
>>
>> http://bit.ly/5oCFtq
>>
>> - It looks like in his case also, the generator(g) & the prime(P) are
>> hard-wired into the app.
>>
>> - In his case, the [(g**b) mod P] is also hard-wired into the
>> application -
>> will this reduce the security in a case - I would assume not, since this
>> is
>> a public key.
>
> It prevents rolling over the key, but this is always a complex problem to
> solve anyway. In terms of security at any given time, it doesn't change
> it.
>
>
>
>> - Joseph gave some respresentive numbers as to how much time
>> it would take to break my original algorithm - 90 seconds, 5 minutes,
>> 1 day etc. Likewise, what kind of time to break Eric Lee Green's
>> algorithm assuming different sizes of the prime?
>
> Same times, its still the same algorithm.
That would mean that if this used a big Prime as you suggested, it cannot
be easily cracked easily.
> The only change would be that if the entropy of client private key is too
> low it may be guessable, but for the use case it won't matter. There is
> also the matter of if the final value is too small, probably also not a
> concern.
> For your situation it won't work though because you're transferring
> different data, so shortcutting a single transfer won't make things more
> possible.
I am not sure I understand this last sentence - can you elaborate if
possible.
> The public key cryptography can be removed, although this can cause
> problems with key rollover situations. This works because no numbers
> change, the shared secret SS is always the same. If you can afford the
> computation time I'd recommend keeping it, there are subtle advantages
> that it gives you.
Again - I am not clear what "it" refers to - what do you recommend keeping?
Res
> "Res" <r...@pk.com> wrote in message
> news:hhv6ri$pks$1...@news.eternal-september.org...
>> Anyone else have a chance to look at this?
>>
>>
>> http://groups.google.com/group/sci.crypt/msg/438469a0c163d6e6
>>
>> http://bit.ly/5oCFtq
>>
>> - It looks like in his case also, the generator(g) & the prime(P) are
>> hard-wired into the app.
>>
>> - In his case, the [(g**b) mod P] is also hard-wired into the
>> application -
>> will this reduce the security in a case - I would assume not, since this
>> is
>> a public key.
>
> It prevents rolling over the key, but this is always a complex problem to
> solve anyway. In terms of security at any given time, it doesn't change
> it.
>
>
>
>> - Joseph gave some respresentive numbers as to how much time
>> it would take to break my original algorithm - 90 seconds, 5 minutes,
>> 1 day etc. Likewise, what kind of time to break Eric Lee Green's
>> algorithm assuming different sizes of the prime?
>
> Same times, its still the same algorithm.
That would mean that if this used a big Prime as you suggested, it cannot
be easily cracked easily.
> The only change would be that if the entropy of client private key is too
> low it may be guessable, but for the use case it won't matter. There is
> also the matter of if the final value is too small, probably also not a
> concern.
> For your situation it won't work though because you're transferring
> different data, so shortcutting a single transfer won't make things more
> possible.
I am not sure I understand this last sentence - can you elaborate if
possible.
> The public key cryptography can be removed, although this can cause
> problems with key rollover situations. This works because no numbers
> change, the shared secret SS is always the same. If you can afford the
> computation time I'd recommend keeping it, there are subtle advantages
> that it gives you.
Again - I am not clear what "it" refers to - what do you recommend keeping?
Sorry about multiple messages - I am using a shared computer for this & I
keep
forgetting to use my identity.
Joseph Ashwood
> "Joseph Ashwood" <ash...@msn.com> wrote in message
>>> [...]Eric Lee Green's
>>> algorithm assuming different sizes of the prime?
>> Same times, its still the same algorithm.
>
> That would mean that if this used a big Prime as you suggested, it cannot
> be easily cracked easily.
Correct. And its not just me that suggests large public keys,
http://www.keylength.com/ has a number of recommendations from different
sources, take any recommendation you want.
>> The only change would be that if the entropy of client private key is too
>> low it may be guessable, but for the use case it won't matter. There is
>> also the matter of if the final value is too small, probably also not a
>> concern.
>
>> For your situation it won't work though because you're transferring
>> different data, so shortcutting a single transfer won't make things more
>> possible.
>
> I am not sure I understand this last sentence - can you elaborate if
> possible.
The method described by Eric builds a permission system, but does not
provide authentication or encryption of data. It won't be of any use in your
situation.
>> The public key cryptography can be removed, although this can cause
>> problems with key rollover situations. This works because no numbers
>> change, the shared secret SS is always the same. If you can afford the
>> computation time I'd recommend keeping it, there are subtle advantages
>> that it gives you.
>
> Again - I am not clear what "it" refers to - what do you recommend
> keeping?
it = The public key cryptography computations.
Joe