Score:2

Crypto

Help with RSA CTF question

jdkleuver

7/30/23, 4:48 AM

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.

151

0 + 0

rsa

attack

jdkleuver

7/30/23, 5:02 AM

This question seems related https://crypto.stackexchange.com/questions/80087/short-padding-known-prefix-rsa-attack But the answer to that question doesn't seem to help because it relies on two ciphertext created with the same modulus.

fgrieu

7/30/23, 9:03 AM

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).

jdkleuver

7/30/23, 11:02 PM

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.

Score:2

Crypto

poncho

7/30/23, 12:23 PM

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

0 + 0

fgrieu

7/30/23, 6:58 PM

But that's not RSA! :-) And if `Crypto.PublicKey.RSA.generate`is somewehat passed using $e$ (as it should), it shouldn't let this happen. Definitely worth checking.

jdkleuver

7/30/23, 10:56 PM

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.

jdkleuver

7/30/23, 11:48 PM

What you were hinting at with this answer was actually the intended solution from the CTF author.

Score:0

Crypto

jdkleuver

7/30/23, 11:14 PM

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.

0 + 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Help with RSA CTF question

TH: ความช่วยเหลือเกี่ยวกับคำถาม RSA CTF

RO: Ajutor cu întrebarea RSA CTF

RU: Помогите с вопросом RSA CTF

VI: Trợ giúp với câu hỏi RSA CTF

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.