Prev: Public & Private Key
Next: Encryption & Authentication
From: Paul Rubin on 19 Dec 2009 13:17
"Pink" <pink(a)nvald.com> writes:
> 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.
From: unruh on 19 Dec 2009 16:50
On 2009-12-19, Pink <pink(a)nvald.com> wrote:
>
> "Paul Rubin" <no.email(a)nospam.invalid> wrote in message
> news:7xr5qrb9x7.fsf(a)ruckus.brouhaha.com...
>> "Res" <res(a)pk.com> writes:
>>> 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.
>
> 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.

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.


>
>
From: unruh on 19 Dec 2009 16:57
On 2009-12-19, Pink <pink(a)nvald.com> wrote:
> Thank you for your patience with my 'naive' questions.
>
>> "Joseph Ashwood" <ashw...(a)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.

>
>
From: Ilmari Karonen on 19 Dec 2009 17:12
On 2009-12-19, unruh <unruh(a)wormhole.physics.ubc.ca> wrote:
>
> 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.
From: Res on 20 Dec 2009 00:12
Thank you everyone for your replies. This has been very useful
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

http://bit.ly/5oCFtq

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?




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