0
$\begingroup$

Scenario: Alice and Bob send each other encrypted AES (128) messages. In order to change key, Alice has a public RSA key (2049 bits). Bob has Alice's public key.

Bob picks a random AES key, encrypts it, and sends it to Alice. Alice decrypts the RSA encryption, if the result is bigger than 2^128, Alice assumes an error occurred and sends an error message to Bob.

Eve performs a man in the middle attack. Eve can change any message and avoid messages to reach their destination. Eve can't change Bob's and Alice's RSA keys.

How Eve can find the most significant bit in the AES key that Bob sent?

I got a hint:

let $c = m^e \bmod n$. The decryption of $c\cdot a^e \bmod n$ is $m\cdot a \bmod n$. That's because decryption of $m^e\cdot a^e \bmod n$ is $(m^e \cdot a^e)^d \bmod n$ when $e\cdot d \bmod \varphi(n)=1$.

So I assume Eve can modify Bob's encrypted message $c$ and multiply it with $a^e \bmod n$.

If Alice sent an error message so we can know that $(m\cdot a \bmod n)\ge 2^{128}$.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Guessing that this is homework, here your hint as out HW policy. Hint: what will happen to a 128-bit multiplied with 2? Is it 129-bit or 128-bit? $\endgroup$
    – kelalaka
    Jan 6, 2021 at 22:55
  • $\begingroup$ @kelalaka Ssshl! $\endgroup$
    – Maarten Bodewes ♦
    Jan 6, 2021 at 23:06
  • 1
    $\begingroup$ Note: for this reason, and others, when good practitioners RSA-encrypt something, they do not use textbook RSA as in the question. They use RSAES-OAEP. Additional hint: that also works when $a$ is a fraction whose denominator is coprime with $n$. There's a fine line between numerator and denominator, but only a fraction of the audience gets it. $\endgroup$
    – fgrieu ♦
    Jan 7, 2021 at 6:46
  • $\begingroup$ Have you found the solution? If so, please delete the question; or make and accept an answer. Further note: I fixed an off-by-one in the last equation. Eve actually substitutes $c$ with $c'\gets c\cdot(a^e \bmod n)\bmod n$. She can find the AES key with about a hundred queries and appropriate $a$. Other (very different) attacks are possible that need no query, but only work for a sizable fraction of $a$, and require in the order of $2^{68}$ modular multiplications. $\endgroup$
    – fgrieu ♦
    Jan 7, 2021 at 17:15

1 Answer 1

Reset to default
1
$\begingroup$

I am assuming you meant to use a=2, so that if it sends an error message, we know that MCB was 1. Anyway RSA in practice is never used in raw form like this precisely because this malleability allows attacks like you just mentioned. Such malleability also allows an attacker to create fake signatures from an oracle and with good padding, we cannot trick any RSA decryption oracle into signing some message while it thinks it was decrypting something which would be possible if RSA was used raw.

Improve this answer
$\endgroup$
4
  • $\begingroup$ What you describe finds the top bit. When that bit is 0, it's easy to get the next one. But how to proceed if we conclude that the top bit is a 1? $\endgroup$
    – fgrieu ♦
    Jan 7, 2021 at 17:24
  • $\begingroup$ I think the OP asked only about finding MCB. You are right, we can find out the number of 0's in the prefix, by repeatedly querying multiplying with each with 2. $\endgroup$
    – Manish Adhikari
    Jan 7, 2021 at 17:30
  • $\begingroup$ I don't know how to proceed after encountering a 1 tho. $\endgroup$
    – Manish Adhikari
    Jan 7, 2021 at 17:38
  • $\begingroup$ Why do you need to proceed? The question is "how can we determine the msbit"; once you've done that, you've answered the problem that was asked. What, are you going for extra credit??? If you are, then try this to obtain additional information: how can you determine the lsbit? $\endgroup$
    – poncho
    Jan 8, 2021 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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