> For the complete documentation index, see [llms.txt](https://ctf.thaysan.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ctf.thaysan.com/ctf-and-writeups/2024-or-efrei-cybernight/cryptographie/shared-flag.md).

# Shared Flag

**Flag:** CYBN{5m4ll\_Gr0up5\_c4n\_0pt1m1s3\_Brut3F0rc3}

## Challenge

{% file src="/files/krADOT8weSZSL4rQlIIl" %}

{% hint style="info" %}
**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 !
{% endhint %}

{% hint style="warning" %}
Ce challenge tourne sur un docker et n'est pas disponible
{% endhint %}

## 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 

<figure><img src="/files/C1IE5IxAIqroT3UKOp8T" alt=""><figcaption></figcaption></figure>

À partir de là, une simple recherche Google permet de tomber sur l'excellent [**Write-Up de Amon**](https://nandynarwhals.org/sieberrsec-ctf-3.0-diffieskeyexchange2/).

Voici une version adaptée au challenge :

```python
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}
```