Original Challenge:

• Solves: 35

• The NSA gave us these packets, they said it should be just enough to break this crypto.

Challenge files

Difficulty estimate: medium

In the files we have one pcap file – surveillance.pcap which contains 40 TCP streams (wireshark → Statistics → Conversations)

When we follow the TCP stream – each stream looks very similar to this:

20779900528817692337799168797527459491 62670239152271854568281304556299175800 93353632585838558129339305409612190036 29275293709030893096906315031093475117 217443785766847465643965167326471366930 87768394800337534630670868726874169262 94272021819697638819758476484784437174 79761509873597193538805774586772152551 287077043474345536330292000256667722862 338545568968754066451781943973364050747 297369519464034454780797709549121754981 56885490048115174244568542056852168691 125409768592704189418754659727077855243 248903210971800661957902959437529720078 105198372128401404878582092383380684270 171346466625618610030275381510572715586 155477660830517170755561240929991575154 182673696836619568854491288432442673233 262702931683036291589579288667282098519 18870116631740236121991956018407513291 259639713869223969256075040261046227211 211759681449153548839999286208573748417 75564698223593131868793110465400517546 3957872548388281697136273156279603423 216645505172179755607682378174353919850 229968384683068856202657067569523090578 66739301027057081876758954753275857501 116367528061570402100923471061918655467 143750469825367138306146966620543701048 183518250254992484830711613992618112334 177659446112610152502618121534022672394 294880691868997745862235404753518785618 296817543478127190410821587158884107642 58918844088249738906048787671526281242 191823527475136131674233114644080652238 115153266167256987643478624321147128279 33028997731842108545265409344234591070 32020688555063599381439427034519438611 136800502151738819775273044156131929386 297262660200845071604521241820385548094
487839305465823234006845594602546874778491
ACCESS GRANTED
aef8c15e422dfb8443fc94aa9b5234383d8ee523d6da9c4875ccf0d2cf24b1c3fa234e90b9f9757862d242063dbd694806bc54582deddbcbcc

except one stream which is:

58557110956988947057604802588561896500 124389245447086365003181102994712842606 82395139655125145682424929123746759522 47649451703051529899277902695473539892 150981473550872530548663509246216281805 168563983740131744014317862124200995089 138586260804512475239450269675967207835 62436069859970279880393432647328777542 22913686979727780041806138144484753933 14377633287456896562041901004526098962 273196090090464520445990336716474469243 242168062305495710098626001414876184684 94362973583077677476509316957112725408 29088551100976965023442015189790524406 43231997455607345760204676007554876342 132361861464878302707174999703933345282 253872750092097302859318147550396944380 213628045569424246848985217725072451309 294344411139289978298406248909275102813 226888910812725047738767244100865543325 94082207521578531435238803168695213013 97111136227337754555078662768570661087 185250299454417634170420352961477926506 67438648618265917969789929448437485879 101682932749781295458233490525355462280 113556545381411565044202682512491580939 244226227037022039791321269794441569705 61030029875782065229041917864523517796 189182692689289560885216139521470329934 30211253278711272924044288553988214247 121622236650064002460174949909446201741 65301450599692169122475160199358409465 73053494341241445616892110693763168071 234683993955061111113773411581440059586 283639424985419487458121053850137768397 127760719714334178221109348661056530813 128791727498437259840522852285552430716 20843448351817739519520104708561322010 176162735964861803752894890674194111533 42645121406909462815210125923299652368
20122444954621613642609378528068231780800
ACCESS DENIED

We also have the python code for the server side:

server code:

import os, math, sys, binascii
from secrets import key, flag
from hashlib import sha256
from Crypto.Cipher import AES

p = 21652247421304131782679331804390761485569
bits = 128
N = 40

def rand():
    return int.from_bytes(os.urandom(bits // 8), 'little')

def keygen():
    return [rand() for _ in range(N)]

if __name__ == '__main__':
    #key = keygen()   # generated once & stored in secrets.py
    challenge = keygen()
    print(' '.join(map(str, challenge)))
    response = int(input())
    if response != sum(x*y%p for x, y in zip(challenge, key)):
        print('ACCESS DENIED')
        exit(1)

    print('ACCESS GRANTED')
    cipher = AES.new(
            sha256(' '.join(map(str, key)).encode('utf-8')).digest(),
            AES.MODE_CFB,
            b'\0'*16)
    print(binascii.hexlify(cipher.encrypt(flag)).decode('utf-8'))

 

Encryption Scheme:

The server send a random challenge – which is a list of N random numbers – each 128 bits long (16 bytes)

It expects a response  back which should be the result of the following calculation: Sum(Challenge[i]*Key[i] % p).

If it the response is correct – we get the flag encrypted with the key

first thought:

• p is not really prime:
• python -m primefac 21652247421304131782679331804390761485569
  21652247421304131782679331804390761485569: 311 311 313 313 317 317 331 331 337 337 347 347 349 349 353 353
  *8 different prime factors
  * each prime factor appears twice
• Since we have the session data – we can use it to solve 40 equations with 40 variables – or at least we could – if we had 40 successful sessions – but we have only 39.
• But we are working in the “Field” of modulus p – so we might not need all 40 equations…
  in the end – all you needed to do was solve the 39 equations…
• We are not completely sure why but it appears that the 39 equations (congruences to be exact) are enough to span the whole vector space of the solutions.

using sage the solution looks like this (python2):

from Crypto.Cipher import AES
from matrix import *
from hashlib import sha256
import binascii

p = 21652247421304131782679331804390761485569 # 311 311 313 313 317 317 331 331 337 337 347 347 349 349 353 353
N = 40

R = IntegerModRing(p)
M = Matrix(R, [vector(R, ch) for ch in Challenges])
b = vector(R, Responses)
key = (M.solve_right(b))

flag = 'aef8c15e422dfb8443fc94aa9b5234383d8ee523d6da9c4875ccf0d2cf24b1c3fa234e90b9f9757862d242063dbd694806bc54582deddbcbcc'.decode('hex')

cipher = AES.new(
            sha256(' '.join(map(str, key)).encode('utf-8')).digest(),
            AES.MODE_CFB,
            b'\0'*16)
print 'solution'
print cipher.decrypt(flag)

 

where matrix is was generated by the following script: (python3)

import pyshark
cap = pyshark.FileCapture('surveillance.pcap')

N = 40
session_data = {}
for i in range(N):
    session_data[i] = b''

Challenges = []
Responses = []

for pkt in cap:
    try:
        session_data[int(pkt.tcp.stream)] += pkt.data.data.binary_value
    except AttributeError:
        pass

for i in range(N):
    data = session_data[i].split(b'\n')
    if data[2] == b'ACCESS GRANTED':
        Challenges.append([int(x) for x in data[0].split(b' ')])
        Responses.append(int(data[1]))

print ('Challenges = []')
print ('Responses = []')

for i in range(N-1):
    print ('Challenges.append(%s)' % (Challenges[i]))
    print ('Responses.append(%s) ' % (Responses[i]))