From 247683ead3c714b5869b5fa2fb62c03dc2b00f0d Mon Sep 17 00:00:00 2001 From: dusoleil Date: Sun, 1 Aug 2021 23:19:55 -0400 Subject: Writeups from Imaginary CTF 2021 Adding Dusoleil's writeups from Imaginary CTF 2021 Signed-off-by: dusoleil --- .../ImaginaryCTF_2021/rock_solid_algorithm.txt | 98 ++++++++++++++++++++++ 1 file changed, 98 insertions(+) create mode 100644 docs/writeups/ImaginaryCTF_2021/rock_solid_algorithm.txt (limited to 'docs/writeups/ImaginaryCTF_2021/rock_solid_algorithm.txt') diff --git a/docs/writeups/ImaginaryCTF_2021/rock_solid_algorithm.txt b/docs/writeups/ImaginaryCTF_2021/rock_solid_algorithm.txt new file mode 100644 index 0000000..efce1a7 --- /dev/null +++ b/docs/writeups/ImaginaryCTF_2021/rock_solid_algorithm.txt @@ -0,0 +1,98 @@ +The Problem +----------- +we're given a text file with three numbers labeled n, e, and c. This looks like an RSA problem where we need to crack the ciphertext c. e is only 5, which looks like this may be a small exponent attack. Normally, e would be something like 65537 = 0x10001 + + + +The Small Exponent Attack +------------------------- +Most documentation online about small exponent attacks talk about e=3, but it should be the same for e=5. Note that this doesn't necessarily mean c will be easy to crack, just that it might be. Because of this, when my original attempt during the competition didn't work, I assumed it must be something else and just moved on. After seeing writeups say that it was, in fact, a small exponent attack, I assumed that I must have made a typo or mistake somewhere in the math and went back to solve it after the fact. + +The idea behind a small exponent attack is that our ciphertext c is calculated from plaintext p with exponent e and modulo n + + c = (p**e)%n + +which would mean that + + (p**e) = c + (k * n) + +for some k. Obviously we don't know what that k is, and it could be very large if p was big enough. A higher e makes it much more likely that k would be extremely large, but since e is so small, there is a chance that we can find (p**e) with only a few iterations trying increasing values for k. + +That alone isn't enough, though, as we have no way to know directly if the (p**e) we calculate for a given k is the correct one. For that, we need to calculate the e-th root of (p**e) to get p and check if a) that root even exists and b) if that p is our flag or some other random value that happens to work. For my attack, I only ever actually checked if the root existed as I figured if I found a false positive I could just fix the code then. + + + +e-th Root In Python +------------------- +Now the hard part is calculating the e-th root of (p**e). There are a number of math tools that can do this for us, but I didn't feel like relearning sagemath or NumPy, so I was trying to just deal with it myself in pure python. As it turns out, there are tons of little hiccups that make this pretty annoying. + +First, for a t = (p**e), p = t**(1/e) will try to convert t into a float and fail because the int is too large. So we can't just do that. + +Instead, I decided to write a binary search over range(0,t) which would calculate i**e and check it against t. This is a pretty decently fast way to search for an e-th root. + +I wrote a generic binary search function which I figured I could reuse later for something else. I did it recursively originally, but python had a fit when my numbers were too large and it hit the recursion limit. So I had to rewrite it as a loop instead. + +I also ran into various issues with keeping it generic and dealing with large numbers. For instance, len(range(0,really_big_number)) throws an exception that that int would be too large for a C ssize_t. So I had to add the ability to define custom start and end points in the iterable. + +The final code looks like this: + +``` +#binary search +#searches for an s in i that satisfies x == f(i[s]) +#i = iterable +#f = function to call on each element of i +#x = value to search for +#start = offset into iterable to start +#end = offset into iterable to end +#if it finds a match, it returns a tuple of (s,i[s],f(i[s])) +#if it does not find a match, it returns (-1,None,None) +def bsearch(i,f,x,start=0,end=-1): + if end == -1: + end = len(i)-1 + #s = _bsearch(i,f,start,end,x) + s = _bsearch2(i,f,start,end,x) + return (s,i[s],f(i[s])) if s != -1 else (s,None,None) + +#recursive +def _bsearch(i,f,lo,hi,x): + if hi >= lo: + md = (hi+lo)//2 + a = f(i[md]) + if a == x: + return md + elif a > x: + return _bsearch(i,f,lo,md-1,x) + else: + return _bsearch(i,f,md+1,hi,x) + else: + return -1 + +#loop +def _bsearch2(i,f,lo,hi,x): + while True: + if hi >= lo: + md = (hi+lo)//2 + a = f(i[md]) + if a == x: + return md + elif a > x: + hi = md-1 + else: + lo = md+1 + else: + return -1 + +def small_e_attack(c,e,n,kend=100): + for k in range(1,kend): + t = c + (k*n) + p = bsearch(range(1,t),lambda p: p**e,t,end=t-2)[1] + if p != None: + print(p.to_bytes(40,'big').decode()) + break; +``` + +and then we can just call + + small_e_attack(c,e,n) + +and it prints the flag -- cgit v1.2.3