30
This describes some attacks against textbook RSA (also known as raw RSA), where the public function $x\mapsto y=x^e\bmod N$ or private function $y\mapsto x=y^d\bmod N$ are applied directly to the integer $m$ representing the message. Per standard assumption, the public key $(N,e)$ is known.
Encryption / Decryption
Per standard assumption, ciphertext $c\gets ...
21
This is a common mistake, so I'd like to give an in-depth answer. Basically, what you are proposing is to rely on the ONE-WAYNESS of RSA as a ONE-WAY FUNCTION, rather than relying on its CPA or CCA security as an encryption scheme. The advantage of using RSA as a one-way function is that no padding etc is needed.
Now, the first important thing to note is ...
20
Rather than making an overly long question even longer, I post this as an answer.
As part of the update process of the French security recommendations linked in the question, I suggested (June 2013) a waiver for the requirement/recommendation that $e>2^{16}$ when using a padding scheme with a security proof. It was kindly refused (within 6 weeks), with ...
16
PKCS#1 v1.5 describes a method (formally known as RSAES-PKCS1-v1_5) that turns textbook RSA into a (heuristically) secure encryption scheme for small messages (PKCS#1 v1.5 also describes a signature scheme, which the question and this answer do not consider).
For a $k$-byte ($8k-7$ to $8k$-bit) public modulus part of public key $(N,e)$, the message to be ...
14
The algorithm you quote is usually called textbook RSA and is not used in practice for numerous security reasons (the problem you pointed out, is just one of them).
In practice, you have to pad (or armor) your message. This should be done using the RSA-OAEP (also called PKCS#1 v2.0) scheme. It transforms your message (1) into a pseudorandom block (not 1) ...
13
It is usually assumed that the length of the message is not secret. Even with padding the approximate length is leaked, and necessarily any encryption reveals a maximum length – or at least information content if compression is used – because the ciphertext cannot in general be shorter than the message.
NaCl's secretbox does not use a block cipher, but a ...
12
RSA PKCS#1 is still secure if padding oracles do not apply. If padding oracles apply, for instance when a server verifies the padding after decryption and somehow leaks the result (through an error message or by leaking information about the the verification time) then OAEP is much more secure.
Note that in principle OAEP can also leak information through ...
12
How does the new attack work at top level?
In short
They used BEAST-like Man in the Browser attack by using Cache-like attacks to perform a downgrade attack against any TLS connection to a vulnerable server. With this, they showed the feasibility of using Cache-like attacks.
More detailed
Even over the years, numerous mitigation techniques are ...
12
Padding is dangerous. CBC mode with padding is secure against chosen-plaintext attacks, where the adversary can convince the legitimate party to encrypt messages and obtain the ciphertexts. But it is usually not secure against chosen-ciphertext attacks, where the adversary can craft ciphertexts and obtain information about the corresponding plaintext. ...
answered May 23 at 16:32
Gilles 'SO- stop being evil'
15.6k3 gold badges40 silver badges79 bronze badges
11
Padding is always added, even if the plaintext is a product of the block size. This way the algorithm look for the last byte(s) and can safely interpret it as padding data. In case of alignment to the block size, a full block is added just for padding purposes.
So if your example shows 8 bytes of data and you are using a 64-bit block cipher, a block of ...
11
TL;DR: Padding is part of the specification of the mode and thus doesn't need to be done by the user of the primitive.
Internally GCM really is CTR mode along with a polynomial hashing function applied on the ciphertext. CTR-mode doesn't need padding because you can just partly use the bits the last counter block generated and the polynomial hash does use (...
10
Textbook RSA encryption scheme is not IND-CPA secure as it is a deterministic scheme.
Textbook RSA signature scheme is not secure considering Existential Unforgability under Chosen Message Attack. e.g. if attacker $\mathcal{A}$ chooses random x $\in$ {1,2,...,n-1} and computes y = x$^{e}$ mod n, then sets m = y, $\sigma_{m}$ = x then $\sigma_{m}$ is a valid ...
10
The Structure of PKCS#1 v1.5 as follows;
The message $m$ is padded to
x = 0x00 || 0x02 || r || 0x00 || m
and the ciphertext calculated as $c=x^e\bmod N$ not by $m^e\bmod N$, where $r$ is a random string.
Cube root attack cannot be applied since the padding guarantees that messages are not short.
The random $r$ make the encryption probabilistic so that ...
9
One good reason not to use RSAES-OAEP for signature is because as it stands, it can't do signature! RSAES-OAEP performs encryption of a message (of limited length) with optional label into a cryptogram, and decryption thereof. There is no way to turn some RSAES-OAEP black box into a signing machine.
OK, we could define an RSA signature scheme with a ...
8
Without a well-designed padding system it may be possible to craft a ciphertext that the decryptor may or may not be able to decrypt properly. Whether the decryptor is able to do so will depend on the private key. The concern is that an attacker may be able to craft a string of ciphertexts, listen in to whether they decrypt properly, and finally deduce the ...
8
Is it somehow connected with sequentially reading in files /data of unknown length?
Yes, indeed. It is part of a requirement to perform online message processing, or, in other words, the ability to stream the data without knowing how much data to expect.
Would it make a difference if you always knew the length of the message to be hashed?
Well, yes, in ...
8
PKCS7 uses mandatory padding. Even if the length of your data is a multiple of your block size, it will pad.
output_size = input_size + (block_size - (input_size % block_size))
8
You are talking about the PKCS#7 padding. There is a simple reason; assume that when the last block is full and you don't apply the padding before encryption and then send the message.
When decrypting, the receiver needs to see a padding pattern to remove the padding. What if the last byte is 01 of the message? is it padding or the message itself? ...
7
The problem is not with compression and encryption, it is with the protocol that is being used, and the type of data being compressed (or not) prior to encryption.
The most damning leaks are on protocols that were either designed to be compressed without encryption, or encrypted without compression.
The best example I have is VOIP systems that use a ...
7
ANSI x.923 padding and the padding used within PKCS#7 are functionally equivalent. The last byte of the padding stream is the length of the padding stream. The difference is the value of the other bytes, which are all 0x00 in ANSI, and all the identical to the last byte in PKCS#7.
f4 93 d6.00 00 00 00 00 00 00 00 00 00 00 00 0d ANSI X.923
f4 93 d6.0d 0d ...
7
I am a cryptographic researcher at Security Innovation, which acquired NTRU.
Apart from the aforementioned attack, there are two significant attacks, namely a chosen plaintext attack (CPA) and a chosen ciphertext attack (CCA), when a proper padding scheme is not used.
Recall that in an IND-CPA game, the challenger is given two plaintexts, suppose they are ...
7
The EAX mode of operation is defined for 128 bit block ciphers. It consists of a combination of CTR mode for confidentiality and OMAC for authentication and nonce derivation. CTR mode does not require padding, but OMAC does, since it is based on CBC-MAC, when the length of the plain text is not a multiple of 128 bits.
Hence, such specifications might mean ...
7
Hash functions we use, e.g. Sha-1, Sha-256, Sha-512, usually don’t have a sufficiently large range. But we can construct full domain hash via repeated application of a hash function $h$: $FDH(m) = h(m||0)||h(m||1)||\cdots $, then take the leading n-bit. This way the hash value is deterministic and the size is arbitrary.
This is something like MGF1 defined ...
6
If we note $|m|$ the number of bits in the bytestring coding the message $m$, the first padding considered is $m\mapsto \tilde m=257\cdot2^{|m|}+m$, and the signature is $m\mapsto\tilde S(m)=S(\tilde m)=\tilde m^d\bmod N$, where $S$ is the textbook/naked RSA signing $m\mapsto m^d\bmod N$. Notice that for any $m$ small enough that $m^2$ can be signed, we can ...
6
The documentation says:
All the block ciphers normally use PKCS#5 padding also known as standard block padding
which is both informative, and slightly misleading. OpenSSL supports, by default, one stream cipher (RC4) and a variety of block ciphers (Blowfish, 3DES, AES...). The enc command (from the command-line tool) encrypts an input file into an ...
6
In $\text{SHA-512}$ the size of the blocks is 1024 bit. The last block must contain:
the rest of data in message (mod 1024).
some filling (padding)
the last 128 bits as length
If the message is 1919 bit length:
Calculate the size of the data in the last block:
$1919 \mod 1024 = 895$
Add the size of length field(128 bit) to the last block size(895 bit), $...
6
If you were using $e=3$, then there is a well known attack by Bleichenbacher that enables the trivial generation of a signature that passes verification. This attack was never published, but is described here. Note that this attack appeared in a real vulnerability in Kindle (and some versions of Android).
In any case, the attack does not work for $e=65536$. ...
6
That's correct. Here are the padding instructions from RFC1321, the MD5 spec:
3.1 Step 1. Append Padding Bits
The message is "padded" (extended) so that its length (in bits) is
congruent to 448, modulo 512. That is, the message is extended so
that it is just 64 bits shy of being a multiple of 512 bits long.
Padding is always performed, even if ...
6
PKCS#5 was initially written for block ciphers using 64-bit blocks, and up to and including PKCS#5v2.0 had no provision for larger ones. PKCS#5v2.1 remains littered with references to eight octets, including in padding.
The principle that PKCS#5 uses for 64-bit blocks padding is easily generalized to block ciphers with larger blocks (up to 255 octets per ...
6
Symmetric crypto does not always have padding. Stream ciphers often will not require padding. Padding is necessary when using a cipher that requires plaintexts to be a multiple of a particular size. For example, AES in CBC mode requires plaintexts that are a multiple of 128 bits. So if your plaintext is not, you must pad to make it the right size.
Only top voted, non community-wiki answers of a minimum length are eligible