HackTheVote Qual 2016: Trump Trump
November 07, 2016 TalkyBirdTrump Trump
100 points (Crypto)
With Trump about to be in office, autographed photos of him are selling like wildfire. The only problem is: Trump makes it a point to never sign a photo of himself. If you could get a signed picture, you could stand to make DOZENS of dollars.
nc trumptrump.pwn.republican 3609
author’s irc nick: negasora
Overview
The given key file provides the public exponent e (65537) and the 2048-bit modulus N. After playing around with the provided service we realized that it expects the message m as a decimal number and returns the signature s also as a decimal number:
s = (m mod N)d mod N
where d is the private exponent.
We can verify the signature using the following formula:
m mod N == se mod N
Sign the photo, not its hash!
In normal RSA signing scheme, the hash of the data is signed, not the data. We followed that scheme by signing the SHA256 and SHA-1 of the given photo with the proper padding but nothing revealed the flag. We were stuck there for a while until we decided to discuss it to the CTF organizer and they hinted us to sign the photo, not it hash :)
We used the followed code snippet to get the decimal number m of the photo to be signed:
1
2
3
4
5
6
7
8
9
import gmpy2
import binascii
N = gmpy2.mpz(23377710160585068929761618506991996226542827370307182169629858568023543788780175313008507293451307895240053109844393208095341963888750810795999334637219913785780317641204067199776554612826093939173529500677723999107174626333341127815073405082534438012567142969114708624398382362018792541727467478404573610869661887188854467262618007499261337953423761782551432338613283104868149867800953840280656722019640237553189669977426208944252707288724850642450845754249981895191279748269118285047312864220756292406661460782844868432184013840652299561380626402855579897282032613371294445650368096906572685254142278651577097577263)
f = open('trump.04a0d9783458ec220e8ba41f4fb3d0e039750b3d79945a5e941f1bfb55cf68fc.jpg', 'rb')
data = f.read()
f.close()
print gmpy2.mpz(binascii.hexlify(data), base=16) % N
And here is m:
18827218237281561365853271562754519781539872429234992869534137971840382404261714042549044900428733910064403567487872040777726232397744142691871261186402747616508182945376519235560292880605379726441897766638908010388991746340837594685029015572272539596995089038692720970103143296494656038334788557421602035403223353705797303280287806282274515684414296566698984222822679816267699671385577836574513471337445277523873203491921082096622318182358465751183885810804210590435538039683647558970257150444629816622086168297325742249472912487229114390061007521656812444992832560689314593051182832171168110371760586908174415614345
We entered that number to the given service and it replied:
Duneld Trump: Well, My horoscope said I should, so okay. WHADDYA TRYIN TO PULL HERE? I don't sign pictures of myself!
So we failed to sign m directly. We realized that m was divisible by 5 since it ended with the digit 5:
m: 18827…4345
It means that we can write m as a product of 5 and another integer number m2:
m = 5 * m2
Here’s how the signature s of m is computed:
s = md mod N = (5 * m2)d mod N = ((5d mod N) * (m2d mod N)) mod N
so we could compute s without directly using m:
s1 = 5d mod N
s2 = m2d mod N
s = (s1 * s2) mod N
s1 is a signature of 5, s2 is a signature of m2.
m2 = 3765443647456312273170654312550903956307974485846998573906827594368076480852342808509808980085746782012880713497574408155545246479548828538374252237280549523301636589075303847112058576121075945288379553327781602077798349268167518937005803114454507919399017807738544194020628659298931207666957711484320407080644670741159460656057561256454903136882859313339796844564535963253539934277115567314902694267489055504774640698384216419324463636471693150236777162160842118087107607936729511794051430088925963324417233659465148449894582497445822878012201504331362488998566512137862918610236566434233622074352117381634883122869
Getting the signatures
We entered the number 5 to the given service to get its signature s1:
s1 = 18938431620064949405099081881389422411569506620645684785718437650149907701313939238017399264771270907473551575023831816899182480214946633959498312433619616816861526269114681215528914329791099013891595131862543300865871379621247867883669403120593815746911158013483346808195756730946735362037791985948842449343328484149265803462983935765047801620079220588638013959948297979415581591179722303271496129424130559547762467547913292325129340535450673107267746074776721093375970510983576513946461957148135755448610570645462794635156136176208419134557678284424568016798221633694322809374691561612990098051154456165773266086828
Then we entered m2 to get s2:
s2 = 15742105247958736958004859844860106392650529642491444791655288653059139800053206167023792876159338330811553994563264038797209523053486931817881299156223450837206775783069574776254654197337314541494064874054449749920216258529257414289049794126137529358458843274774718683434637726891822317083908587215429977340799931758155377373656742947190372216055450421108566287038161365843817023142180328035768992726841684537565155117632165969899505426984495819465218509929865350057283134017766501372618581237936784285588661088765130624093014320161531747074858737002260566015050922492437422682387506583350890218827504186050632600504
Then we compute s:
s = (s1 * s2) mod N = 7240527260044126899075832339973255923943354335060037001558105343295495841635843603507411996488568977206115374657942401805673165802944813082589201103827861325639581582005106924492724100812077464571265915352012064311221086996199961637876724784326540728342282620427706011099830010859187486529928704673604893811823836195858916605646466850177580221970723526928598144155086898666864544017092301766812496415256830844105167571316067435310083881243302996555421199570092966497927454347195963984192282682803663188954259681974561132158520131591167970511602803401392202553720288822909116428852233039667283953852194960467196349739
The flag
The generated value of s also did not reveal the flag. So we entered it to the given service and here was its reply:
Duneld Trump: Well, My horoscope said I should, so okay. Trump looks shocked, appalled by the fact that he'd sign a picture of himself for such a not-billionaire. Trump sprints away at a blinding 2mph, dropping what he was carrying. It's a stack of photos, you pick one up and look at it. ffd8ffe000104a46494600010101006000600000ffdb004300030202030202030303030403....85038562057ffd9
The returned signature now is not a decimal number, but a hex encoded of an JPEG image. And here we get the flag:
flag{y0u_c4n’T_duMp_TrUmp}