PicoCTF - Broadcast
April 18, 2017

You stumbled upon a group Message. Can you figure out what they were sending? The string sent is ascii encoded as a hex number (submit the ascii string as the flag)

```
e = 3
c1 = 261345950255088824199206969589297492768083568554363001807292202086148198540785875067889853750126065910869378059825972054500409296763768604135988881188967875126819737816598484392562403375391722914907856816865871091726511596620751615512183772327351299941365151995536802718357319233050365556244882929796558270337
n1 = 1001191535967882284769094654562963158339094991366537360172618359025855097846977704928598237040115495676223744383629803332394884046043603063054821999994629411352862317941517957323746992871914047324555019615398720677218748535278252779545622933662625193622517947605928420931496443792865516592262228294965047903627
c2 = 147535246350781145803699087910221608128508531245679654307942476916759248311896958780799558399204686458919290159543753966699893006016413718139713809296129796521671806205375133127498854375392596658549807278970596547851946732056260825231169253750741639904613590541946015782167836188510987545893121474698400398826
n2 = 405864605704280029572517043538873770190562953923346989456102827133294619540434679181357855400199671537151039095796094162418263148474324455458511633891792967156338297585653540910958574924436510557629146762715107527852413979916669819333765187674010542434580990241759130158992365304284892615408513239024879592309
c3 = 633230627388596886579908367739501184580838393691617645602928172655297372145912724695988151441728614868603479196153916968285656992175356066846340327304330216410957123875304589208458268694616526607064173015876523386638026821701609498528415875970074497028482884675279736968611005756588082906398954547838170886958
n3 = 1204664380009414697639782865058772653140636684336678901863196025928054706723976869222235722439176825580211657044153004521482757717615318907205106770256270292154250168657084197056536811063984234635803887040926920542363612936352393496049379544437329226857538524494283148837536712608224655107228808472106636903723
```

Another RSA challenge. This time we have number of group messages, encrypted with the same small exponent (e). After doing a little bit of googling, I've found that Hastad's Broadcast Attack is able to break this encryption. You can read more about it here , at chapter 4.2.

If three parties participating in the same system encrypt the same message m using the same public exponent e=3, although perhaps different modulus n1, n2, and n3, then one can easily compute m from the three cipher texts.

Now we can look at the equations:

c1 = m^3 modulo n1

c2 = m^3 modulo n2

c3 = m^3 modulo n3

But what now? This amazing piece of code will perform the attack for us. Let's take a look at it.

import sys
import binascii
from Crypto.PublicKey import RSA
from base64 import b64decode
if ( len ( sys . argv ) < 7 ):
print " \t\n\n Arg error: python rsaHastad.py <n0 File> <n1 File> <n2 File> <c0 File> <c1 File> <c2 File> [--decimal/--hex/--b64] [-v/--verbose] \n\n "
exit ()
print " \n "
print " \t ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
print " \t RSA Hastad Attack "
print " \t JulesDT -- 2016 "
print " \t License GNU/GPL "
print " \t ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
def chinese_remainder ( n , a ):
sum = 0
prod = reduce ( lambda a , b : a * b , n )
for n_i , a_i in zip ( n , a ):
p = prod / n_i
sum += a_i * mul_inv ( p , n_i ) * p
return sum % prod
def mul_inv ( a , b ):
b0 = b
x0 , x1 = 0 , 1
if b == 1 : return 1
while a > 1 :
q = a / b
a , b = b , a % b
x0 , x1 = x1 - q * x0 , x0
if x1 < 0 : x1 += b0
return x1
def find_invpow ( x , n ):
high = 1
while high ** n < x :
high *= 2
low = high / 2
while low < high :
mid = ( low + high ) // 2
if low < mid and mid ** n < x :
low = mid
elif high > mid and mid ** n > x :
high = mid
else :
return mid
return mid + 1
def parseC ( argv , index , verbose ):
import string
file = open ( argv [ index ], 'r' )
cmd = ' ' . join ( argv )
fileInput = '' . join ( file . readlines ()) . strip ()
if '--decimal' in cmd :
if verbose :
print "##"
print "##" , fileInput
print "## Considered as decimal input"
print "##"
return long ( fileInput )
elif '--hex' in cmd :
if verbose :
print "##"
print "##" , fileInput
print "## Considered as hexadecimal input"
print "##"
return long ( fileInput , 16 )
elif '--b64' in cmd :
if verbose :
print "##"
print "##" , fileInput
print "## Considered as base64 input"
print "##"
return long ( binascii . hexlify ( binascii . a2b_base64 ( fileInput )), 16 )
else :
try :
fileInput = long ( fileInput )
if verbose :
print "##"
print "##" , fileInput
print "## Guessed as decimal input"
print "##"
return long ( fileInput )
except ValueError :
if all ( c in string . hexdigits for c in fileInput ):
if verbose :
print "##"
print "##" , fileInput
print "## Guessed as hexadecimal input"
print "##"
return long ( fileInput , 16 )
else :
if verbose :
print "##"
print "##" , fileInput
print "## Guessed as base64 input"
print "##"
return long ( binascii . hexlify ( binascii . a2b_base64 ( fileInput )), 16 )
pass
def parseN ( argv , index ):
file = open ( argv [ index ], 'r' )
fileInput = '' . join ( file . readlines ()) . strip ()
try :
fileInput = long ( fileInput )
return fileInput
except ValueError :
from Crypto.PublicKey import RSA
return long ( RSA . importKey ( fileInput ) . __getattr__ ( 'n' ))
pass
if __name__ == '__main__' :
e = 3
cmd = ' ' . join ( sys . argv )
if '-v' in cmd or '--verbose' in cmd :
verbose = True
else :
verbose = False
n0 = parseN ( sys . argv , 1 )
n1 = parseN ( sys . argv , 2 )
n2 = parseN ( sys . argv , 3 )
c0 = parseC ( sys . argv , 4 , verbose )
c1 = parseC ( sys . argv , 5 , verbose )
c2 = parseC ( sys . argv , 6 , verbose )
n = [ n0 , n1 , n2 ]
a = [ c0 , c1 , c2 ]
result = ( chinese_remainder ( n , a ))
resultHex = str ( hex ( find_invpow ( result , 3 )))[ 2 : - 1 ]
print ""
print "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
print "Decoded Hex : \n " , resultHex
print "---------------------------"
print "As Ascii : \n " , resultHex . decode ( 'hex' )
print "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"

Shoutout to JulesDT !

And now it's time to finally crack this message. Firstly let's create files that will hold our ciphertext and modulus n values.

[email protected] ~> echo "261345950255088824199206969589297492768083568554363001807292202086148198540785875067889853750126065910869378059825972054500409296763768604135988881188967875126819737816598484392562403375391722914907856816865871091726511596620751615512183772327351299941365151995536802718357319233050365556244882929796558270337" >> c0
[email protected] ~> echo "1001191535967882284769094654562963158339094991366537360172618359025855097846977704928598237040115495676223744383629803332394884046043603063054821999994629411352862317941517957323746992871914047324555019615398720677218748535278252779545622933662625193622517947605928420931496443792865516592262228294965047903627" >> n0
[email protected] ~> echo "147535246350781145803699087910221608128508531245679654307942476916759248311896958780799558399204686458919290159543753966699893006016413718139713809296129796521671806205375133127498854375392596658549807278970596547851946732056260825231169253750741639904613590541946015782167836188510987545893121474698400398826" >> c1
[email protected] ~> echo "405864605704280029572517043538873770190562953923346989456102827133294619540434679181357855400199671537151039095796094162418263148474324455458511633891792967156338297585653540910958574924436510557629146762715107527852413979916669819333765187674010542434580990241759130158992365304284892615408513239024879592309" >> n1
[email protected] ~> echo "633230627388596886579908367739501184580838393691617645602928172655297372145912724695988151441728614868603479196153916968285656992175356066846340327304330216410957123875304589208458268694616526607064173015876523386638026821701609498528415875970074497028482884675279736968611005756588082906398954547838170886958" >> c2
[email protected] ~> echo "1204664380009414697639782865058772653140636684336678901863196025928054706723976869222235722439176825580211657044153004521482757717615318907205106770256270292154250168657084197056536811063984234635803887040926920542363612936352393496049379544437329226857538524494283148837536712608224655107228808472106636903723" >> n2

Now we can use provided code to break the crypto, and get the message.

[email protected] ~> python2 hastad.py n0 n1 n2 c0 c1 c2
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
RSA Hastad Attack
JulesDT -- 2016
License GNU/GPL
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Decoded Hex :
62726f6164636173745f776974685f736d616c6c5f655f69735f6b696c6c65725f3430333332333030313931
---------------------------
As Ascii :
broadcast_with_small_e_is_killer_40332300191
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Amazing crypto challenge, and we have another flag!

Contact
If you have any suggestions regarding this post or just want to chat together check out these ways to reach out to me.