Google CTF 2017 Quals - RSA CTF Challenge writeup
“Somebody used PKCS1v1.5 really insecurely. Can you exploit this?"
Following the link (pkcs-is-bad.ctfcompetition.com), we find a simple form asking us to submit a signature for the challenge text (which is actually just challenge). Viewing the source reveals some interesting snippets:
<!-- TODO: How can we make sure this is PKCS1v1.5/MD5? Also, we need to validate that it's base64. -->
Paste your signature here: <input id="pwd" type="text" value="" /><br/>
<!-- TODO: remove -->
<div id="adminPubKey" style="visibility:hidden">
-----BEGIN RSA PUBLIC KEY-----
MIGdMA0GCSqGSIb3DQEBAQUAA4GLADCBhwKBgQDXnmZBhgORgRu6gXwGplTHHIfV
Z1kXgC/o3cSDl8JbK14wMn3o3CPIlhbDFuyzapB3rkKcECP3uGKco4AoBf/CQDoH
ZJii5gL9YwXnUPul2wWCvTy2NyW0fkBpZwK85HtR4D6AwhHaCP6hhMPdj41spp4O
q6xbZ1E1zypmjToxVQIBAw==
-----END RSA PUBLIC KEY-----
</div>
Also, it appears that the form sends a POST request with the signature to the /check endpoint to get the flag:
<script>
$("#post").submit(function(event) {
event.preventDefault();
var request = JSON.stringify({"Signature": $('#pwd').val()});
$.post("/check", request,
function(data) {
var result = JSON.parse(data);
if(result.CheckSucceeded) {
$("#result").empty().append("Succeeded. Flag is: <kbd>" + result.Flag + "</kbd>");
} else {
$("#result").empty().append("Failed.");
}
}).fail(
function(response) {
console.log('Error: ' + response.responseText);
});
});
</script>
The page confusingly requests to sign the challenge with a public key, but it’s likely just a typo. From what the source says, the server expects a signed MD5 hash with PKCS#1 v1.5 padding, encoded in Base64. We also should check out that admin key, for example, saving it to a file and using the pycrypto library:
from Crypto.PublicKey import RSA
from Crypto.Util.number import size
key = RSA.importKey(open('admin.key').read())
print "N = %s" % key.n
print "e = %s" % key.e
print "N size is %s bits" % size(key.n)
(ctf) tr@karabut.com:~/work/googlectf17/crypto/pkcs_is_bad$ python check.py
N = 151412633855954843819733434464125339052568898102931536911637903559841544558723973043050816338485284590514808104500875340749604123632852946469150713976173372290733260940828083371874628381129699367481235628443486831633794198594140144657045371665601505687547633943899965976948544127536969540495613484548832768341
e = 3
N size is 1024 bits
Signing a message with RSA works like this: the message is hashed, the resulting hash is padded to the modulus size, following some kind of a padding scheme, then raised to the power of the private exponent d (modulo N) and passed to the other party for verification. The verification, then, consists of raising the signature to the power of the public exponent e modulo N, basically reversing it to the padded hash state, and checking the result. The hash here is MD5, and the padding (PKCS#1 v1.5) involves encoding the hash with ASN.1 and prepending it with the bytes 00 01 FF .. FF 00, with as many FF bytes as needed to get it to, in our case, 1024 bits, or 128 bytes.
But how would we go about signing the message without a private key?
Well, it turns out that as long as e is very small (and it is for us, 3 being one of the most popular sizes), and the PKCS#1 v1.5 implemenation of the verifying party is not entirely accurate, we could do exactly that. In 2006, Daniel Bleichenbacher described a method of forging RSA signatures when e equals 3, exploiting the fact that most implementations did not check that the padded message actually ended after the ASN.1/hash block; that is, when supplied with a fake signature which after the exponentiation - cubing, here - would form a correctly left-padded block, they would ignore everything else and accept it.
While Bleichenbacher demonstrated this with a 3072 bit key, further research followed, resulting in successful forging of 1024-bit signatures of MD5 and SHA-1 hashes; but the catch is, the paper assumes some control over the source message (they forge X.509 certificates, so the hash could be easily manipulated by bruteforcing, say, the expiration date value), and we have none. So when it comes to the requirement that there should be no less than 8 FF bytes of padding, we fail at finding a good cube root:
from Crypto.Signature import PKCS1_v1_5
from Crypto.Hash import MD5
from Crypto.Util.number import bytes_to_long, long_to_bytes, size
def true_cbrt(n):
lo = 0
hi = n
while lo < hi:
mid = (lo+hi)//2
if mid**3 < n:
lo = mid+1
else:
hi = mid
return lo
h = MD5.new("challenge")
print "MD5 of challenge: %s" % h.hexdigest()
print
padded = PKCS1_v1_5.EMSA_PKCS1_V1_5_ENCODE(h, 1024/8)
print "Real message:"
print padded.encode('hex')
print
asn1hash = padded.split("\xff\xff\xff\x00")[-1]
forged_prefix = "\x00\x01" + "\xff"*8 + "\x00"
forged = (forged_prefix + asn1hash).ljust(128, "\xff")
print "Desired forged message:"
print forged.encode('hex')
print
sig = true_cbrt(bytes_to_long(forged))
print "Closest forged message 1:"
print long_to_bytes(sig ** 3).rjust(128, "\x00").encode('hex')
print
sig -= 1
print "Closest forged message 2:"
print long_to_bytes(sig ** 3).rjust(128, "\x00").encode('hex')
print
(ctf) tr@karabut.com:~/work/googlectf17/crypto/pkcs_is_bad$ python check2.py
MD5 of challenge: b04ec0ade3d49b4a079f0e207d5e2821
Real message:
0001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff003020300c06082a864886f70d020505000410b04ec0ade3d49b4a079f0e207d5e2821
Desired forged message:
0001ffffffffffffffff003020300c06082a864886f70d020505000410b04ec0ade3d49b4a079f0e207d5e2821ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
Closest forged message 1:
0001ffffffffffffffff003020300c06082a864886f70d020505000410b04ec0ade3d49b4a079f0e207d5e2b9fb38ad1a65ad421ff2e1ec5cd7c1f08e7b24a683632a3377883325ec9fa1ee584503c4f4a43990d0b231cf65f09b41ee6e0563b4e8bfce030f0e4a67563d4660737514309417daaf5f8f259c38efe9cc2af8000
Closest forged message 2:
0001ffffffffffffffff003020300c06082a864886f70d020505000410b04ec0ade3d49b4a079f0e207d5e26dc93cbd621af7ba28474d3e8b8fc82e30ef8456f553a5cd76f02216e1b7e56069d537d9a4dfa400c500bbf4b79e1db124a8d4cc7ac481286a1033cee8a8e73e922f8e555f3187fe8bd714cfb531297e08e949f9f
As you can see, we narrowly miss our target here; it rests in between of our messages differing by 1, so we can’t do much more without reducing the number of FF bytes to six or less (which doesn’t work, too). So, maybe there could be something else wrong with the implementation?
As a matter of fact, indeed there could be. In 2016, Filippo Valsorda (@FiloSottile) wrote this article on the issue in python-rsa (later assigned CVE-2016-1494) - in short, while the part of the message following the hash wasn’t ignored, the bug allowed using any kind of byte being used instead of the FF padding as long as it wasn’t a zero.
Of course, the beginning of the message in that case could be simply 00 01 with no regard to the following bytes up to the very end, where the 34 bytes of the ASN.1 encoded MD5 hash would reside. So we could search for a value resulting in those 34 bytes when cubed (Filippo offers a simple algorithm for that, provided the hash value we need is odd - and luckily it is), and then combine it with a simple cube root for the prefix.
The only catch here is that we should check for null bytes in the padding output so it would still appear valid. Let’s do this just as lazily as Filippo did:
import os
import asn1
import requests
import base64
from Crypto.Signature import PKCS1_v1_5
from Crypto.Hash import MD5
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, long_to_bytes, size
def true_cbrt(n):
lo = 0
hi = n
while lo < hi:
mid = (lo+hi)//2
if mid**3 < n:
lo = mid+1
else:
hi = mid
return lo
def get_bit(n, pos):
return (1 if (n & (1 << pos)) else 0)
message = "challenge"
key = RSA.importKey(open('adminpub.key').read())
h = MD5.new(message)
padded = PKCS1_v1_5.EMSA_PKCS1_V1_5_ENCODE(h, size(key.n)/8)
asn1hash = "\x00" + padded.split("\xff\xff\xff\x00")[-1]
asn1hash_l = bytes_to_long(asn1hash)
# find the value resulting in ASN.1 + hash suffix when cubed
sig_suffix = 1
for bit_pos in range(len(asn1hash) * 8):
if get_bit(sig_suffix ** 3, bit_pos) != get_bit(asn1hash_l, bit_pos):
sig_suffix ^= (1 << bit_pos) # flip the incorrect bit
if not long_to_bytes(sig_suffix ** 3).endswith(asn1hash):
raise
print "Signature suffix found"
print
# combine the cube roots checking for null bytes
while True:
prefix = bytes_to_long("\x00\x01" + os.urandom(1024/8 - 2))
sig_prefix = long_to_bytes(true_cbrt(prefix))[:-len(asn1hash)]
sig = sig_prefix + long_to_bytes(sig_suffix)
if "\x00" not in long_to_bytes(bytes_to_long(sig) ** 3)[:-len(asn1hash)]:
break
print "Full signature obtained"
print
print "Resulting padded message:"
print long_to_bytes(bytes_to_long(sig) ** 3).encode('hex')
print
sig = sig.rjust(128, "\x00")
sig = base64.b64encode(sig)
r = requests.post("http://pkcs-is-bad.ctfcompetition.com/check", json={"Signature":sig})
print r.text
(ctf) tr@karabut.com:~/work/googlectf17/crypto/pkcs_is_bad$ python solve.py
Signature suffix found
Full signature obtained
Resulting padded message:
01106e9c552b4e23f4d58c06eda3ee461960984a7c485cb0c5fef4092bee3330c27831be68a6919be4c2944237aa2865d67a071e7a9f8b69bda0297e09025d5dc4a9169f4742bc1b05133274165b4bb76e6504d8f42e4efcebde70aa003020300c06082a864886f70d020505000410b04ec0ade3d49b4a079f0e207d5e2821
{"CheckSucceeded" : 1, "Flag" : "CTF{zx2fn265ll7}"}
And that’s our flag right there!