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.

$\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 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 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 at 23:02

2 Answers 2

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

$\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 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 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 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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