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
  • Diffie-Hellman Starter 1
    10 pts · 2875 Solves

    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 Fp.

    The Diffie-Hellman protocol works with elements of some finite field Fp, 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.


  • Diffie-Hellman Starter 2
    20 pts · 2321 Solves · 10 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: H = {g, g^2, g^3, ...}

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

    You must be logged in to submit your flag.


  • Diffie-Hellman Starter 3
    20 pts · 2371 Solves · 1 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*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 diffculty of the discrete logarithm, if the protocol has been implemented correctly the secret integer should be infeasible to compute.

    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.


  • Diffie-Hellman Starter 4
    30 pts · 2256 Solves · 3 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 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.


  • Diffie-Hellman Starter 5
    40 pts · 2035 Solves · 2 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!

    Challenge files:
      - source.py
      - decrypt.py

    You must be logged in to submit your flag.



Man In The Middle

Toggle
  • Parameter Injection
    60 pts · 1461 Solves · 13 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 "Diffie-Hellman Starter 5" to decrypt the flag once you've recovered the shared secret.

    Connect at nc socket.cryptohack.org 13371

    You must be logged in to submit your flag.


  • Export-grade
    100 pts · 1179 Solves · 10 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 nc socket.cryptohack.org 13379

    You must be logged in to submit your flag.


  • Static Client
    100 pts · 662 Solves · 9 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 nc socket.cryptohack.org 13373

    You must be logged in to submit your flag.



Group Theory

Toggle
  • Additive
    70 pts · 820 Solves · 10 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 "Diffie-Hellman Starter 5" to decrypt the flag once you've recovered the shared secret.

    Connect at nc socket.cryptohack.org 13380

    You must be logged in to submit your flag.


  • Static Client 2
    120 pts · 428 Solves · 9 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 nc socket.cryptohack.org 13378

    You must be logged in to submit your flag.



Misc

Toggle

Level Up

level up icon

You are now level Current level