Whitfield Diffie and Martin Hellman's 1976 paper "New Directions in Cryptography" heralded a huge leap forward for the field of cryptography. The paper defined the concepts of public-key cryptosystems, one-way trapdoor functions, and digital signatures, and described a key-exchange method for securely sharing secrets over an insecure channel. Although these were independently discovered at GCHQ some years earlier, Diffie and Hellman were first to share this landmark knowledge with the world.
The Diffie-Hellman key exchange (DH) is central to the security of the internet today. As part of the TLS handshake, it's typically used to securely compute a shared AES encryption key over the internet between a web browser and server. Although several other algorithms can be used for key exchange, DH is the only option available in the latest revision of the TLS spec (1.3), showing how it's held up over the years. This is mainly due to how easily DH can be adapted to support "forward secrecy", which we'll discuss more below.
DH relies on the assumption that the discrete logarithm problem (DLP) is difficult to solve. However, in practice the parameters need to be chosen carefully or the discrete logarithm can be easy to crack, which we'll explore in these challenges. Furthermore, the most basic version of the protocol is vulnerable to a man-in-the-middle attack, showing how DH requires careful authentication of who you are talking to.
The set of integers modulo n
, together with the operations of both addition and multiplication is a ring. This means that adding or multiplying any two elements in the set returns another element in the set.
When the modulus is prime: n = p
, we are guaranteed an inverse of every element in the set, and so the ring is promoted to a field. We refer to this field as a finite field F_{p}
.
The Diffie-Hellman protocol works with elements of some finite field F_{p}
, where the prime modulus is typically a large prime.
Given the prime p = 991
, and the element g = 209
, find the inverse element d
such that g * d mod 991 = 1
.
You must be logged in to submit your flag.
Every element of a finite field F_{p}
can be used to make a subgroup H
under repeated action of multiplication. In other words, for an element g
: H = {g, g^2, g^3, ...}
A primitive element of F_{p}
is an element whose subgroup H = F_{p}
, i.e., every element of F_{p}
, can be written as g^n mod p
for some integer n
. Because of this, primitive elements are sometimes called generators of the finite field.
For the finite field with p = 28151
find the smallest element g
which is a primitive element of F_{p}
.
This problem can be solved by brute-force, but there's also clever ways to speed up the calculation.
You must be logged in to submit your flag.
The Diffie-Hellman protocol is used because the discrete logarithm is assumed to be a "hard" computation for carefully chosen groups.
The first step of the protocol is to establish a prime p
and some generator of the finite field g
. These must be carefully chosen to avoid special cases where the discrete log can be solved with efficient algorithms. For example, a safe prime p = 2*q +1
is usually picked such that the only factors of p - 1
are {2,q}
where q
is some other large prime. This protects DH from the Pohligâ€“Hellman algorithm.
The user then picks a secret integer a < p
and calculates g^a mod p
. This can be transmitted over an insecure network and due to the assumed difficulty of the discrete logarithm, the secret integer should be infeasible to compute.
Given the NIST parameters:
g: 2
p: 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
Calculate the value of g^a mod p
fora: 972107443837033796245864316200458246846904598488981605856765890478853088246897345487328491037710219222038930943365848626194109830309179393018216763327572120124760140018038673999837643377590434413866611132403979547150659053897355593394492586978400044375465657296027592948349589216415363722668361328689588996541370097559090335137676411595949335857341797148926151694299575970292809805314431447043469447485957669949989090202320234337890323293401862304986599884732815
You must be logged in to submit your flag.
Now it's time to calculate a shared secret using data received from your friend Alice. Like before, we will be using the NIST parameters:
g: 2
p: 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
You have received the following integer from Alice:
A: 70249943217595468278554541264975482909289174351516133994495821400710625291840101960595720462672604202133493023241393916394629829526272643847352371534839862030410331485087487331809285533195024369287293217083414424096866925845838641840923193480821332056735592483730921055532222505605661664236182285229504265881752580410194731633895345823963910901731715743835775619780738974844840425579683385344491015955892106904647602049559477279345982530488299847663103078045601
You generate your secret integer b
and calculate your public one B
, which you send to Alice.b: 12019233252903990344598522535774963020395770409445296724034378433497976840167805970589960962221948290951873387728102115996831454482299243226839490999713763440412177965861508773420532266484619126710566414914227560103715336696193210379850575047730388378348266180934946139100479831339835896583443691529372703954589071507717917136906770122077739814262298488662138085608736103418601750861698417340264213867753834679359191427098195887112064503104510489610448294420720
B: 518386956790041579928056815914221837599234551655144585133414727838977145777213383018096662516814302583841858901021822273505120728451788412967971809038854090670743265187138208169355155411883063541881209288967735684152473260687799664130956969450297407027926009182761627800181901721840557870828019840218548188487260441829333603432714023447029942863076979487889569452186257333512355724725941390498966546682790608125613166744820307691068563387354936732643569654017172
You and Alice are now able to calculate a shared secret, which would be infeasible to calculate knowing only {g,p,A,B}
.
What is your shared secret?
You must be logged in to submit your flag.
Alice wants to send you her secret flag and asks you to generate a shared secret with her. She also tells you she will be using the NIST standard:
g: 2
p: 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
You receive the following integer from Alice:
A: 112218739139542908880564359534373424013016249772931962692237907571990334483528877513809272625610512061159061737608547288558662879685086684299624481742865016924065000555267977830144740364467977206555914781236397216033805882207640219686011643468275165718132888489024688846101943642459655423609111976363316080620471928236879737944217503462265615774774318986375878440978819238346077908864116156831874695817477772477121232820827728424890845769152726027520772901423784
You then generate your secret integer and calculate your public one, which you send to Alice.b: 197395083814907028991785772714920885908249341925650951555219049411298436217190605190824934787336279228785809783531814507661385111220639329358048196339626065676869119737979175531770768861808581110311903548567424039264485661330995221907803300824165469977099494284722831845653985392791480264712091293580274947132480402319812110462641143884577706335859190668240694680261160210609506891842793868297672619625924001403035676872189455767944077542198064499486164431451944
B: 1241972460522075344783337556660700537760331108332735677863862813666578639518899293226399921252049655031563612905395145236854443334774555982204857895716383215705498970395379526698761468932147200650513626028263449605755661189525521343142979265044068409405667549241125597387173006460145379759986272191990675988873894208956851773331039747840312455221354589910726982819203421992729738296452820365553759182547255998984882158393688119629609067647494762616719047466973581
Individually you each use the shared secret to derive an AES private key. This allows you to encrypt large amounts of data over your channel without needing to exchange keys again.
Alice sends you the following IV and ciphertext:{'iv': '737561146ff8194f45290f5766ed6aba', 'encrypted_flag': '39c99bf2f0c14678d6a5416faef954b5893c316fc3c48622ba1fd6a9fe85f3dc72a29c394cf4bc8aff6a7b21cae8e12c'}
Decrypt this to obtain your flag!
The decrypt.py
script is provided to help you here and on future challenges too.
Challenge files:
- source.py
- decrypt.py
You must be logged in to submit your flag.
You're in a position to not only intercept Alice and Bob's DH key exchange, but also rewrite their messages. Think about how you can play with the DH equation that they calculate, and therefore sidestep the need to crack any discrete logarithm problem.
Use the script from "Diffie-Hellman Starter 5" to decrypt the flag once you've recovered the shared secret.
Connect at socket.cryptohack.org 13371
You must be logged in to submit your flag.
Alice and Bob are using legacy codebases and need to negotiate parameters they both support. You've man-in-the-middled this negotiation step, and can passively observe thereafter. How are you going to ruin their day this time?
Connect at socket.cryptohack.org 13379
You must be logged in to submit your flag.
You've just finished eavesdropping on a conversation between Alice and Bob. Now you have a chance to talk to Bob. What are you going to say?
Connect at socket.cryptohack.org 13373
You must be logged in to submit your flag.
Alice and Bob decided to do their DHKE in an additive group rather than a multiplicative group. What could go wrong?
Use the script from "Diffie-Hellman Starter 5" to decrypt the flag once you've recovered the shared secret.
Connect at socket.cryptohack.org 13380
You must be logged in to submit your flag.
Bob got a bit more careful with the way he verifies parameters. He's still insisting on using the p and g values provided by his partner. Wonder if he missed anything?
Connect at socket.cryptohack.org 13378
You must be logged in to submit your flag.
Found this cool script on Github and I've been using it to keep my secrets from anyone listening in on the school wifi!
Challenge files:
- script.py
- output.txt
You must be logged in to submit your flag.
I must get out of here. I must get free, and in this mind is the key, my key!
Challenge files:
- the_matrix.sage
- flag.enc
Challenge contributed by jschnei
You must be logged in to submit your flag.
It's happening exactly as before... Well, not exactly.
Challenge files:
- matrix_reloaded.zip
Challenge contributed by jschnei
You must be logged in to submit your flag.
Everything that has a beginning has an end, Neo.
Challenge files:
- matrix_revolutions.zip
Challenge contributed by jschnei
You must be logged in to submit your flag.
You are now level Current level