full-disclosure - Re: question regarding RSA

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date: Thu, 2 Sep 2010 20:25:19 +0200 (CEST)
From: Pavel Kankovsky <peak@...o.troja.mff.cuni.cz>
To: jf@...s74ur.corenetworks.net
Cc: full-disclosure@...ts.grok.org.uk
Subject: Re: question regarding RSA

On Mon, 30 Aug 2010 jf@...s74ur.corenetworks.net wrote:

> basically my understanding of RSA PKI

You made general questions about RSA as a cryptographic primitive.
There was nothing about PKI in them.

> is that the padding bytes are added because RSA is a deterministic
> algorithm and that without the padding an attacker with knowledge of the
> plaintext and access to the resultant ciphertext can significantly
> reduce the keyspace in deducing the private key, but the question is by
> how much?

RSA encryption uses public keys. Public keys are--as their name
suggests--supposed to be known publicly. Anyone can compute ciphertexts
from plaintexts. An encryption oracle will not help you crack RSA private 
keys. If you can do it with the oracle, you can do it without the oracle 
as well.

As far as encryption is concerned the purpose of padding is to provide
semantic security ie. to make it impossible to infer anything useful about
the plaintext (e.g. the value of any bit, equality to another plaintext)  
given its corresponding ciphertext.

RSA itself is not semantically secure. When you get two ciphertexts you
can always tell with certainty whether their plaintexts were identical
(this can lead to a practical attack if the set of possible plaintexts is
known and small enough to make it possible to compute and check all
possible ciphertexts). This holds for any deterministic encryption
function. Moreover, RSA preserves certain properties of plaintext (such
as Jacobi symbol).

An oracle can help you crack RSA private keys but it needs to be a 
DECRYPTION oracle (viz Bleichenbacher attack).

-- 
Pavel Kankovsky aka Peak                          / Jeremiah 9:21        \
"For death is come up into our MS Windows(tm)..." \ 21st century edition /

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/