2
$\begingroup$

I'm trying to solve a CTF problem relating to RSA encryption.

I can run a challenge binary that will read a flag from a file, the flag will match the following RegEx:

AB1234C\{[0-9a-f]{32}\}\n

So in total the flag is 42 bytes including the newline

The flag is then padded with random padding to a total of 128 bytes.

I can choose the public exponent e, as long as e>1. The binary will generate a random 2048 bit modulus using the python function Crypto.PublicKey.RSA.generate(bits=2048)

The binary will print out the modulus as well as the ciphertext of the encrypted padded flag.

I can run the binary multiple times, the modulus and padding will be different between each run.

I thought it could be related to Hastad's attack but that only appears to work for linear padding, and Coppersmith's short pad attack only works if you have two messages with random padding but encrypted with the same modulus, which I don't have here due to the fact that a different modulus is generated each time I run the binary.

I'm still a beginner when it comes to crypto so I might have been wrong about those attacks and may have missed something obvious.

I believe that the vulnerability could be relating to the size of the padding, as the padded message is only half of the length of the modulus.

I don't necessarily want the solution, but just a nudge in the right direction. Thanks.

Improve this question
$\endgroup$
3
  • $\begingroup$ This question seems related crypto.stackexchange.com/questions/80087/… But the answer to that question doesn't seem to help because it relies on two ciphertext created with the same modulus. $\endgroup$
    – jdkleuver
    Mar 30, 2022 at 5:02
  • 1
    $\begingroup$ Being a CTF, the question is borderline on-topic, and perhaps will be answered by hints. That said: with no stated way to reuse a modulus and 22 bytes of random padding, I can't think of a solution. I'd look at the code doing the padding to see if it does as advertised; and at the code doing the generation to see if it uses the specified $e$ (the code extract in the question does not). $\endgroup$
    – fgrieu ♦
    Mar 30, 2022 at 9:03
  • $\begingroup$ I can't share the source code as it is a private CTF, but I can confirm that when the modulus is generated it does not pass the e value as an argument, only the bits argument is passed. $\endgroup$
    – jdkleuver
    Mar 30, 2022 at 23:02

2 Answers 2

Reset to default
2
$\begingroup$

This is a CTF, and so I've just give a hint.

I can choose the public exponent e, as long as e>1

Can we pick an $e$ that makes this easy from a single query? Consider:

... to a total of 128 bytes

The binary will generate a random 2048 bit modulus

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ But that's not RSA! :-) And if Crypto.PublicKey.RSA.generateis somewehat passed using $e$ (as it should), it shouldn't let this happen. Definitely worth checking. $\endgroup$
    – fgrieu ♦
    Mar 30, 2022 at 18:58
  • $\begingroup$ Can confirm that the Crypto.PublicKey.RSA.generate is not passed using e, so I guess you are onto something there. The only argument is 'bits' so the e value generated by Python is ignored, only the n is used. $\endgroup$
    – jdkleuver
    Mar 30, 2022 at 22:56
  • $\begingroup$ What you were hinting at with this answer was actually the intended solution from the CTF author. $\endgroup$
    – jdkleuver
    Mar 30, 2022 at 23:48
0
$\begingroup$

So after reading @fgrieu comment I looked at the padding scheme again and realised that it is actually deterministic not random as I thought. I just solved it using Hastad's attack, so it was in fact a weakness of the padding. My apologies for the incorrectly stated question.

Improve this answer
$\endgroup$

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.