Apokryptografisi kryptografimenou arxeiou me ksexasmeno password
Christos Ricudis
ricudis at itc.auth.gr
Fri Jun 20 15:19:45 EEST 2008
Antonis Christofides wrote:
>> To 1985, xlwmo na xrhsimopoiousan kapoion estw kai psilo-soi
>> encryption algori8mo, opote mallon 8anai kapoio aplo XOR, opote
>> xwraei xalara kryptanalysh, kai mallon 8a nai kai poly eykolo to
>> reverse engineering tou .com. Gia steile mou ta arxeia na ta koitaksw
>> ligo.
>>
>> Ta dedomena einai toso polytima pou na aksizei ton kopo na to
>> spaseis?
>>
>
> Λοιπόν, έπαιξα λίγο με το crypt.com και διαπιστώνω ότι ο αλγόριθμος
> είναι απίστευτα γελοίος. Δεν μπορώ να τον καταλάβω όμως :-) Αλλά
> καταλαβαίνω ότι είναι της πλάκας. Δυστυχώς δεν θέλω να σου στείλω τα
> κρυπτογραφημένα αρχεία γιατί είναι πολύ προσωπικά (εν τω μεταξύ δεν
> θυμάμαι και τι λένε ακριβώς :-). Αλλά σου στέλνω το crypt.com μήπως
> του κάνεις reverse engineering. Αν έχεις εμπειρία σε δυαδικά και xor,
> μάλλον θα τον βρεις γρήγορα. Αν μου πεις τον αλγόριθμο, μετά πιστεύω
> ότι θα μπορέσω να τα αποκρυπτογραφήσω μόνος μου.
>
>
Exei plaka na prospa8hseis na to kryptanalyseis xwris na deis ton kwdika
tou, alla mono ta input/output associations :
plaintext 111111111111111111111111111111111111111111111
key 1
result HNC217NHNC217NHNC217NHNC217NHNC217NHNC217NHNC
plaintext 1111111 1111111 1111111 1111111 1111111 1111111 11111
key 11
result HNC217N HNC217N HNC217N HNC217N HNC217N HNC217N HNC21
(ara h kryptografhsh einai aneksarthth tou key length.
Parathroume thn periodo twn 7 bytes)
plaintext : 1111111 1111111 1111111 1211111 1111111
key : 1
result : HNC217N HNC217N HNC217N HMC217N HNC217N
plaintext : 1111111 1111111 1111111 1211111 1111111
key : 11
result : HNC217N HNC217N HNC217N HMC217N HNC217N
Edw parathroume oti to "2" sto plaintext, ephreazei men to apotelesma,
alla mono *sth 8esh pou brisketai* - to ypoloipo kryptogramma peran tou
"2" sto arxiko plaintext paramenei to idio. Ayto einai shmantiko, giati
mas deixnei oti den ginetai rolling, kai oti genikotera h antistoixia
plaintext kai kryptografhmatos einai ena pros ena - ara prokeitai gia
kryptografhma polyalfabhtikhs antikatastashs, pragma poy 8a mas boh8hsei
parakatw.
plaintext 1111111 1111111 1111111 1111111 1111111 1111111
key 2
result KM at 124M KM at 124M KM at 124M KM at 124M KM at 124M KM at 124M
plaintext 1111111 1111111 1111111 1111111 1111111 1111111
key 0
result JLA035L JLA035L JLA035L JLA035L JLA035L JLA035L
(to key "0" epilexthke epeidh h bitwise timh tou diaferei
kata 1 bit mono apo to "1")
plaintext 1111111 1111111 1111111 1111111 1111111 1111111
key 12
result HMC114N KN at 227M HMC114N KN at 227M HMC114N KN at 227M
(Edw exoume periodo 14 bytes, kai parathroume oti ginetai kapoio mangling
sto kleidi prin thn kryptografhsh - an xrhsimopoioutan opws einai, to "1"
sto kleidi 8a eprepe na prokalei to pattern "HNC217N" sto kryptogramma.
1 2 H N C 2 7
49 50 72 78 67 50 55
00110001 00110010 01001000 01001110 01000011 00110010 00110111
K M @ 1 2 4 M
75 77 64 49 50 52 77
01001011 01001101 01000000 00110001 00110010 00110100 01001101
0 J L A 0 3 5
48 74 76 65 48 51 53
00110000 01001010 01001100 01000001 00110000 00110011 00110101
H N C 2 1 7 N (key = 1)
72 78 67 50 49 55 78
J L A 0 3 5 L (key 0)
74 76 65 48 51 53 76
+2 -2 -2 -2 +2 -2 -2
(edw blepoume oti diafora enos bit sto kleidi mas dinei sta8erh ari8mhtikh
diafora sto kryptografhma, alla to proshmo mas ta xalaei ligo)
K M @ 1 2 4 M (key 2)
75 77 64 49 50 52 77
+3 -1 -3 -3 +1 -3 -1
(ok, edw yparxei ena pattern, alla den einai profanes, opote to paratame)
Psaxnoume mpas kai broume kapoio ari8mhtiko h difyako :P pattern MESA sthn
periodo tou kryptogrammatos
01001000 H
01001110 N
01000011 C
00110010 2
00110001 1
00110111 7
01001010 J
01001100 L
01000001 A
00110000 0
00110011 3
00110101 5
01001100 L
Yparxei kapoio pattern kai edw, alla pali den einai apolyta profanes.
Koitazoume pws h metabolh enos h 2 bits sto kleidi, ephreazei to
kryptogramma :
00110001 00110001 00110001 00110001 00110001 00110001 00110001 ( = 1111111)
00110000 00110000 00110000 00110000 00110000 00110000 00110000 ( = 0000000)
00110010 00110010 00110010 00110010 00110010 00110010 00110010 ( = 2222222)
01001000 01001110 01000011 00110010 00110001 00110111 01001110 ( = HNC217N)
01001010 01001100 01000001 00110000 00110011 00110101 01001100 ( = JLA035L)
01001011 01001101 01000000 00110001 00110010 00110100 01001101 ( = KM at 124M)
Edw blepoume oti allagh enos bit sto kleidi prokalei allagh enos bit sto
kryptogramma, allagh 2 bit sto kleidi prokalei allagh 2 bit sto
kryptogramma, ktl.
Apo ta parakatw odhgoumaste sto symperasma oti kata pasa pi8anothta o
algori8mos einai kati san :
1) Mangle the key to something that provides 7 bytes of output for 1
byte of key.
To something einai kata pasa pi8anothta kapoia aplh grammikh synarthsh.
2) Repeatedly XOR the plaintext with the mangled key
To prwto bhma twra mporoume na to ksexasoume teleiws, giati de mas dinei
kapoia xrhsimh plhroforia. Apo th stigmh pou den exoume to arxiko
kleidi, opws kai na ginetai mangle, ligo mas endiaferei.
Kai twra to problhma dyskoleyei kai ginetai pio endiaferon. Apo th
stigmh pou exoume *mono to teliko kruptografhma* kai *kanena stoixeio
gia to kleidi*, o idios o algori8mos ligo mas endiaferei, akoma kai an
mporoume na ton antistrepsoume.
Opote 8a prepei na katafygoume se statistikh, pragma poy 8a prepei na to
kaneis esy, mia kai egw den exw prosbash sto kyptogramma. Kapoia
pragmata pou brhkame sthn arxikh diereynhsh, 8a mas boh8hsoun.
H me8odos pou 8a akolou8hseis einai gnwsth. Estw kryptogramma :
KDFGHSKLDFHGKLHWERGUER9GH83HGWEFBNKLSDFB983HRB93HB0EJRBOEHNBO8H358BH49HB0B4NTBORNOBT
8a to xwriseis se omades twn n*7 (gia ka8e pi8ano key length) kai 8a ta
baleis se sthles :
case n=1 :
KDFGHSK
LDFHGKL
HWERGUE
R9GH83H
GWEFBNK
LSDFB98
3HRB93H
B0EJRBO
EHNBO8H
358BH49
HB0B4NT
BORNOBD
case n=2 :
KDFGHSKLDFHGKL
HWERGUER9GH83H
GWEFBNKLSDFB98
3HRB93HB0EJRBO
EHNBO8H358BH49
HB0B4NTBORNOBD
Twra, pairneis ka8e sthlh (p.x. prwth sthlh sto prwto case :
KLHRGL3BE3HB. prwth sthlh sto deytero case : KHG3EH) kai metras th
syxnothta emfanishs ka8e xarakthra sto kryptogramma. Otan oi syxnothtes
bgoun oi idies gia ka8e sthlh, exeis brei to key length.
Ystera apla 8a prepei na kaneis match tis syxnothtes emfanishs ka8e
xarakthra, me tis syxnothtes emfanishs twn xarakthrwn se gnwsto keimeno,
paromoio me to arxiko poy xrhsimopoih8hke gia thn kryptografhsh. Gia
tetoies xrhseis. ta associative arrays ths perl gamane kai dernoyn.
As paroume gia paradeigma klassikou ellhnikou keimenou to keimeno poy
brisketai sth selida :
http://www.e-e-e.gr/
Ftiaxnoume ena programmataki poy metraei absolute count kai relative
frequency gia ka8e gramma tou keimenou :
#!/usr/bin/perl
my %occurence;
while (<>) {
chop;
foreach $j (split('',$_)) {
$count++;
$occurence{$j}++;
}
}
foreach $j (keys %occurence) {
printf("%5d %s %3d %f\n",$occurence{$j},$j,ord($j),$occurence{$j}/$count);
}
$ perl letterhistogram.perl < E1.txt | sort -nr
30475 32 0.111202
15548 Σ 211 0.056734
10591 Ο 207 0.038646
10572 Α 193 0.038577
9709 Ι 201 0.035428
8527 A 65 0.031115
8473 Ε 197 0.030918
8396 O 79 0.030637
7881 - 45 0.028758
7815 I 73 0.028517
7075 Τ 212 0.025816
6848 E 69 0.024988
6713 Ν 205 0.024496
5911 N 78 0.021569
5887 Λ 203 0.021481
5800 Π 208 0.021164
5793 T 84 0.021138
5332 Ω 217 0.019456
ktl ktl ktl. PROSOXH STO CHARACTER SET. Ean to arxiko keimeno exei
graftei se DOS, mallon 8a xrhsimopoiei Codepage 737.
To prwto shmantiko stoixeio pou parathroume edw, einai oti se grapto
keimeno, o pio syxna xrhsimopoioumenos xarakthras einai to space, kai
malista me megalh diafora. Ayto mas epitrepei na xwrisoume sxedon amesws
to kryptografhma se lekseis. Kanonika 8a eprepe na xrhsimopoihsw keimeno
me peripou thn idia proeleysh me to arxiko plaintext, na bgalw eksw tous
agglikous xarakthres kai shmeia stikshs, ktl, alla bariemai.
As doume twra kai th syxnothta emfanishs leksewn sto idio keimeno :
#!/usr/bin/perl
my %occurence;
while (<>) {
chop;
foreach $j (split(' ',$_)) {
$count++;
$occurence{$j}++;
}
}
foreach $j (keys %occurence) {
printf("%5d \"%s\" %f\n",$occurence{$j},$j,$occurence{$j}/$count);
}
Kanoume kai to aparaithto tr apo agglika se ellhnika epeidh o typos den
fainetai na kserei na allazei plhktrologio, kai exoume :
$ cat E1.txt | tr [α-ω] [Α-Ω] | tr AEHYIOTNMK ΑΕΗΥΙΟΤΝΜΚ | perl
whistogram.perl | sort -nr
1332 "ΚΑΙ" 0.037551
979 "ΤΟΥ" 0.027599
920 "ΤΗΣ" 0.025936
771 "ΤΗΝ" 0.021735
562 "ΤΟ" 0.015843
482 "ΝΑ" 0.013588
454 "ΕΙΣ" 0.012799
435 "Η" 0.012263
364 "ΜΕ" 0.010262
353 "ΤΩΝ" 0.009952
334 "-" 0.009416
299 "Ο" 0.008429
270 "ΑΠΟ" 0.007612
255 "ΘΑ" 0.007189
250 "ΤΟΝ" 0.007048
241 "ΕΙΝΑΙ" 0.006794
238 "ΟΙ" 0.006710
236 "ΤΑ" 0.006653
199 "ΔΕΝ" 0.005610
197 "ΔΙΑ" 0.005554
168 "ΤΟΥΣ" 0.004736
152 ""Ε"" 0.004285
142 "ΙΣΤΟΥ" 0.004003
...
62 "ΣΕ" 0.001748
59 "ΜΑΣΩΝΙΚΗ" 0.001663
58 "ΕΛΛΑΔΟΣ" 0.001635
57 "ΑΛΛΑ" 0.001607
54 "ΩΣ" 0.001522
54 "ΚΙΝΕZΟΕBPΑΙΟΚΙΝΟΥΜΕΝΗΣ" 0.001522
52 "ΜΑΣΩΝΩΝ" 0.001466
...
39 "ΕBPΑΪΚΗΣ" 0.001099
38 "ΤΕΛΕΤΟΥPΓΙΚΩΣ" 0.001071
38 "ΣΤΟ" 0.001071
38 "ΑΝΩΘΙ" 0.001071
37 "ΔΙΟΤΙ" 0.001043
36 "ΛΕΥΚΗΣ" 0.001015
36 "ΕΠΙ" 0.001015
35 "ΚΙΝΕZΟΚΙΝΟΥΜΕΝΗΣ" 0.000987
35 "ΔΡΑΚΟΝΙΑΝΗ" 0.000987
34 "ΣΟΔΟΜΙΣΜΕΝΩΝ" 0.000959
34 "ΜΟΥ" 0.000959
34 "ΜΙΣΕΛΛΗΝΙΚΗ" 0.000959
34 "ΜΑΣΩΝΟΙ" 0.000959
34 "ΜΑΣΩΝΙΚΩΝ" 0.000959
34 "ΕΜΜΑΝΟΥΗΛ" 0.000959
18 "ΡΕ" 0.000507
18 "ΠPΑΚΤΟPΕΣ" 0.000507
18 "ΜΟΝΟΝ" 0.000507
18 "ΚΙΝΕΖΟΕΒΡΑΙΟΔΟΥΛΟΣ" 0.000507
ktl ktl ktl.
Pragma pou mas odhgei
(peran apo thn aporia ths emfanishs ths lekshs "sodomismenwn" mono 34
fores se keimeno 5000 leksewn, kai thn aporia tou giati h syxnothta twn
"sodomismenwn" diaferei elafrws apo thn syxnothta twn "teletourgikws"
pou synh8ws thn akolou8ei sto sygkekrimeno keimeno)
se symperasmata gia tis pio syxnes lekseis triwn grammatwn sthn Ellhnikh
- profanws ta ar8ra - opws kai sto asfales symperasma oti kata pasa
pi8anothta mia leksh triwn grammatwn arxizei apo T, ktl ktl ktl. Apo
ekei mporeis na arxiseis thn antistoixhsh leksewn kai grammatwn, wste na
apokryptografhseis arketo kommati tou keimenou wste siga siga na
mporeseis na symplhrwseis kai to ypoloipo.
More information about the Linux-greek-users
mailing list