Διαγωνισμός Hack the Boo-Crypto writeups

Ο διαγωνισμός Hack the Boo του Hack the Box φέτος, είχε ενδιαφέρουσες δοκιμασίες Crypto και σκέφτηκα να μοιραστώ μαζί σας τις λύσεις που βρήκα σε ορισμένες από αυτές για να μου πείτε τις σκέψεις σας (δεν ξέρω αν είναι αποτυπωμένα με απολύτως ορθό τρόπο από μαθηματική άποψη).

Για τις δοκιμασίες χρειάζονται υπολογισμοί που τους έκανα με την βιβλιοθήκη της  python gmpy2 . Βέβαια, εφόσον κάποιος κατανοήσει τη λογική, μπορεί να χρησιμοποιήσει ό,τι γλώσσα και βιβλιοθήκες θέλει. Σημαντικό είναι να θυμάται κανείς ότι πρέπει να επιλέξει κάποιο εργαλείο που να υποστηρίζει μεγάλη ακρίβεια στους υπολογισμούς με πολύ μεγάλους αριθμούς.

Spooky RSA

Σύμφωνα με τον κώδικα Python της δοκιμασίας:

Ν= p*q που είναι πρώτοι αριθμοί και

f=priv[0] άρα f=p

Επίσης:

c1=((f^e1 mod N) +m ) mod N και 

c2=((f^e1 mod N) +m ) mod N

Η δοκιμασία μας δίνει τα N, e1, e2, c1 και c2 που μπορούμε να τα βρούμε στο αρχείο out.txt

Από τη θεωρία ξέρουμε τα εξής:

1.(a+b) mod N= ((a mod N) + (b mod N) ) mod N και

2.a mod N =b mod N ⇔ (a+k) mod N= (b+k) mod N 

άρα:

Αφού f=p έχουμε:

c1=(p^e1 mod N) +(m  mod N) και 

c2=(p^e1 mod N) +(m  mod N)

Εφαρμόζοντας την ιδιότητα (1) έχουμε:

c1=(p^e1 mod N) +(m  mod N) και 

c2=(p^e1 mod N) +(m  mod N)

και

Εφαρμόζοντας την ιδιότητα (2) έχουμε:

c1-c2 = (p^e1 mod N) +(m  mod N) -(p^e1 mod N) -(m  mod N) ⇔ c1-c2=(p^e1 mod N) -(p^e1 mod N) ⇔ c1-c2=(p^e1-p^e2) mod N⇔ c1-c2=p(p^e1-1-p^e2-1)<=> (c1-c2)/p= κάποιος ακέραιος αριθμός

Συνεπώς το p είναι διαιρέτης της διαφοράς c1-c2 ΚΑΙ επίσης, ο p είναι διαιρέτης του N

ΑΡΑ το p είναι ο μέγιστος κοινός διαιρέτης του c1-c2 και του Ν

Με αυτόν τον τρόπο βρίσκουμε εύκολα τον p.

Στη συνέχεια, αφού βρούμε το p το βάζουμε στα 

c1=(p^e1 mod N) +(m  mod N) και 

c2=(p^e1 mod N) +(m  mod N)

και βρίσκουμε το m. Το μετατρέπουμε με long_to_bytes (που το συμπληρώνουμε για να το κάνουμε import στην αρχή από το Crypto.Util.number)  και βρίσκουμε την απάντηση

Gonna-Lift-Em-All

Σύμφωνα με τον κώδικα python της δοκιμασίας:

s = h^y mod p

c1=g * y mod p και 

c2= m * s mod p

Η δοκιμασία μας δίνει τα p, g, h, c1 και c2 που μπορούμε να τα βρούμε στο αρχείο data.txt

Από τη θεωρία ξέρουμε τα εξής:

If a x ≡ b (mod n) and a is coprime to n, then the solution to this linear congruence is given by x ≡ a^–1b (mod n)

Για να είμαστε σίγουροι, χρησιμοποιούμε τη βιβλιοθήκη gmpy2 της python που πραγματοποιεί υπολογισμούς με μεγάλη ακρίβεια. Η βιβλιοθήκη αυτή έχει ακριβώς μία συνάρτηση γι αυτή τη δουλειά:

divm()

divm(a, b, m) returns x such that b * x == a modulo m. Raises a ZeroDivisionError exception if no such value x exists.

Αρχικά βρίσκουμε το y με την συνάρτηση divm().

Μετά χρησιμοποιούμε το y  για να βρούμε το s και τέλος το s για να βρούμε το m.

Μετατρέπουμε το m με το long_to_bytes (που το συμπληρώνουμε για να το κάνουμε import στην αρχή από το Crypto.Util.number) και βρίσκουμε την απάντηση

Fast Carmichael

Σε αυτή τη δοκιμασία το βασικό πρόβλημα είναι να βρούμε έναν αριθμό που ΔΕΝ είναι πρώτος, αλλά ταυτόχρονα περνάει το primality test Miller-Robin, όπως θα εξηγήσουμε παρακάτω.

Σύμφωνα με τον κώδικα, στη συνάρτηση main(s) βλέπουμε ότι μόλις θα συνδεθούμε με τον server, θα μας ζητήσει να δώσουμε κάποιο input p που πρέπει να είναι int. Στη συνέχεια θα μας δώσει τη σημαία εάν πληρούνται δύο προϋποθέσεις, if _isPrime(p) and not isPrime(p):

1) το p δεν πρέπει να είναι πρώτος αριθμός  ( not isPrime(p) ) και 

2) το p πρέπει να πληροί τα κριτήρια της συνάρτησης _isPrime(p) που έχει ο κώδικας λίγο πιο πάνω

Η συνάρτηση _isPrime(p) έχει δύο κρίτηρια:

1. ο p πρέπει να είναι μεγαλύτερος από το 1 (p>1)

2. ο p πρέπει να είναι ένας αριθμός που να πληροί τα κριτήρια της συνάρτησης millerRabin() που έχει παραπάνω στον κώδικα

Το όνομα μας θυμίζει το Miller–Rabin primality test δηλαδή μια συνάρτηση που πιθανολογεί εάν ένας αριθμός είναι πρώτος. Η συνάρτηση millerRabin() του κώδικα είναι ουσιαστικά η μετατροπή σε python του ψευδοκώδικα στο παραπάνω link άρα πρόκειται για το ίδιο πράγμα.

Συνεπώς, είναι πλέον είναι προφανές ότι πρέπει να βρούμε έναν πολύ μεγάλο αριθμό (βλ, ότι καλείται η συνάρτηση generate_basis(300)), που αφενός μεν ΔΕΝ είναι πρώτος, αλλά ταυτόχρονα περνάει το primality test της μεθόδου Miller-Rabin. Τέτοιοι αριθμοί είναι οι Carmichael number.

Πράγματι, στην υποσημείωση b του άρθρου της wikipedia για το Miller-Rabin primality test βλέπουμε ότι:

For instance, in 1995, Arnault gives a 397-digit composite number for which all bases less than 307 are strong liars; this number was reported to be prime by the Maple isprime() function, because it implemented the Miller–Rabin test with the specific bases 2, 3, 5, 7 and 11.

και το link για το συγκεκριμένο άρθρο το οποίο το αφήνω για όποιον θέλει να ψάξει το ζήτημα πιο βαθιά.

Για τις ανάγκες της συγκεκριμένης δοκιμασίας, η λύση βρίσκεται απευθείας στο άρθρο της wiki για τα Carmichael numbers. Αυτοί είναι ψευδοπρώτοι αριθμοί οι οποίοι περνούν, μεταξύ άλλων και το Miller–Rabin primality test. Εκεί βρίσκει κανείς έτοιμα τα στοιχεία που χρειάζεται προκειμένου να λύσει τη δοκιμασία, δηλαδή  για να υπολογίσει τέτοιο αριθμό, όπως έκανε ο Arnault: