ݺߣ

ݺߣShare a Scribd company logo

katagaitai CTF㏊ #3 crypto

?Download as PPTX, PDF?
?
T
trmr

2015/12/20~ԭˤƌgʩkatagaitai㏊ #3Υ饤ɡǤ

1 of 85
Downloaded 138 times
CTF㏊ #3 Crypto 20151220 trmr (@trmr105) katagaitai
ע ? 饤ɤ㏊äΤԪɤƤޤ ? ㏊Ǥφ}`ФäޤȤֹͣƤޤ ? }`ФIPۥƤwޤri 椨ޤ ? ФȤ⤯ ? }ӛURLäƤޤ ? http://pastebin.com/Ea3Gm8w2 ? Υک`㏊μ־writeupdƤޤ ? ˽writeup100ʤΤǡҤդƤ 2
ϼȤϤʤ󤾤 äʤȤ֤Ϥˤ򉈤䤷 3
SߤˤƤ뤳 TwitterѲ Writeup #katagaitaiCTF 4
katagaitaig ? ذk ? bata(@bata_24) `` ? trmr(@trmr105) 󥻥 ? Yϥӥ` ? askn(@asai_ken) ` # gˤY餷 # tl֪ʤ We are katagaitai! 5
դΆ} ? [Ghost in the shellcode CTF 2013] Q20 - Subme CODE 6
subme٤4Ĥ ? ͨIŤ ? _IŤν⤭ѥ`󻯤Ƥ놖} ? ޤwriteupʤ ? MSLCwriteupҊĤ󤫤ä ? ֤MMAäԔwriteupƤϤ ? ŽƤ뤫 ? }⤯^̤gHΰť르ꥺ˽ݤ ? Ά}ˤĤƤƤʤ ? Ƥ׷Ƥ ? ͎ĿָB 7
Ά} ? ޤϤ˴ΤSHA1ϥåҪ󤵤 ? SHA1ϥåĩβ16ӥåȤ1 ? 뤨줿Фʼޤ ? L21Х ? T餷ˤäƤߤޤ礦 ? Kä醖}⤭ʼƤ 208
ͨIŤȹ_I ? ͨI C ͨIäưŻ/ͺŤgʩ ? _I C ŻȏͺŤˮʤI 9
ͨIŤΥƥ` ? 夳Τ褦ʥƥ櫓Ǥ루Ϥ ? ȥ`వ ? LFSRͣsnow, K-Cipher2 etc. ? ״BwͣRC4, trivium, chacha-20 etc. ? ֥å ? Feistel죺DES, MISTY, Camellia etc. ? SPN죺AES, Serpent etc. դϤ 10
SPN ? GaborPete 11
SPN ? GaborPete AddRoundKey Substitution Permutation 1 Round is and iterate it 12
SPNθҪ ? Substitution ? Ǿvj ? СgλХȣȤ˄I뤳Ȥत ? ÓQƩ`֥루S-boxä뤳Ȥत ? Permutation ? ȫ򥷥åե뤷Ӱ푤ڹ ? ֥åȫˌI Input S S S S S S S S Permutation 13
SPNθҪ ? Substitution ? Ǿvj ? СgλХȣȤ˄I뤳Ȥत ? ÓQƩ`֥루S-boxä뤳Ȥत ? Permutation ? ȫ򥷥åե뤷Ӱ푤ڹ ? ֥åȫˌI S S S S S S S S Permutation 1byte` ȫӰ 14
AESҊƤ ? AES: Advanced Encryption Standard ? ԪRijndaelǩ`룿饤`룿 ? 2001FIPS197׹˜ʤʤΤ˥٥륮`u ? 128, 192, 256bitꡢ΢˘` 15
AESΘ ? AES: Advanced Encryption Standard ? ڻȤ ? KEY EXPANTION ? ͨIȤӛI1饦ɤȤ ? AddRoundKey ? SubBytes ? ShiftRows ? MixColumns ? ӛI10饦R귵(128bitΈ) 16
AESΘ (1饦) Input Key (K) (expanded) Output S S S S S S S S MixColumns 1 AddRoundKey 2 SubBytes ShiftRows 3 ShiftRows 4 MixColumns 17
AESΘ (1饦) Input Key (K) (expanded) Output S S S S S S S S MixColumns 1 AddRoundKey 2 SubBytes Substitution ShiftRows 3 ShiftRows Permutation 4 MixColumns Permutation Permutation 18
AESȫQ S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation ƽ 19
AESȫQ S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation ƽ AESΤϤɤ 20
submeΥ`` ? Subme.py 21
submeΥ`` ? Subme.py 22 1 AddRoundKey 2 Substitution 3 Permutation
submeΥ`` ? Subme.py 23 1 AddRoundKey 2 Substitution 3 Permutation AESͬSPN
submeΥ`` ? hζϡӛȶx 24 Step 1 Step 2 Step 3
SubmeΘ Step1 Plaintext (P) Key (K) Ciphertext (C) Step2 Step3 25
Subme Step1 Input Key (K) Output S S S S S S S S Permutation 26
Subme Step1 Input Key (K) Output S S S S S S S S Permutation 1-2 S-boxQ =Substitution 1-3 ÓQƩ`֥Q =Permutation 1-1 I΂XoR =AddRoundKey 27
Subme Step2 Input Key (K) Output S S S S S S S S Permutation 1-2 S-boxQ =Substitution 1-3 ÓQƩ`֥Q =Permutation 1-1 I΂XoR =AddRoundKey Step2Step1ͬI 28
Subme Step3 Input Key (K) Output 3-1 bytegλ ǥЩ` 3-2 I΂㤹 Ϥ֤ϒΤƤ Add 29
Subme ȫQ Output S S S S S S S S Permutation S S S S S S S S Permutation + ƽ 30
[ْ] AESȫQ S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation ƽ 31
^ S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S Permutation S S S S S S S S Permutation AES subme 32
^ S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S Permutation S S S S S S S S Permutation AES subme SubmeϽ⤱ʚݤ룡 33
^ ? 饦 ? AES-128:10饦 ? Subme:2饦 ? QI ? Substitution ? AES: [0x63, 0x7c, 0x77,.,0xbb, 0x16] ? Subme: [0x63, 0x7c, 0x77,.,0xbb, 0x16] ? Permutation ?AES: Shift-Rows&MixColumns ?Subme: bitK椨 AESͬIǥ饦٤ʤ ʮI󤬻줶ΤǤϣ 34
mФʔ Key (K) Key (K) Ż Ż ? I?ƽģmФʔ褬ǤƤʤ ĤI󤬲Ф 35
ֽ Plaintext A Plaintext A + S Key (K) Key (K) Ż Ż diff ˲ ? I?ƽģڥ˲֤뤨 ? vʤ 󤬵ä 36
SubmevҊƤ S S S S S S S S Permutation S S S S S S S S Permutation + ƽ ? StepȤvҊƤ 37
x Output S S S S S S S S Permutation S S S S S S S S Permutation + ƽ K1 K2 K3 C11 C12 C13 C21 C22 C23 C31 C=C33 38
SubmevStep 1 Input Key (K) Output S S S S S S S S Permutation 1-2 S-boxQ =Substitution 1-3 ÓQƩ`֥Q =Permutation 1-1 I΂XoR =AddRoundKey C11 C12 C13 39
SubmevStep 1 Input Output S S S S S S S S Permutation Key (K) C111byte֤뤨 Key (K) Permutationǔ 8bitˤӰ푤ʤ Key (K) S-boxǷǾΉQ뤬 byteӰ푤Ϥʤ C11 C12 C13 40
Submev(Step1) S S S S S S S S Permutation S S S S S S S S Permutation Perm(S(A)) Perm(S(A+S)) diff A A + S B 41
Submeβ(Step1) diff β֥ѥ`B C11ضڥAA+SǤԤߤ ? = ? ??????˲֥ѥ` ?????˲ ? ?[?????˲] ?[??????˲֥ѥ`] 42
ԭ (Step1) ? ǰ᣺Τ״r򁢶 ؤͬ״r ? ߤIϤ狼ʤ ? ƽĤˌꤷĤȡÿܣxkƽĹģ 43
ԭ (Step1) ? ֨SQ ? C11ڥ(A, A+S)Q֥ѥ`Bȡ 44 S S S S S S S S Permutation S S S S S S S S Permutation C11[0] = A C11[0] = A + S K diff B
ԭ (Step1) S S S S S S S S Permutation S S S S S S S S Permutation ? ӛƽĤ(Ҥ{0,..,255}΂) K 45 P[0] = A+ P[0] = A+S+
ԭ (Step1) S S S S S S S S Permutation S S S S S S S S Permutation ? K[0]ΤȤ:Ȥˤʤ K 46 P[0] = A+ P[0] = A+S+ A + + K[0] A + S + + K[0]
ԭ (Step1) S S S S S S S S Permutation S S S S S S S S Permutation ? = K[0]ΤȤ:ѥ`󤬳룡 K 47 P[0] = A+ P[0] = A+S+ A + K[0] + K[0] = A A + S + K[0] + K[0] = A + S
ԭ (Step1) S S S S S S S S Permutation S S S S S S S S Permutation ? = K[0]ΤȤ:ѥ`󤬳룡 K 48 P[0] = A+ P[0] = A+S+ A + K[0] + K[0] = A A + S + K[0] + K[0] = A + S Ĥضβ֥ѥ`BH ƽĤβ֦Ҥ΂I1ХȤƜyܣ
Fgstep2ؤ S S S S S S S S Permutation S S S S S S S S Permutation 1byteĿ˲ Step1K˕r 8bit Step2K˕r ȫˎڤ g֤뤨Ǥ Step2K˕r ȫ˔褵 Ť餤 Step1ַ Εrγ ä뤳Ȥǰ 49
Fgstep2ؤ S S S S S S S S Permutation S S S S S S S S Permutation 1byteĿ˲ Step1K˕r 8bit Step2K˕r ȫˎڤ g֤뤨Ǥ Step2K˕r ȫ˔褵 Ť餤 Step1ַ Εrγ ä뤳ǰ 50 Step2،gʩ뤳Ȥ ߜgߣ
? } ? 1ؤStepʤIƜy ? 2ؤStepgʩIƜyy 51 S S S S S S S S Permutation S S S S S S S S Permutation Step2ؤ byteˎڤ Ȥ}
? } ? 1ؤStepʤIƜy ? 2ؤStepgʩIƜyy ? ? Step1γڤʤ ? Step2γStep1ͬȤ 52 S S S S S S S S Permutation S S S S S S S S Permutation ϤΤ褤I 򤹤Step1 Step1γ 1byteˤ ڤʤ Step2γ ȤStep1ͬȤ
? } ? 1ؤStepʤIƜy ? 2ؤStepgʩIƜyy ? ? Step1γڤʤ ? Step2γStep1ͬȤ 53 S S S S S S S S Permutation ȫ ڤäƤޤ ֤ 1bitˤƤߤ S S S S S S S S Permutation S-box byte-to-byteQ
? } ? 1ؤStepʤIƜy ? 2ؤStepgʩIƜyy ? ? Step1γڤʤ ? Step2γStep1ͬȤ 54 S S S S S S S S Permutation ȫ ڤäƤޤ ֤ 1bitˤƤߤ S S S S S S S S Permutation S-box byte-to-byteQ ͣ
? } ? 1ؤStepʤIƜy ? 2ؤStepgʩIƜyy ? ? Step1γڤʤ ? Step2γStep1ͬȤ 55 S S S S S S S S Permutation IiǤ ѥ`󤬳 β֤ 1bitǤ S S S S S S S S Permutation PermutationǤ Ӱ푹ώڤʤ
? } ? 1ؤStepʤIƜy ? 2ؤStepgʩIƜyy ? ? Step1γڤʤ ? Step2γStep1ͬȤ 56 S S S S S S S S Permutation IiǤ ѥ`󤬳 β֤ 1bitǤ S S S S S S S S Permutation PermutationǤ Ӱ푹ώڤʤ ȤԤäƤ ֱڲ״B ʤ
? } ? 1ؤStepʤIƜy ? 2ؤStepgʩIƜyy ? ? Step1γڤʤ ? Step2γStep1ͬȤ ? ? S-box1ͨ^1bit֤ ߳ƽĥڥ ? ضγ֤̽ 57 S S S S S S S S Permutation S S S S S S S S Permutation S-boxͨ^1bit֤ 褦ƽĥڥ ضγ ֥ѥ`򥲥åȣ
ƽĤ귽 S S S S S S S S Permutation S S S S S S S S Permutation ? gH˲֤״B K 58 C12[0] = D C12[0] = D+1
ƽĤ귽 S S S S S S S S Permutation S S S S S S S S Permutation ? gH˲֤״B K 59 C12[0] = D C12[0] = D+1 C11[0] = inv_S[D] C12[0] = inv_S[D+1]
ƽĤ귽 S S S S S S S S Permutation S S S S S S S S Permutation ? gH˲֤״B K 60 C12[0] = D C12[0] = D+1 C11[0] = inv_S[D] C12[0] = inv_S[D+1] P[0] = inv_S[D]+ P[0] = inv_S[D+1]+
ƽĤ귽 S S S S S S S S Permutation S S S S S S S S Permutation ? gH˲֤״B K 61 C12[0] = D C12[0] = D+ 1 C11[0] = inv_S[D] C12[0] = inv_S[D+1] P[0] = inv_S[D]+ P[0] = inv_S[D+1]+ =K[0]ΤȤĤ ضβ֥ѥ`B Ҥ΂I1ХȤƜyܣ
K1, K2Iiܣ S S S S S S S S Permutation S S S S S S S S Permutation 1) 혴ԇƤ ȤK1i 62 2)ͬ gʩ뤳Ȥ K2i
K1, K2Iiܣ S S S S S S S S Permutation S S S S S S S S Permutation 1) 혴ԇƤ ȤK1i 63 2)ͬ gʩ뤳Ȥ K2i ʤƤʤ
Submev(Step3) ? I΄IXoRǤϤʤAdd ? 2MҊHϤθk ? XoRDz֤ȤäH˥Υ줸 ? ֤ȤHϤRҪ Input = Step2γ Key (K) Output 3-1 bytegλ ǥЩ` 3-2 I΂㤹 Ϥ֤ϒΤƤ Add 64
Submev(Step3) ? ⤷K3XoRǤStep2γXoRdz Input = Step2γ Output 65 Input = Step2γ Output diff
Submev(Step3) ? ⤷K3AddǤStep2γXoRdz Input = Step2γ Output 66 Input = Step2γ Output diff 㤷ʤΤXoR Step2γʤ
AddXoR` ? XoRΈ 0 0 0 0 67 C C 0 1 0 0 1 1 0 1 0 K3 0 1 0 0 1 1 0 1 0 K3 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 1 1 C23 C23 XoR XoR
AddXoR` ? XoRΈ 0 0 0 0 ĤXoR 0 0 0 0 1 0 1 1 0 68 C C 0 1 0 0 1 1 0 1 0 K3 0 1 0 0 1 1 0 1 0 K3 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 1 1 C23 C23 XoR XoR C23XoR 0 0 0 0 1 0 1 1 0 ڴ֥ѥ`֥ѥ`
AddXoR` ? XoRΈ 0 0 0 0 ĤXoR 0 0 0 0 1 0 1 1 0 69 C C 0 1 0 0 1 1 0 1 0 K3 0 1 0 0 1 1 0 1 0 K3 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 1 1 C23 C23 XoR XoR C23XoR 0 0 0 0 1 0 1 1 0 ڴ֥ѥ`֥ѥ` K3XoRǤаĥڥXoR C23, C23XoRһ¤
AddXoR` ? AddΈ 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 70 C C 0 1 0 0 1 1 0 1 0 K3 0 1 0 0 1 1 0 1 0 K3 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 1 1 C23 C23 Add Add
AddXoR` ? AddΈ 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 71 C C 0 1 0 0 1 1 0 1 0 K3 0 1 0 0 1 1 0 1 0 K3 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 1 1 C23 C23 Add Add ĤXoR 1 1 1 1 1 0 0 1 0 C23XoR 0 0 0 0 1 0 1 1 0 ڴ֥ѥ`֥ѥ`
AddXoR` ? AddΈ 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 72 C C 0 1 0 0 1 1 0 1 0 K3 0 1 0 0 1 1 0 1 0 K3 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 1 1 C23 C23 Add Add ĤXoR 1 1 1 1 1 0 0 1 0 C23XoR 0 0 0 0 1 0 1 1 0 ڴ֥ѥ`֥ѥ` K3AddʤΤǰĥڥXoR C23, C23XoRһ¤ʤ
AddXoR` ? AddXoR` = RϤ XoR 1 1 1 1 0 0 1 0 0 73 0 0 0 0 1 0 1 1 0 1 1 1 1 1 0 0 1 0 C23,C23β Addγ Addγ֣RϤ꣩؏ ?C23,C23β֤1äƤԽ1 ?ؤBAƳ
trmrStep3 ? ӛַRe ? äȤϤϤ 1 0 0 1 0 0 0 0 1 74 ǰC23,C23 ֥ѥ`ȡ
trmrStep3 ? ӛַRe ? äȤϤϤ 1 0 0 1 0 0 0 0 1 75 ǰC23,C23 ֥ѥ`ȡ 1 0 1 0 0 1 0 1 1 ƽĥڥP[0], P[0] diffY XoR 0 0 1 1 0 1 0 1 0XoRYΤ _J ?C23,C231 ƤBA 1äƤ뤫 NG
٤ƤIi S S S S S S S S Permutation S S S S S S S S Permutation + ? StepȤI򌧳 76 1) 혴ԇƤ ȤK1i 2) 혴ԇƤ ȤK2i 3)K3 = C C23
g ? ȤꤢäƤߤޤ礦 ? ȤwriteupB餷ޤ ? trmr棺http://pastebin.com/WQdc2knT ? MSLC棺http://mslc.ctf.su/wp/gits-ctf-2013-crypto-500 ? 狼ˤϥäƤ ? Ф30֤ˤʤäwriteupΥ`ɽh褦˼äƤޤ ? `ɤǤʤΤǤޤꤿʤǤ ? lֱ ? S˥ꥯȤ@trmr105ޤ#katagaitaiǥ `ȤƤ 9077
trmrSubmeν⤭ ? ֤ʹä⤭Ϥ롢˼ ? ޤһ 78
trmrSubmeν⤭ ? 1) C12β֥ꥹȤGET 79 C121bit`C221byteʤ롣 줾γ֤submepermutation Ʃ`֥С֥ꥹȤȤʤ
trmrSubmeν⤭ ? 2) I` 80 C12Ȳ1ӥåȤC12 Inv_SQΤ򰵺Ż ꥹȄIƤΤϡ `ؓɤӋٶȤΤ diff֥ꥹȤ ¤Ƥ뤫å
trmrSubmeν⤭ ? 3) ֥å (MSLC󥹥ѥ) ? ʉäȤϤƤʤ 81 ֥ꥹȤΈԽ RϤοԤ gHγ֤ȥꥹȤ` BAʤRϤ Ԥʤʤäȁ RϤοԤʤ״B ֤ȥꥹȤ` NG
? Key{HackerLikesHakkaAme} ? k1||k2||k3[::-1]΂ ? Flag{HackTheKatagaitai!} ? ȡ㏊Ά}`ФǤäƤޤ 82
[Մ]դtrmr ? Step3 ? IAdd ? AddXoRȸߤv ? 2Ĥγβ֤ȤФۤ ? Step1,2 ? S-box s = [0x63, 0x7c, 0x77,.,0xbb, 0x16] AESͬs-box ? Permutation bit΁K椨 ? gʩ ? Step3Ϥäoҕ2Step1ͨäȳĿ ? ֤뤨ڥɤv ⤱ʤä Τ֤뤨ơ ΥڥXoRƤС פv AESͬs-box äȫȁ ÓQƩ`֥ 1byte`8bit˔ 1ؤΥ饦ɤǴ󤭤 褹櫓ǤϤʤ 83
ο ? ο ? More Smoked Leet Chicken ? http://mslc.ctf.su/wp/gits-ctf-2013-crypto-500/ ? Wikipedia[ӢZ] ? https://en.wikipedia.org/wiki/Advanced_Encryption_Standard ? żgȫ (åץǩ`ϣ) ? Փ 84
Writeup & Impression85 ? ㏊gʩreconҊĤwriteupǤ ? http://fish.minidns.net/news/55 ? kanataˤ롣핽⤤ƤƤϤ ? http://qiita.com/kusano_k/items/33d3d634f80a4999a400 ? kusano_kˤwriteup3ĿΌI䤨ƤΤ Ǥ ? https://bitbucket.org/snippets/nomeaning777/kEK5j ? no_meaningˤwriteuprubyˤӛ3ĿΌ I䤨Ƥޤ͡ ? dƤʤˡ˽ReconǤʤ ? ⤷writeuptwitterȤBjޤ

More Related Content

katagaitai CTF㏊ #3 crypto

  • 2. ע ? 饤ɤ㏊äΤԪɤƤޤ ? ㏊Ǥφ}`ФäޤȤֹͣƤޤ ? }`ФIPۥƤwޤri 椨ޤ ? ФȤ⤯ ? }ӛURLäƤޤ ? http://pastebin.com/Ea3Gm8w2 ? Υک`㏊μ־writeupdƤޤ ? ˽writeup100ʤΤǡҤդƤ 2
  • 5. katagaitaig ? ذk ? bata(@bata_24) `` ? trmr(@trmr105) 󥻥 ? Yϥӥ` ? askn(@asai_ken) ` # gˤY餷 # tl֪ʤ We are katagaitai! 5
  • 6. դΆ} ? [Ghost in the shellcode CTF 2013] Q20 - Subme CODE 6
  • 7. subme٤4Ĥ ? ͨIŤ ? _IŤν⤭ѥ`󻯤Ƥ놖} ? ޤwriteupʤ ? MSLCwriteupҊĤ󤫤ä ? ֤MMAäԔwriteupƤϤ ? ŽƤ뤫 ? }⤯^̤gHΰť르ꥺ˽ݤ ? Ά}ˤĤƤƤʤ ? Ƥ׷Ƥ ? ͎ĿָB 7
  • 8. Ά} ? ޤϤ˴ΤSHA1ϥåҪ󤵤 ? SHA1ϥåĩβ16ӥåȤ1 ? 뤨줿Фʼޤ ? L21Х ? T餷ˤäƤߤޤ礦 ? Kä醖}⤭ʼƤ 208
  • 9. ͨIŤȹ_I ? ͨI C ͨIäưŻ/ͺŤgʩ ? _I C ŻȏͺŤˮʤI 9
  • 10. ͨIŤΥƥ` ? 夳Τ褦ʥƥ櫓Ǥ루Ϥ ? ȥ`వ ? LFSRͣsnow, K-Cipher2 etc. ? ״BwͣRC4, trivium, chacha-20 etc. ? ֥å ? Feistel죺DES, MISTY, Camellia etc. ? SPN죺AES, Serpent etc. դϤ 10
  • 13. SPNθҪ ? Substitution ? Ǿvj ? СgλХȣȤ˄I뤳Ȥत ? ÓQƩ`֥루S-boxä뤳Ȥत ? Permutation ? ȫ򥷥åե뤷Ӱ푤ڹ ? ֥åȫˌI Input S S S S S S S S Permutation 13
  • 14. SPNθҪ ? Substitution ? Ǿvj ? СgλХȣȤ˄I뤳Ȥत ? ÓQƩ`֥루S-boxä뤳Ȥत ? Permutation ? ȫ򥷥åե뤷Ӱ푤ڹ ? ֥åȫˌI S S S S S S S S Permutation 1byte` ȫӰ 14
  • 15. AESҊƤ ? AES: Advanced Encryption Standard ? ԪRijndaelǩ`룿饤`룿 ? 2001FIPS197׹˜ʤʤΤ˥٥륮`u ? 128, 192, 256bitꡢ΢˘` 15
  • 16. AESΘ ? AES: Advanced Encryption Standard ? ڻȤ ? KEY EXPANTION ? ͨIȤӛI1饦ɤȤ ? AddRoundKey ? SubBytes ? ShiftRows ? MixColumns ? ӛI10饦R귵(128bitΈ) 16
  • 17. AESΘ (1饦) Input Key (K) (expanded) Output S S S S S S S S MixColumns 1 AddRoundKey 2 SubBytes ShiftRows 3 ShiftRows 4 MixColumns 17
  • 18. AESΘ (1饦) Input Key (K) (expanded) Output S S S S S S S S MixColumns 1 AddRoundKey 2 SubBytes Substitution ShiftRows 3 ShiftRows Permutation 4 MixColumns Permutation Permutation 18
  • 19. AESȫQ S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation ƽ 19
  • 20. AESȫQ S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation ƽ AESΤϤɤ 20
  • 22. submeΥ`` ? Subme.py 22 1 AddRoundKey 2 Substitution 3 Permutation
  • 23. submeΥ`` ? Subme.py 23 1 AddRoundKey 2 Substitution 3 Permutation AESͬSPN
  • 26. Subme Step1 Input Key (K) Output S S S S S S S S Permutation 26
  • 27. Subme Step1 Input Key (K) Output S S S S S S S S Permutation 1-2 S-boxQ =Substitution 1-3 ÓQƩ`֥Q =Permutation 1-1 I΂XoR =AddRoundKey 27
  • 28. Subme Step2 Input Key (K) Output S S S S S S S S Permutation 1-2 S-boxQ =Substitution 1-3 ÓQƩ`֥Q =Permutation 1-1 I΂XoR =AddRoundKey Step2Step1ͬI 28
  • 29. Subme Step3 Input Key (K) Output 3-1 bytegλ ǥЩ` 3-2 I΂㤹 Ϥ֤ϒΤƤ Add 29
  • 30. Subme ȫQ Output S S S S S S S S Permutation S S S S S S S S Permutation + ƽ 30
  • 31. [ْ] AESȫQ S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation ƽ 31
  • 32. ^ S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S Permutation S S S S S S S S Permutation AES subme 32
  • 33. ^ S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S ShiftRowsPermutation S S S S S S S S Permutation S S S S S S S S Permutation AES subme SubmeϽ⤱ʚݤ룡 33
  • 34. ^ ? 饦 ? AES-128:10饦 ? Subme:2饦 ? QI ? Substitution ? AES: [0x63, 0x7c, 0x77,.,0xbb, 0x16] ? Subme: [0x63, 0x7c, 0x77,.,0xbb, 0x16] ? Permutation ?AES: Shift-Rows&MixColumns ?Subme: bitK椨 AESͬIǥ饦٤ʤ ʮI󤬻줶ΤǤϣ 34
  • 35. mФʔ Key (K) Key (K) Ż Ż ? I?ƽģmФʔ褬ǤƤʤ ĤI󤬲Ф 35
  • 36. ֽ Plaintext A Plaintext A + S Key (K) Key (K) Ż Ż diff ˲ ? I?ƽģڥ˲֤뤨 ? vʤ 󤬵ä 36
  • 37. SubmevҊƤ S S S S S S S S Permutation S S S S S S S S Permutation + ƽ ? StepȤvҊƤ 37
  • 38. x Output S S S S S S S S Permutation S S S S S S S S Permutation + ƽ K1 K2 K3 C11 C12 C13 C21 C22 C23 C31 C=C33 38
  • 39. SubmevStep 1 Input Key (K) Output S S S S S S S S Permutation 1-2 S-boxQ =Substitution 1-3 ÓQƩ`֥Q =Permutation 1-1 I΂XoR =AddRoundKey C11 C12 C13 39
  • 40. SubmevStep 1 Input Output S S S S S S S S Permutation Key (K) C111byte֤뤨 Key (K) Permutationǔ 8bitˤӰ푤ʤ Key (K) S-boxǷǾΉQ뤬 byteӰ푤Ϥʤ C11 C12 C13 40
  • 41. Submev(Step1) S S S S S S S S Permutation S S S S S S S S Permutation Perm(S(A)) Perm(S(A+S)) diff A A + S B 41
  • 42. Submeβ(Step1) diff β֥ѥ`B C11ضڥAA+SǤԤߤ ? = ? ??????˲֥ѥ` ?????˲ ? ?[?????˲] ?[??????˲֥ѥ`] 42
  • 43. ԭ (Step1) ? ǰ᣺Τ״r򁢶 ؤͬ״r ? ߤIϤ狼ʤ ? ƽĤˌꤷĤȡÿܣxkƽĹģ 43
  • 44. ԭ (Step1) ? ֨SQ ? C11ڥ(A, A+S)Q֥ѥ`Bȡ 44 S S S S S S S S Permutation S S S S S S S S Permutation C11[0] = A C11[0] = A + S K diff B
  • 45. ԭ (Step1) S S S S S S S S Permutation S S S S S S S S Permutation ? ӛƽĤ(Ҥ{0,..,255}΂) K 45 P[0] = A+ P[0] = A+S+
  • 46. ԭ (Step1) S S S S S S S S Permutation S S S S S S S S Permutation ? K[0]ΤȤ:Ȥˤʤ K 46 P[0] = A+ P[0] = A+S+ A + + K[0] A + S + + K[0]
  • 47. ԭ (Step1) S S S S S S S S Permutation S S S S S S S S Permutation ? = K[0]ΤȤ:ѥ`󤬳룡 K 47 P[0] = A+ P[0] = A+S+ A + K[0] + K[0] = A A + S + K[0] + K[0] = A + S
  • 48. ԭ (Step1) S S S S S S S S Permutation S S S S S S S S Permutation ? = K[0]ΤȤ:ѥ`󤬳룡 K 48 P[0] = A+ P[0] = A+S+ A + K[0] + K[0] = A A + S + K[0] + K[0] = A + S Ĥضβ֥ѥ`BH ƽĤβ֦Ҥ΂I1ХȤƜyܣ
  • 49. Fgstep2ؤ S S S S S S S S Permutation S S S S S S S S Permutation 1byteĿ˲ Step1K˕r 8bit Step2K˕r ȫˎڤ g֤뤨Ǥ Step2K˕r ȫ˔褵 Ť餤 Step1ַ Εrγ ä뤳Ȥǰ 49
  • 50. Fgstep2ؤ S S S S S S S S Permutation S S S S S S S S Permutation 1byteĿ˲ Step1K˕r 8bit Step2K˕r ȫˎڤ g֤뤨Ǥ Step2K˕r ȫ˔褵 Ť餤 Step1ַ Εrγ ä뤳ǰ 50 Step2،gʩ뤳Ȥ ߜgߣ
  • 51. ? } ? 1ؤStepʤIƜy ? 2ؤStepgʩIƜyy 51 S S S S S S S S Permutation S S S S S S S S Permutation Step2ؤ byteˎڤ Ȥ}
  • 52. ? } ? 1ؤStepʤIƜy ? 2ؤStepgʩIƜyy ? ? Step1γڤʤ ? Step2γStep1ͬȤ 52 S S S S S S S S Permutation S S S S S S S S Permutation ϤΤ褤I 򤹤Step1 Step1γ 1byteˤ ڤʤ Step2γ ȤStep1ͬȤ
  • 53. ? } ? 1ؤStepʤIƜy ? 2ؤStepgʩIƜyy ? ? Step1γڤʤ ? Step2γStep1ͬȤ 53 S S S S S S S S Permutation ȫ ڤäƤޤ ֤ 1bitˤƤߤ S S S S S S S S Permutation S-box byte-to-byteQ
  • 54. ? } ? 1ؤStepʤIƜy ? 2ؤStepgʩIƜyy ? ? Step1γڤʤ ? Step2γStep1ͬȤ 54 S S S S S S S S Permutation ȫ ڤäƤޤ ֤ 1bitˤƤߤ S S S S S S S S Permutation S-box byte-to-byteQ ͣ
  • 55. ? } ? 1ؤStepʤIƜy ? 2ؤStepgʩIƜyy ? ? Step1γڤʤ ? Step2γStep1ͬȤ 55 S S S S S S S S Permutation IiǤ ѥ`󤬳 β֤ 1bitǤ S S S S S S S S Permutation PermutationǤ Ӱ푹ώڤʤ
  • 56. ? } ? 1ؤStepʤIƜy ? 2ؤStepgʩIƜyy ? ? Step1γڤʤ ? Step2γStep1ͬȤ 56 S S S S S S S S Permutation IiǤ ѥ`󤬳 β֤ 1bitǤ S S S S S S S S Permutation PermutationǤ Ӱ푹ώڤʤ ȤԤäƤ ֱڲ״B ʤ
  • 57. ? } ? 1ؤStepʤIƜy ? 2ؤStepgʩIƜyy ? ? Step1γڤʤ ? Step2γStep1ͬȤ ? ? S-box1ͨ^1bit֤ ߳ƽĥڥ ? ضγ֤̽ 57 S S S S S S S S Permutation S S S S S S S S Permutation S-boxͨ^1bit֤ 褦ƽĥڥ ضγ ֥ѥ`򥲥åȣ
  • 58. ƽĤ귽 S S S S S S S S Permutation S S S S S S S S Permutation ? gH˲֤״B K 58 C12[0] = D C12[0] = D+1
  • 59. ƽĤ귽 S S S S S S S S Permutation S S S S S S S S Permutation ? gH˲֤״B K 59 C12[0] = D C12[0] = D+1 C11[0] = inv_S[D] C12[0] = inv_S[D+1]
  • 60. ƽĤ귽 S S S S S S S S Permutation S S S S S S S S Permutation ? gH˲֤״B K 60 C12[0] = D C12[0] = D+1 C11[0] = inv_S[D] C12[0] = inv_S[D+1] P[0] = inv_S[D]+ P[0] = inv_S[D+1]+
  • 61. ƽĤ귽 S S S S S S S S Permutation S S S S S S S S Permutation ? gH˲֤״B K 61 C12[0] = D C12[0] = D+ 1 C11[0] = inv_S[D] C12[0] = inv_S[D+1] P[0] = inv_S[D]+ P[0] = inv_S[D+1]+ =K[0]ΤȤĤ ضβ֥ѥ`B Ҥ΂I1ХȤƜyܣ
  • 62. K1, K2Iiܣ S S S S S S S S Permutation S S S S S S S S Permutation 1) 혴ԇƤ ȤK1i 62 2)ͬ gʩ뤳Ȥ K2i
  • 63. K1, K2Iiܣ S S S S S S S S Permutation S S S S S S S S Permutation 1) 혴ԇƤ ȤK1i 63 2)ͬ gʩ뤳Ȥ K2i ʤƤʤ
  • 64. Submev(Step3) ? I΄IXoRǤϤʤAdd ? 2MҊHϤθk ? XoRDz֤ȤäH˥Υ줸 ? ֤ȤHϤRҪ Input = Step2γ Key (K) Output 3-1 bytegλ ǥЩ` 3-2 I΂㤹 Ϥ֤ϒΤƤ Add 64
  • 65. Submev(Step3) ? ⤷K3XoRǤStep2γXoRdz Input = Step2γ Output 65 Input = Step2γ Output diff
  • 66. Submev(Step3) ? ⤷K3AddǤStep2γXoRdz Input = Step2γ Output 66 Input = Step2γ Output diff 㤷ʤΤXoR Step2γʤ
  • 67. AddXoR` ? XoRΈ 0 0 0 0 67 C C 0 1 0 0 1 1 0 1 0 K3 0 1 0 0 1 1 0 1 0 K3 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 1 1 C23 C23 XoR XoR
  • 68. AddXoR` ? XoRΈ 0 0 0 0 ĤXoR 0 0 0 0 1 0 1 1 0 68 C C 0 1 0 0 1 1 0 1 0 K3 0 1 0 0 1 1 0 1 0 K3 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 1 1 C23 C23 XoR XoR C23XoR 0 0 0 0 1 0 1 1 0 ڴ֥ѥ`֥ѥ`
  • 69. AddXoR` ? XoRΈ 0 0 0 0 ĤXoR 0 0 0 0 1 0 1 1 0 69 C C 0 1 0 0 1 1 0 1 0 K3 0 1 0 0 1 1 0 1 0 K3 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 1 1 C23 C23 XoR XoR C23XoR 0 0 0 0 1 0 1 1 0 ڴ֥ѥ`֥ѥ` K3XoRǤаĥڥXoR C23, C23XoRһ¤
  • 70. AddXoR` ? AddΈ 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 70 C C 0 1 0 0 1 1 0 1 0 K3 0 1 0 0 1 1 0 1 0 K3 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 1 1 C23 C23 Add Add
  • 71. AddXoR` ? AddΈ 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 71 C C 0 1 0 0 1 1 0 1 0 K3 0 1 0 0 1 1 0 1 0 K3 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 1 1 C23 C23 Add Add ĤXoR 1 1 1 1 1 0 0 1 0 C23XoR 0 0 0 0 1 0 1 1 0 ڴ֥ѥ`֥ѥ`
  • 72. AddXoR` ? AddΈ 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 72 C C 0 1 0 0 1 1 0 1 0 K3 0 1 0 0 1 1 0 1 0 K3 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 1 1 C23 C23 Add Add ĤXoR 1 1 1 1 1 0 0 1 0 C23XoR 0 0 0 0 1 0 1 1 0 ڴ֥ѥ`֥ѥ` K3AddʤΤǰĥڥXoR C23, C23XoRһ¤ʤ
  • 73. AddXoR` ? AddXoR` = RϤ XoR 1 1 1 1 0 0 1 0 0 73 0 0 0 0 1 0 1 1 0 1 1 1 1 1 0 0 1 0 C23,C23β Addγ Addγ֣RϤ꣩؏ ?C23,C23β֤1äƤԽ1 ?ؤBAƳ
  • 74. trmrStep3 ? ӛַRe ? äȤϤϤ 1 0 0 1 0 0 0 0 1 74 ǰC23,C23 ֥ѥ`ȡ
  • 75. trmrStep3 ? ӛַRe ? äȤϤϤ 1 0 0 1 0 0 0 0 1 75 ǰC23,C23 ֥ѥ`ȡ 1 0 1 0 0 1 0 1 1 ƽĥڥP[0], P[0] diffY XoR 0 0 1 1 0 1 0 1 0XoRYΤ _J ?C23,C231 ƤBA 1äƤ뤫 NG
  • 76. ٤ƤIi S S S S S S S S Permutation S S S S S S S S Permutation + ? StepȤI򌧳 76 1) 혴ԇƤ ȤK1i 2) 혴ԇƤ ȤK2i 3)K3 = C C23
  • 77. g ? ȤꤢäƤߤޤ礦 ? ȤwriteupB餷ޤ ? trmr棺http://pastebin.com/WQdc2knT ? MSLC棺http://mslc.ctf.su/wp/gits-ctf-2013-crypto-500 ? 狼ˤϥäƤ ? Ф30֤ˤʤäwriteupΥ`ɽh褦˼äƤޤ ? `ɤǤʤΤǤޤꤿʤǤ ? lֱ ? S˥ꥯȤ@trmr105ޤ#katagaitaiǥ `ȤƤ 9077
  • 81. trmrSubmeν⤭ ? 3) ֥å (MSLC󥹥ѥ) ? ʉäȤϤƤʤ 81 ֥ꥹȤΈԽ RϤοԤ gHγ֤ȥꥹȤ` BAʤRϤ Ԥʤʤäȁ RϤοԤʤ״B ֤ȥꥹȤ` NG
  • 82. ? Key{HackerLikesHakkaAme} ? k1||k2||k3[::-1]΂ ? Flag{HackTheKatagaitai!} ? ȡ㏊Ά}`ФǤäƤޤ 82
  • 83. [Մ]դtrmr ? Step3 ? IAdd ? AddXoRȸߤv ? 2Ĥγβ֤ȤФۤ ? Step1,2 ? S-box s = [0x63, 0x7c, 0x77,.,0xbb, 0x16] AESͬs-box ? Permutation bit΁K椨 ? gʩ ? Step3Ϥäoҕ2Step1ͨäȳĿ ? ֤뤨ڥɤv ⤱ʤä Τ֤뤨ơ ΥڥXoRƤС פv AESͬs-box äȫȁ ÓQƩ`֥ 1byte`8bit˔ 1ؤΥ饦ɤǴ󤭤 褹櫓ǤϤʤ 83
  • 84. ο ? ο ? More Smoked Leet Chicken ? http://mslc.ctf.su/wp/gits-ctf-2013-crypto-500/ ? Wikipedia[ӢZ] ? https://en.wikipedia.org/wiki/Advanced_Encryption_Standard ? żgȫ (åץǩ`ϣ) ? Փ 84
  • 85. Writeup & Impression85 ? ㏊gʩreconҊĤwriteupǤ ? http://fish.minidns.net/news/55 ? kanataˤ롣핽⤤ƤƤϤ ? http://qiita.com/kusano_k/items/33d3d634f80a4999a400 ? kusano_kˤwriteup3ĿΌI䤨ƤΤ Ǥ ? https://bitbucket.org/snippets/nomeaning777/kEK5j ? no_meaningˤwriteuprubyˤӛ3ĿΌ I䤨Ƥޤ͡ ? dƤʤˡ˽ReconǤʤ ? ⤷writeuptwitterȤBjޤ