[Encryptie] Security challenge

[Richum]

Hallo mede-tweakers,

Momenteel probeer ik een security challenge op te lossen maar ik kom helaas niet verder

Opzet van de challenge
De challenge ziet er ongeveer als volgt uit:

1. Alice leest een authenticatie-code uit een tekstbestand
2. Alice leest de flag uit een tekstbestand
3. Bob leest de authenticatie-code uit een tekstbestand
4. Bob stuurt Alice zijn authenticatie code
5. Alice verifieert de authenticatie code
6. Alice stuurt Bob de flag

Aanpak
Om de communicatie te versleutelen wordt er gebruik gemaakt van Diffie-Hellman (DH) om een geheim getal c.q. sleutel af te spreken. Ik denk daarom de challenge als volgt te moeten oplossen:

1. Wissel een geheime sleutel uit met Alice via DH
2. Wissel een geheime sleutel uit met Bob via DH
3. Ontvang de authenticatie-code van Bob
4. Ontsleutel de authenticatie-code
5. Versleutel de authenticatie-code voor Alice met de uitgewisselde sleutel
6. Ontvang de flag van Alice
7. Decrypt de flag
8. Profit!

Nu is bovenstaande in zoverre gelukt dat ik een man-in-the-middle verbinding heb opgezet tussen beide partijen:

code:

[Alice] <====> [Eve] <====> [Bob]

Ook heb ik via Diffie-Hellman met beide partijen een gemeenschappelijke sleutel afgesproken. Dus een sleutel voor de verbinding met Alice en een sleutel voor de verbinding met Bob.

Het probleem
Het probleem is de encryptie die wordt toegepast na de uitwisseling van de sleutels, namelijk:

code:

plain_text ^ key % constante = encrypted

oftewel

encrypted = plain_text ^ key mod(constante)

Alle variabelen in bovenstaand voorbeeld zijn integers. Ik ontvang van Bob de encrypted waarde. Echter moet ik deze decrypten en vervolgens weer encrypten met de key van Alice zodat zij mij het wachtwoord stuurt.

Ik weet de waarde van alle gebruikte variabelen behalve plain_text. Echter is encrypted het resultaat van een modulus operatie. Hoe kom ik er achter wat plain_text was? Ik heb al lang gezocht en van alles geprobeerd maar ik kom er niet uit

Heeft iemand een idee? Alvast ontzettend bedankt

[ Voor 3% gewijzigd door Richum op 27-07-2019 18:53 ]

[Squ1zZy]

<verwijderd>

[ Voor 98% gewijzigd door Squ1zZy op 08-11-2020 17:22 ]

[Richum]

Het concept van Diffie-Hellman (DH) is mij duidelijk: een algorithme om een gemeenschappelijke geheime sleutel uit te wisselen. Dit is ook wat ik heb gedaan, namelijk d.m.v DH een geheime sleutel uitwisselen/afspreken met Alice en Bob.

DH voorziet niet in het verifiëren van de identiteit van de andere partij. Een MITM-attack is daarom nog gewoon mogelijk. Het probleem is niet het DH-algorithme maar de vorm van encryptie die daarna plaatsvindt met de uitgewisselde sleutel.

Edit:

De stappen hadden niets te maken met de implementatie van DH. Daarom de oorspronkelijke post aangepast/verduidelijkt.

[ Voor 27% gewijzigd door Richum op 27-07-2019 18:48 ]

[Thralas]

Richum schreef op zaterdag 27 juli 2019 @ 17:42:
Ik weet de waarde van alle gebruikte variabelen behalve plain_text. Echter is encrypted het resultaat van een modulus operatie. Hoe kom ik er achter wat plain_text was? Ik heb al lang gezocht en van alles geprobeerd maar ik kom er niet uit

Wat is de waarde van constante? Is het een priemgetal?

Is dit huiswerk?

[Richum]

Nee, geen huiswerk maar persoonlijke interesse

De waarde van de constante (in hex) is:

code:

p = 0x85e99842bf55f81044e281004808b209a516bd029c32672df1971a73f2537809bd6c1729ead34ebc26622b0ed41eded76b27c3a87015a2c14adbe0b413491ce14a7e871e33509e70c344e59b002ba9a9f4b0dddde452fa544ffe38914632c45c78070efe79b8175b4fd18ccbf671548aa8064b6c6c5652c5c3a7d866dc5ef9b1

Gezien de naam van de variabele zou dit best een priemgetal kunnen zijn.

[Thralas]

Richum schreef op zaterdag 27 juli 2019 @ 19:47:
Gezien de naam van de variabele zou dit best een priemgetal kunnen zijn.

Dat kun je natuurlijk controleren. Spoiler: dat is zo.

Even versimpelen:

code:

encrypted = plain_text ^ key mod(constante)

y = x ^ e (mod p)

Volgens mij zoek je de e'de machtswortel modulo p. Als gcd(e, φ(p)) = 1 (ga dit na, anders valt de rest van deze post in duigen), dan is het vinden van hiervan simpel (bron):

φ(p) = p - 1 (triviaal want p is priem) ¹
d = e^-1 (mod φ(p)) (noot: ²)

En is de e'de machtswortel van y: x = y^d (mod p)

¹ zie Euler's totient)
² De inverse van e bepaal je met het extended euclidian-algoritme.

Aangenomen dat het bovenstaande klopt, zie de gelijkenis met het berekenen van de private exponent d in RSA, alleen daar krijg je φ(p) niet cadeau, zoals hier.

[Richum]

Challenge is inmiddels opgelost. Variabelen tijdens de key exchange werden hergebruikt voor het encrypten. Daardoor was het mogelijk om de encryptie teniet te doen. Ik zal verder niet in detail treden om potentiële spoilers te voorkomen. Iedereen bedankt voor het meedenken!