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 · 9156 Solves
    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$.

  • Generators of Groups
    20 pts · 7893 Solves · 25 Solutions
    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.

  • Computing Public Values
    25 pts · 7974 Solves · 6 Solutions
    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

  • Computing Shared Secrets
    30 pts · 7613 Solves · 12 Solutions
    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.

    What is your shared secret?

  • Deriving Symmetric Keys
    40 pts · 6812 Solves · 8 Solutions
    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

Man In The Middle

 Toggle
  • Parameter Injection
    60 pts · 5389 Solves · 22 Solutions
    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

  • Export-grade
    100 pts · 4621 Solves · 19 Solutions
    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

  • Static Client
    100 pts · 2274 Solves · 11 Solutions
    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

Group Theory

 Toggle
  • Additive
    70 pts · 2458 Solves · 12 Solutions
    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

  • Static Client 2
    120 pts · 1606 Solves · 15 Solutions
    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

Misc

 Toggle

Level Up

level up icon

You are now level Current level