Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 6 down vote favorite

I am attempting to determine the strength of an incorrectly implemented 1024 bit RSA signature scheme. The weakness in the implementation is that the padding data lacks random numbers. As a result, for every message signed, only 160 bits of data are changed (cryptographic hash).

How does one determine the resulting reduction of strength in the scheme? How many signed messages would be necessary to make a 1024 bit private key a mathematically feasible operation to recover?

share|improve this question
1  
The PKCS#1 v1.5 signature scheme does not use randoms during signature creation, so your question might be void. It only uses randoms within PKCS#1 v1.5 encryption, and that is mainly used to protect plain text. The full mathematical and cryptographic answer is certainly something for crypto as Jason S suggests. When you ask the answer there, please provide more info on the actual scheme used as you cannot answer the question without that info. – owlstead Feb 3 '12 at 22:25

2 Answers

up vote 7 down vote accepted

Well, there are no necessary 'reduction in strength', for two reasons:

  • You ask about how many signatures you'd need to recover the private key. Well, even with unrestricted Oracle access to the private operation, there's no known way to recover the private key (or equivalently, factor the modulus) that's more efficient than just ignoring the Oracle and attacking the modulus directly. Hence, giving the attacker access to a limited number of signatures cannot help him recover the private key.

  • What the attacker might be able to do with some padding methods is deduce the value of other signature operations; this would be generating a forgery without the private key. Now, there are certainly known padding methods (such as a naive 'zero fill' method) that are prone to this. On the other hand, there are deterministic padding methods (such as the PKCS #1.5 RSASSA-PKCS1-v1_5 method) for which there is no known method of generating forgeries easier than finding collisions in the hash function.

So, if the system is using, say, the above PKCS method, there is no known weakness, even if the attacker has access to huge numbers of signatures.

share|improve this answer
I understood that introducing random data in the block to be RSA encrypted was necessary. So based on your answer, padding the cryptographic hash even with 0xff does not introduce any weaknesses into the system? – hsikcah Feb 3 '12 at 17:19
1  
@hsikcah: introducing randomness is necessary for data encryption (before applying the public key operation), but is optional for signature production (before applying the private key operation). PKCS#1-v1.5 signs without randomness, and there is no known attack. ISO/IEC 9796-2 scheme 3 also signs without randomness, and even has a strong security proof. – fgrieu Feb 3 '12 at 17:29
@hsikcah: to answer your question about "padding the cryptographic hash with 0xff" with certainty, some details are missing on what happens on the very left. If the padding produces a value less than n (implying that the leftmost bit is forced to 0, not 1), likely your are safe. Same if the adversary can not realistically obtain the signature of many messages of chosen content. – fgrieu Feb 3 '12 at 17:42
1  
@hsikcah: Also, no matter how bad the padding scheme and how many signatures an adversary gets, the private key never leaks for that reason (that's a virtue of the odd exponent in RSA). What can happen is that an adversary could forge signatures of some messages, using the signatures of other messages. – fgrieu Feb 3 '12 at 17:51
Given that the public key and modulus are stored in a hardware device, it is sent some data and a signature. It uses the keys to decrypt the signature and compare it against a locally calculated cryptographic hash. I just happen to know that once decrypted the signature is a 160 bit hash preceeded by 0x1f 0xfffff....fff (864 bits of padding). I was hoping this could somehow be used to find a way to generate my own signature blocks that would correctly decrypt and validate. – hsikcah Feb 3 '12 at 18:57
show 3 more comments
up vote 4 down vote

Well, that is exactly how RSA signatures normally work. PKCS#1 version 1.5 block type 1 is the most common signature format used today. For block type 1, the padding is a constant string, and the data is the hash packaged in an ASN.1 structure that also identifies the signature algorithm.

More modern signature schemes incorporate a random component, but they are not nearly as widely supported yet.

share|improve this answer
GregS: String of constants, or string of constants for a certain key size and hash algorithm? The length of the string depends on the (structure around the) hash algorithm and of course the 3 byte overhead, so the string itself is not constant. – owlstead Feb 4 '12 at 2:05
owlstead: You are correct, the amount of padding depends on the hash function and the key size. Rather than edit the answer, I'll just suggest that for full details the reader is encouraged to examine the RFCs linked to. – GregS Feb 4 '12 at 3:00
I guess that would suffice :) – owlstead Feb 4 '12 at 13:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.