HackTheVote Qual 2016: Trump Trump

Trump 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

trump

trumpkey

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 == s^e 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 m₂:

m = 5 * m₂

Here’s how the signature s of m is computed:

s = m^d mod N = (5 * m₂)^d mod N = ((5^d mod N) * (m₂^d mod N)) mod N

so we could compute s without directly using m:

s₁ = 5^d mod N

s₂ = m₂^d mod N

s = (s₁ * s₂) mod N

s₁ is a signature of 5, s₂ is a signature of m₂.

m₂ = 3765443647456312273170654312550903956307974485846998573906827594368076480852342808509808980085746782012880713497574408155545246479548828538374252237280549523301636589075303847112058576121075945288379553327781602077798349268167518937005803114454507919399017807738544194020628659298931207666957711484320407080644670741159460656057561256454903136882859313339796844564535963253539934277115567314902694267489055504774640698384216419324463636471693150236777162160842118087107607936729511794051430088925963324417233659465148449894582497445822878012201504331362488998566512137862918610236566434233622074352117381634883122869

Getting the signatures

We entered the number 5 to the given service to get its signature s₁:

s₁ = 18938431620064949405099081881389422411569506620645684785718437650149907701313939238017399264771270907473551575023831816899182480214946633959498312433619616816861526269114681215528914329791099013891595131862543300865871379621247867883669403120593815746911158013483346808195756730946735362037791985948842449343328484149265803462983935765047801620079220588638013959948297979415581591179722303271496129424130559547762467547913292325129340535450673107267746074776721093375970510983576513946461957148135755448610570645462794635156136176208419134557678284424568016798221633694322809374691561612990098051154456165773266086828

Then we entered m₂ to get s₂:

s₂ = 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}