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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ctf.thaysan.com/ctf-and-writeups/2024-or-efrei-cybernight/cryptographie/shared-flag.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.