Shared Flag

Flag: CYBN{5m4ll_Gr0up5_c4n_0pt1m1s3_Brut3F0rc3}

Challenge

2KB

shared-flag.zip

archive

Description

---

Tu veux ce flag ? Eh bien, bonne chance. J’ai volé ça aux admins, mais comme je suis sympa, je te le donne… no bonobo no troll.

Il faut juste m'envoyer ta clé publique pour sécuriser notre échange, rien de plus simple !

Ce challenge tourne sur un docker et n'est pas disponible

Solution

L'objectif de ce challenge n'était pas d'être un crack en crypto, mais de comprendre les bases de Diffie-Hellman et voir le problème pour chercher une solution ensuite.

Soit, on comprend tout de suite que g = 1337 est bizarre, soit on demande à ChatGPT

À partir de là, une simple recherche Google permet de tomber sur l'excellent Write-Up de Amon.

Voici une version adaptée au challenge :

from pwn import *
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import unpad
import primefac
import random
import hashlib

def decrypt_flag(shared_secret: int, encrypted: bytes) -> str:
  key = hashlib.md5(long_to_bytes(shared_secret)).digest()
  cipher = AES.new(key, AES.MODE_ECB)
  return unpad(cipher.decrypt(encrypted), AES.block_size).decode()

context.log_level = 'error'

client = remote('challenge1.cybernight-c.tf', 14606)

# Get g
client.recvuntil(b'g : ')
g = int(client.recvline())
client.recvuntil(b'p : ')
p = int(client.recvline())
client.recvuntil(b'> ')

# Check that p is prime and factor p-1.
if not primefac.isprime(p):
  print("The provided modulus is not prime!")
  exit(1)
factors = primefac.primefac(p - 1)

# Most likely 2 is a factor and thus provides a subgroup of size 2 but this generalises it.
seen_factors = set()
for factor in factors:
  if factor in seen_factors:
    continue
  seen_factors.add(factor)

  # Test 1000 integers.
  for i in range(1000):
    generator_candidate = random.randrange(2, p - 1)
    candidate = pow(generator_candidate, (p - 1) // factor, p)
    if candidate != (p - 1) and candidate != 1:
      # Find the possible shared values.
      possible_shared = set()
      ctr = 1
      max_ctr = 100
      while len(possible_shared) != factor and ctr < max_ctr:
        possible_shared.add(pow(candidate, ctr, p))
        ctr += 1
    
      if ctr >= max_ctr:
        continue
      
      # Now that we have all we need to predict the possible shared secrets, send the candidate.
      print(f'Candidate {candidate} has {len(possible_shared)} elements in subgroup: {possible_shared}')
      client.sendline(str(candidate).encode())
      client.recvuntil(b'Ton flag : ')
      encrypted_flag = bytes.fromhex(client.recvline().decode())
      print(f'Encrypted flag: {encrypted_flag.hex()}')
      
      for shared_secret in possible_shared:
        try:
          possible_flag = decrypt_flag(shared_secret, encrypted_flag)
          if 'CYBN{' in possible_flag:
            print(f'Shared secret: {shared_secret}')
            print(f'Flag: {possible_flag}')
            exit(0)
        except Exception:
          pass
      print('No shared value found, please restart.')
      exit(2)

Candidate 6265678245991872456320858998073671351007489794814114793080913635250710728201785243423030151832175440788246829129062001725088177920132524672557673973271865 has 11 elements in subgroup: {1, 9029120652166378964367429851156482578200495177912752180512995593660126632458108459462275708197304643385229689780956189627061965350538884149385114925512798, 1838838042286935489418306134744273648397086420941649932939758359294756924869614601283219521610912486051596540595116931003984172163790678001185171088854959, 87395888045951907346296534852819083484102635863786724780913155655335878404968631860011943082857238294764172701399219919164750489753057551747502426071156, 1446413906302913307220827318777044225820773415195883392767389608171421354764666352865916526876316055396387777540539319951313647236274119727167323868950274, 4497663980674247798869013093047617904002464346021793252932109293598193935087053459941161962399463932969903292626373400853929973865902294601750444107918275, 9250591517024289522338668621801789753790914226604337022152551046938720552424195176073029057656713900305082382513776525487372750476153926859020429791686987, 9682934674256688108950077478046964042168375551589576065014988750640546437075673661077370354630538103339476905395920361874176612094376562711114941328632532, 2973184386827321182901460992877524244086209233632889019589699592403500006582255651154384543737765845074524596232166640426566109957792424757993590241744836, 6265678245991872456320858998073671351007489794814114793080913635250710728201785243423030151832175440788246829129062001725088177920132524672557673973271865, 3872496823964448705149379948506244064328250160186939852389515479277771585593402890039126808406145999908446037170992674975566195288871858844648781882690682}
Encrypted flag: f2a63e89b41c0bae56f174e52f9948f08026255eaf742fffba8bc75c8f9bc3bded19a7bdb596b22ae95d03cf8e8cb518
Shared secret: 1446413906302913307220827318777044225820773415195883392767389608171421354764666352865916526876316055396387777540539319951313647236274119727167323868950274
Flag: CYBN{5m4ll_Gr0up5_c4n_0pt1m1s3_Brut3F0rc3}