# RSA message integrity

I wish to send some small data that RSA alone can encrypt, and I send a shared secret along with it.

A --> B ; RSA(data||shared_secret)  // B will verify the shared_secred and authenticate A;


vs

A --> B ; RSA(data||shared_secret) || SHA-256(data||shared_secret)


RSA is RSA-OEAP, not something home grown.

Will verifying the shared secret be enough for message integrity and authenticity? Or, should I also send a hash of the message? I wish to ask because it seems redundant to send twice as much data if I do not need the hash.

• @fgrieu, I meant RSA-OAEP. I'm not writing my own implementation, only writing the handshake where A tells B the password. – user29359 Dec 8 '15 at 9:02
• @fgrieu, made the changes as you suggested. – user29359 Dec 8 '15 at 9:06
• I agree, the auth should be the job of HMAC, but shared_secret is a plain text password, this handshake establishes a random 128 bit key for later HMAC, but A only knows a password, which might or might not be weak and hence no HMAC here, because that means a dictionary attack on the second one for sure. This is why the question came up, which is --- Is RSA which contains the authentication secret good enough. The scheme is to send password and a random number. The random number cryptographically strong for use in HMAC later. – user29359 Dec 8 '15 at 9:32

If shared_secret is a plain text password as we are told, then the second method, which sends
RSA-OAEP(data||shared_secret) || SHA-256(data||shared_secret)
is unsafe.

That's because a guess of data allows to mount an off-line check of the password by comparison to the known SHA-256(data||shared_secret). That's ideal for password cracking. That also applies if we change SHA-256(data) to HMAC-SHA-256(shared_secret, data), which is a way of constructing a MAC from a hash with a security proof/argument.

For the same reason, that construction also compromises the confidentiality of data.

It remains to determine if A sending
RSA-OAEP(data||shared_secret)
to B (computed with B's public key), and having B decipher (with B's private key) and verify shared_secret, is enough for insuring integrity and authenticity of data; assuming of course, that no adversary could have learned shared_secret.

My answer is: no, that does not give the desired insurance of integrity and authenticity, at least for some possible ways of establishing or using shared_secret. In particular:

• If there was any prior use of shared_secret by any party knowing it, that involved sending
RSA-OAEP(something||shared_secret)
per B's public key, then poof goes the desired integrity and authenticity of data, because an adversary can reuse that cryptogram to abuse B into believing that data is that unrelated something.
• That includes if shared_secret is merely used for several iterations of the protocol involving different values of data.
• Independently, it is quite possible that the check B makes of that message can be used as an oracle to test shared_secret; if that is a password (as we are told), this is bad (though not nearly as bad as with the other protocol, because that's an online attack). Then, after shared_secret leaked, the sky is the limit.

On the other hand, if shared_secret was a wide secret of fixed length established by XOR of secrets chosen by authenticated parties, and RSA-OAEP(data||shared_secret) was the only time shared_secret is used other than as the key of a symmetric algorithm, then I see no reason why the objective would not be met. This is no insurance.

• Yes, RSA-OAEP(data||shared_secret) is only used once to verify that A is A. If I wish to re-use it, I'd do RSA-OAEP(data||shared_secret||128-bit-random). I believe that 128-bit random controlled by A will make attacks impossible. This 128-bit random is then used for encryption. The goal is to protect the shared secret to be attacked. To take it a step further I have first B send a 128 R that gets encrypted along with data, shared_secret and a random by B. RSA-OAEP(RB||data,shared_secret||RA). In practice a replay is not possible is it? data is small and all of it is less than 2048 bit. – user29359 Dec 8 '15 at 21:16
• Anyhow the goal was to authenticate just once, but I'd appreciate it if you could comment on my previous comment. – user29359 Dec 8 '15 at 21:21
• @lel: protocol analysis is hard even with a full description of the protocol, and the only firm conclusions that can be made with a partial description is that the protocol is insecure; thus without a full description, you'll only get conclusions of this kind. And, with the re-use assumption, I do not even get how the extended protocol resists better against any of the three bulleted attacks; thus I pass at further analysis. – fgrieu Dec 8 '15 at 21:33

The SHA-256 method is unsafe for the reason given in fgrieu's answer.

The other protocol is also unsafe, but not for the reason given in fgrieu's answer.
Concatentaion is not injective, so an adversary could guess multiple passwords with a
single ciphertext. ​ For example, 1||01 = 101 = 10||1, so if the adversary encrypts 111
and outputs the ciphertext, then both password = 1 and password = 01 would lead
to that ciphertext being accepted. ​ Similarly, a password of 101 or the empty string
would also lead to that ciphertext being accepted, and by encrypting longer things,
the adversary could make even more guesses with a single ciphertext.
Instead, you should use a pairing function, such as ​ pair(x,y) = prefixfree(x)||y ​ or
pair(x,y) ​ ​ ​ = ​ ​ ​ if ​ length(y) < length(x) ​ then ​ 1||prefixfree(y)||x ​ else ​ 0||prefixfree(x)||y ​ ​ ​ ​ ​ ​ ​ ​ .

There quite simply cannot be any non-interactive protocol that continues to provide authentication despite all "possible ways of establishing or using" their secrets - "if there was any prior use of" any given party's secrets by that party, that involved sending exactly what the protocol specifies should be sent [[when something is the plaintext] per the public information], "then poof goes
the desired integrity and authenticity of" the protocol, "because an adversary can reuse" what
was sent to abuse the other party into believing that the plaintext "is that unrelated something".
By default, one must be able to assume that secrets are only
used as specified in the protocol(s) under consideration.

• We are asked a question about a part of the protocol, with the rest unspecified; in that situation, I find it prudent to assume the worse. $\;$ I agree, of course, with your remark that concatenation is unsafe in the context. – fgrieu Dec 8 '15 at 21:05

How do you know that the message will not be replayed? Do the data contain a timestamp? If not then add it.

In principle, since I presume that your messages are structured even if you use the first version (with timestamps) then you should be ok. Please also be careful how you encode the data, do not use the by the book definition of RSA, there is specific RFC for that.

• Issue of replay is not a concern, there is a step above the step shown where Bob sends out a random number that is also encrypted in the message along with the shared secret. So, replay is not an issue since A & B will both send out their own nonces. B will send out a shared secret too. RSA is done using a good library not a homegrown one. – user29359 Dec 8 '15 at 8:53