Re: Raw RSA binary string and public key 'detection'

2008-11-22 Thread Florian Weimer
* Dirk-Willem van Gulik:

 Been looking at the Telnic (dev.telnic.org) effort.

 In essence; NAPTR dns records which contain private details such as a
 phone number. These are encrypted against the public keys of your
 friends (so if you have 20 friends and 3 phone numbers visible to all
 friends - you need 20 subdomains x 3 NAPTR entries under your
 master').

 Aside from the practicality of this - given a raw RSA encrypted block
 and a list of public keys - is there any risk that someone could
 establish which of those public keys may have been used to create that
 block ?

If the padding scheme is decent, this should not be possible without
breaking RSA.

However, the proposal limits keys to about 250*6 bits, which seems
rather restrictive for RSA keys.

I'm also concerned about reflective attacks were you ask someone who's
trusted by the data owner to decrypt the data for you, possibly in an
automated fashion.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Raw RSA binary string and public key 'detection'

2008-11-20 Thread Dirk-Willem van Gulik

Been looking at the Telnic (dev.telnic.org) effort.

In essence; NAPTR dns records which contain private details such as a  
phone number. These are encrypted against the public keys of your  
friends (so if you have 20 friends and 3 phone numbers visible to all  
friends - you need 20 subdomains x 3 NAPTR entries under your 'master').


Aside from the practicality of this - given a raw RSA encrypted block  
and a list of public keys - is there any risk that someone could  
establish which of those public keys may have been used to create that  
block ? I.e. something which would be done in bulk for large  
populations; so the use of large tables and what not is quite warranted.


Thanks,

Dw

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Raw RSA

2006-09-11 Thread Alexander Klimov
On Sun, 10 Sep 2006, James A. Donald wrote:
 Could you describe this attack in more detail.  I do not see a
 scenario where it would be useful.

Suppose that an attacker runs an activex control on the user's
computer and the control is able to ask a smart card connected to the
computer to perform raw RSA operations with user's private key. The
goal of the attacker is to be able to sign some useful messages with
the user's private key *after* the user disconnect his smart card.

 The attacker can encrypt a subset of numbers - those that encrypt to
 a B smooth number, but for this to be useful to him, he has to find
 a number in the subset set that corresponds to what he desires to
 encrypt, which looks like a very long brute force search.

If the attacker needs to sign a message x, he needs to find a smooth
number y = x + k n, where n is the RSA modulus and k is some arbitrary
number. I forgot what was the algorithm to find such y (I am not even
sure that it exists), IIRC, it was based on LLL.

-- 
Regards,
ASK

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Raw RSA

2006-09-10 Thread James A. Donald

Leichter, Jerry wrote:

| It is known, that given such an oracle, the attacker can ask for
| decryption  of all primes less than B, and then he will be able to
| sign PKCS-1 encoded messages if the representative number is B-smooth,
| but is there any way to actually recover d itself?



RSA is multiplicative, so, yes, this follows easily unless the encoding
used prevents it.


Could you describe this attack in more detail.  I do not see a scenario 
where it would be useful.


The attacker can encrypt a subset of numbers - those that encrypt to a B 
smooth number, but for this to be useful to him, he has to find a number 
in the subset set that corresponds to what he desires to encrypt, which 
 looks like a very long brute force search.



-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Raw RSA

2006-09-10 Thread John R. Black
 I don't follow.  For RSA, the only difference between encryption and
 decryption, and public and private key, and hence between chosen
 plaintext and chosen ciphertext, is the arbitrary naming of one of
 a pair of mutually-inverse values as the private key and the other
 as the public key.
   -- Jerry
  
Negative, Jerry.

There is a very big difference between which one you make public and
which one you make private.  The difference is that the public one
is given out to the world.

It is well known that if d (the RSA private exponent) is small enough,
it can be recovered via Wiener's continued fraction attack or the 
several extensions of it.  I think Wiener's attack worked if d  N^{1/4},
and Boneh (with Glenn Durfee) brought this up to N^{.292}.  There is
a conjecture that d needs to be  sqrt(N), but no one's come close to
proving this.

So it IS important which one you name as the private key: name the bigger
one! :)

john//

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Raw RSA

2006-09-10 Thread Leichter, Jerry
|  | It is known, that given such an oracle, the attacker can ask for
|  | decryption  of all primes less than B, and then he will be able to
|  | sign PKCS-1 encoded messages if the representative number is B-smooth,
|  | but is there any way to actually recover d itself?
| 
|  RSA is multiplicative, so, yes, this follows easily unless the encoding
|  used prevents it.
| 
| Could you describe this attack in more detail.  I do not see a scenario where
| it would be useful.
| 
| The attacker can encrypt a subset of numbers - those that encrypt to a B
| smooth number, but for this to be useful to him, he has to find a number in
| the subset set that corresponds to what he desires to encrypt, which  looks
| like a very long brute force search.
Let R(x) = x^k mod n - where k might be the public key - for encryption -
or the private key - for signing.  R(xy) = R(x)R(y) mod n.  For
encryption, this means little - since the encryption exponent is
public, anyone can compute R(xy) directly anyway.  But for signing,
it means that if I have my hands on signed copies of x and y, I can
forge a signature on xy.  Thus, if I am able to get signatures on a
good collection of primes, I can sign many messages easily.  Yet
another reason to sign hashes of messages, not raw messages - and
that the signer module should compute the hash itself, not rely on
the caller to do it.
-- Jerry


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Raw RSA

2006-09-08 Thread Leichter, Jerry
| Hi.
| 
| If an attacker is given access to a raw RSA decryption oracle (the
| oracle calculates c^d mod n for any c) is it possible to extract the
| key (d)?
If I hand you my public key, I have in effect handed you an oracle that
will compute c^d mod n for any c.  What you are asking is whether you
can then extract my private key e - which is exactly what the security
claims for RSA say you cannot do.  (Note that I chose to call my
public key d and by private key e - but since the two keys are
completely equivalent in RSA, that's just naming.)
 
| It is known, that given such an oracle, the attacker can ask for
| decryption  of all primes less than B, and then he will be able to
| sign PKCS-1 encoded messages if the representative number is B-smooth,
| but is there any way to actually recover d itself?
RSA is multiplicative, so, yes, this follows easily unless the encoding
used prevents it.
-- Jerry

| -- 
| Regards,
| ASK
| 
| -
| The Cryptography Mailing List
| Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
| 

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Raw RSA

2006-09-08 Thread Alexander Klimov
On Thu, 7 Sep 2006, Leichter, Jerry wrote:
 | If an attacker is given access to a raw RSA decryption oracle (the
 | oracle calculates c^d mod n for any c) is it possible to extract the
 | key (d)?
 If I hand you my public key, I have in effect handed you an oracle that
 will compute c^d mod n for any c.  What you are asking is whether you
 can then extract my private key e - which is exactly what the security
 claims for RSA say you cannot do.  (Note that I chose to call my
 public key d and by private key e - but since the two keys are
 completely equivalent in RSA, that's just naming.)

I want to extract the exponent that is used by the oracle: this is the
difference between the chosen-plaintext attack (it does not require an
oracle, since it is a public key scheme) and the chosen-ciphertext
attack (CCA1).

-- 
Regards,
ASK

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Raw RSA

2006-09-08 Thread Hal Finney
Alexander Klimov asks:
 If an attacker is given access to a raw RSA decryption oracle (the
 oracle calculates c^d mod n for any c) is it possible to extract the
 key (d)?

This is equivalent to asking whether factoring reduces to RSA inversion.
That is, given access to an RSA inversion oracle, can you factor the
modulus?  (Factoring the modulus is equivalent to finding d.)

Then see Breaking RSA May Not Be Equivalent to Factoring by Boneh and
Venkatesan, Eurocrypt 98.  Abstract (with my added emphasis):

We provide evidence that breaking low-exponent RSA cannot be equivalent
to factoring integers. We show that an algebraic reduction from factoring
to breaking low-exponent RSA can be converted into an efficient factoring
algorithm. THUS, IN EFFECT AN ORACLE FOR BREAKING RSA DOES NOT HELP In
FACTORING INTEGERS. Our result suggests an explanation for the lack of
progress in proving that breaking RSA is equivalent to factoring. We
emphasize that our results do not expose any specific weakness in the
RSA System.

So the answer would appear to be no, an oracle for RSA does not help in
factoring and therefore will not reveal d.

See also http://citeseer.ist.psu.edu/bellare01onemorersainversion.html
The One-More-RSA-Inversion Problems and the Security of Chaum's Blind
Signature Scheme by Bellare et al for some discussion of this issue.

Hal Finney

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Raw RSA

2006-09-08 Thread Leichter, Jerry
|  | If an attacker is given access to a raw RSA decryption oracle (the
|  | oracle calculates c^d mod n for any c) is it possible to extract the
|  | key (d)?
|  If I hand you my public key, I have in effect handed you an oracle that
|  will compute c^d mod n for any c.  What you are asking is whether you
|  can then extract my private key e - which is exactly what the security
|  claims for RSA say you cannot do.  (Note that I chose to call my
|  public key d and by private key e - but since the two keys are
|  completely equivalent in RSA, that's just naming.)
| 
| I want to extract the exponent that is used by the oracle: this is the
| difference between the chosen-plaintext attack (it does not require an
| oracle, since it is a public key scheme) and the chosen-ciphertext
| attack (CCA1).
I don't follow.  For RSA, the only difference between encryption and
decryption, and public and private key, and hence between chosen
plaintext and chosen ciphertext, is the arbitrary naming of one of
a pair of mutually-inverse values as the private key and the other
as the public key.
-- Jerry
 
| -- 
| Regards,
| ASK
| 
| -
| The Cryptography Mailing List
| Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
| 

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Raw RSA

2006-09-07 Thread Alexander Klimov
Hi.

If an attacker is given access to a raw RSA decryption oracle (the
oracle calculates c^d mod n for any c) is it possible to extract the
key (d)?

It is known, that given such an oracle, the attacker can ask for
decryption  of all primes less than B, and then he will be able to
sign PKCS-1 encoded messages if the representative number is B-smooth,
but is there any way to actually recover d itself?

-- 
Regards,
ASK

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]