SECT CTF 2018: Writeup for matsign

A while ago I participated in the SECT CTF 2018 with my team HackingForSoju. Here is a writeup for the level Matsign.

                         SECT-CTF 2018 write-up
                                Matsign

Abstract

   This is a write-up for the Matsign challenge of SEC-T CTF 2018 by
   LarsH on behalf of team Hacking for Soju.

Table of Contents

   1.  Description
   2.  Figuring out the behaviour
   3.  Solution
   4.  Overkill solution

1.  Description

   The challenge was running on 178.128.171.133:5555, and the flag was
   said to be the lowest 20 digits of d.

   When connecting to the service, it presents this interface:

                                               __
                                              /C/
             MatSign Cryptographic Service   /I/
             -----------------------------  /B/
                                           |/
                 Security in            | a b c |
                 multiple               | d e f |
                 dimensions             | g h i |


       Give comma-separated matrix to sign:

   Trying some bogus data gives the error message: "Something went
   wrong... size needs to be 3x3" and the service disconnects.

2.  Figuring out the behaviour

   If we give the service nine comma separated digits, the service
   replies with a 2x3 matrix with quite large numbers.

   If we supply the identity matrix 1,0,0,0,1,0,0,0,1 the reply from the
   service is

   [[1L, 0L, 0L], [0L, 1L, 0L]]

   And with the hint that the flag has to do with d, this is probably an
   RSA signing procedure using matrices, with a reply that is truncated
   to only the two first rows of the signed matrix.

   To test this hypothesis, we signed 2,4,3 and 9 using only the upper
   left matrix element.  This gave us

2**d % n = 603679504658226852258733857127676536438248398553526464506065500164789
20892468788806193056971340519189632591200228322574450863215073463938809513217771
27454218151709503308906485870739798369285902552803026690123593617754351285267483
1795529276636510222747378681491655760328983542122308539965569062960418027228183L

4**d % n = 926875655887109007820138851641838494342820714642022256276980010882813
69083202978850909071939396731888865937257211783503498517481458171092865273336295
02679786970301586391509019452500275418214518988911259672731921753902916312843023
0826432702708375423212724719649924819226542225995482529552443813838549471313322L

3**d % n =1002783014045680989162002369174882727519394851004682250516623232951979
31456945237050522241170678807530733514341047234698367738018287290685132701072323
82885426994795428296689422450100483060299748403585984932886370070098500410652752
2352685174235357463416363798084052572369869218241585397948175808995950214249823L

9**d % n = 495967715248440183321179074466677143303668392819564162181938566729935
84684880325084294326181161165473234176322716648852264854729112396270122126314023
39429249451479809223316534416370066154224263543748724963713983872714384359553650
0038124674914252524999992711503900926307291857797248003824799689533766593838147L

   And we can now compute the value of n.  Because

 (2**d % n)**2 = (4**d%n) + a*n    and    (3**d % n)**2 = (9**d%n) + b*n

   then

    n = c * GCD( (2**d % n)**2 - (4**d%n) , (3**d % n)**2 - (9**d%n) )

   There might be some extra factor c, but in this case c was 1.

n = 1167880879539630321283855857098624385796403183896228302611852628744808193253
58293077704265052032681793494472152951802121882380333334023139095912125054377042
73584260405126879310746133999429385784711382198310144962197080782467305669284876
2006415090468821976791496266369267044931986102543085443093592771899364043L

   We finally verify the hypothesis with the commonly used public
   exponent e = 0x10001

>>> pow( 60367950465822685225873385712767653643824839855352646450606550016478920
89246878880619305697134051918963259120022832257445086321507346393880951321777127
45421815170950330890648587073979836928590255280302669012359361775435128526748317
95529276636510222747378681491655760328983542122308539965569062960418027228183L, 
0x10001, n)
2L

   so the signed value of two is indeed two when verified with the
   public exponent.

3.  Solution

   After some thought, we found out that this uppertriangular matrix can
   be used to leak out d:

      | 1 1 0 |**d   | 1 d 0 |
      | 0 1 0 |    = | 0 1 0 |
      | 0 0 0 |      | 0 0 0 |

   This is because exponentiation is just repeated matrix
   multiplication; every multiplication with this matrix to itself will
   increase the top middle element by one:

      | 1 1 0 |   | 1 i 0 |   | 1 (i+1) 0 |
      | 0 1 0 | * | 0 1 0 | = | 0   1   0 |
      | 0 0 0 |   | 0 0 0 |   | 0   0   0 |

   So the solution that leaks out d is

$ echo 1,1,0,0,1,0,0,0,0 | nc 178.128.171.133 5555

                                        __
                                       /C/
      MatSign Cryptographic Service   /I/
      -----------------------------  /B/
                                    |/
          Security in            | a b c |
          multiple               | d e f |
          dimensions             | g h i |


Give comma-separated matrix to sign: [[1L, 5943028721584245726050413176410138283
15456096295820893420591195334533976913911084447172931242701060135959938096181180
21343323376362812940611390044868753126296266703287597058581803060094740282543610
71673572477363571820379071571307323768821649021601211516734751578279378417106050
597533639902738566133769973073L, 0L], [0L, 1L, 0L]]

   The value 59...73L is of d, and the flag is the last 20 digits of
   this number.

   >>> 'SECT{%u}'% (d % 10**20)
   'SECT{2738566133769973073}'

4.  Overkill solution

   As we now have both n, e and d, it is possible to fully factorize n
   into p and q.  This is because of the relation

   e*d = 1 (mod phi(n))
   e*d = 1 + K*(p-1)(q-1) = 1 + K(p*q-p-q+1) = 1 + K(n-p-q+1)  (eq.A)

   and as n is very large compared to p, q and 1, we can compute K as

   K = round(e*d/n) = (e*d + n/2) // n = 3335

   and we can now rewrite (eq.A) to express the sum of p and q and fully
   factorize n

   p+q = 1 + n - (e*d-1)/K
   q = 1 + n - p - (e*d-1)/K
   n = p*q = p * ( 1 + n - p - (e*d-1)/K )
   0 = p**2 - p(n+1 - (e*d-1)/K) + n

   A = (n + 1 - (e*d-1)/k) / 2
   p = A + sqrt(A**2 - n)

   The factors p and q are

p = 1336630743399795870796447022252017388701511267269973434672368351156860707692
3294855549140374608334350841149318231659041457171104749357709779496554220581913
q = 8737498260507305634520033781659157635088054656248608647433097973262598642807
611526467945801713981127525934898453762929448056973637158526184438433905851011