## Diffie-Hellman

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.

#### Starter

Toggle
• Working with Fields
10 pts ·
The set of integers modulo $N$, together with the operations of both addition and multiplication forms a ring $\mathbb{Z}/ N\mathbb{Z}$. Fundamentally, 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 additionally guaranteed a multiplicative inverse of every element in the set, and so the ring is promoted to a field. In particular, we refer to this field as a finite field denoted $\Fp$.

The Diffie-Hellman protocol works with elements of some finite field $\Fp$, where the prime modulus is typically very large (thousands of bits), but for the following challenges we will keep numbers smaller for compactness.

Given the prime $p = 991$, and the element $g = 209$, find the inverse element $d = g^{-1}$ such that $g \cdot d \mod 991 = 1$.

You must be logged in to submit your flag.

• Generators of Groups
20 pts · 4889 Solves
Every element of a finite field $\Fp$ can be used to make a subgroup $H$ under repeated action of multiplication. In other words, for an element $g$ the subgroup $H = \langle g \rangle = \{g, g^2, g^3, \ldots \}$

A primitive element of $\Fp$ is an element whose subgroup $H = \Fp^*$, i.e., every non-zero element of $\Fp$, 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 $\Fp$.

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.

• Computing Public Values
25 pts · 4989 Solves
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 \cdot 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 - 1$ 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. The value $a$ is known as the secret value, while $A = g^a \mod p$ is the public value.

Given the NIST parameters:

g: 2
p: 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919

Calculate the value of $g^a \mod p$ for

a: 972107443837033796245864316200458246846904598488981605856765890478853088246897345487328491037710219222038930943365848626194109830309179393018216763327572120124760140018038673999837643377590434413866611132403979547150659053897355593394492586978400044375465657296027592948349589216415363722668361328689588996541370097559090335137676411595949335857341797148926151694299575970292809805314431447043469447485957669949989090202320234337890323293401862304986599884732815

You must be logged in to submit your flag.

• Computing Shared Secrets
30 pts · 4773 Solves
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 value $B = g^b \mod p$, which you send to Alice.

b: 12019233252903990344598522535774963020395770409445296724034378433497976840167805970589960962221948290951873387728102115996831454482299243226839490999713763440412177965861508773420532266484619126710566414914227560103715336696193210379850575047730388378348266180934946139100479831339835896583443691529372703954589071507717917136906770122077739814262298488662138085608736103418601750861698417340264213867753834679359191427098195887112064503104510489610448294420720
B: 518386956790041579928056815914221837599234551655144585133414727838977145777213383018096662516814302583841858901021822273505120728451788412967971809038854090670743265187138208169355155411883063541881209288967735684152473260687799664130956969450297407027926009182761627800181901721840557870828019840218548188487260441829333603432714023447029942863076979487889569452186257333512355724725941390498966546682790608125613166744820307691068563387354936732643569654017172

Try and compute $B$ yourself and verify things are working using the values above.

You and Alice are now able to calculate a shared secret by using your secret values $a, b$ with each others public values $B, A$. Note that computing this shared value is infeasible knowing only $\{g,p,A,B\}$, it's the knowledge of $a, b$ which allows the generation of the shared value.

You must be logged in to submit your flag.

• Deriving Symmetric Keys
40 pts · 4273 Solves
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.

#### Man In The Middle

Toggle
• Parameter Injection
60 pts · 3274 Solves
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 "Deriving Symmetric Keys" 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.

100 pts · 2727 Solves
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.

• Static Client
100 pts · 1376 Solves
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.

#### Group Theory

Toggle
70 pts · 1536 Solves
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 "Deriving Symmetric Keys" 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.

• Static Client 2
120 pts · 923 Solves
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.

Toggle

### Level Up

You are now level Current level