0
votes
$\begingroup$

First of all, this is not a beginner's question since I already know a good deal about encryption and brute-force attacks. This is also no question on how to code programs for brute-force attacks since I already know that too and as you can see below I have already coded such a tool. This is more of a set of questions for other experts out there who may help me with their opinions or their suggestions...

To cut a long story short, I have developed an user-friendly brute-force attack tool called bfxor (for Windows and Linux) to crack ciphertexts and/or encrypted files which have been xored with at least 1 byte and with a maximum of 8 bytes (64 bits), plus the user can search each brute-forced result for a known or "suspected" string to shorten the time of a ciphertext attack. I made my tool look in the style of cgminer and other Bitcoin/Altcoin miners, although it has nothing to do with cryptocurrencies and is coded from scratch by my myself.

In bfxor a string-search is part of a so-called "deep scan" for which I have coded a special function which does two things at current stage:

  • checks if the current xored result is in the common ascii range 32..126 and returns TRUE if so.
  • when the xored result is in the range then scans through the data block for the searchstring.

So here comes my first expert question:

1. Should I also perform a string search if the xored result is outside the common ascii range?

enter image description here

Now this may all be laughable in 2014 though where most cryptographers and even I use 2048 to 8192-bit (256 to 1024 Bytes) Keys for XOR encryption. So bfxor on a 3-4 GHz PC wouldn't have a chance to crack keys over 64 bits in just a single day running straight. It would take days or even weeks and months to run through the whole process, although I have coded my brute-force scan-functions in a way that they are superfast and don't waste too many resources or frames in the repeated attack-run. For example, it loads only the first 240 bytes of an XOR-encrypted file into a block memory instead of scanning through the whole encrypted file. It does that, because it assumes that if the first 240 bytes of an xor-encrypted file, where most of the header information is stored in, are correct than the rest must be correct with the found key too.

So here comes my second expert question:

2. Let's assume that someone encrypted a large file of several megabytes or even gigabytes with an XOR key of unknown length, and bfxor has found 64 bits of that key which correctly decrypts the first 240 bytes of the file! How safe is it to assume that this is the correct key for the rest of the file? Or should there be additional scans be performed to determine whether the found key decrypts all the data of the file, regardless how big it is, and not just the first 240 bytes of the analyzed block?

Alright, that's it. Thanks for reading and I hope these questions are understandable enough...

P.S. I added logging to bfxor for saving the outputs. And here's a logfile of my testscan which shows also all the brute-forced results (rejected ones) which bfxor ran through in this example:

[BFLOG]
; Config Settings
FileName=testme1.dat
FileSize=24
FileType=Unknown
KeyLength=1
ASCIIRange=#1..255|$01..FF
TextString=SECRET

; Session Log
[2014-11-16 21:18:02] Brute-force Session started.
[2014-11-16 21:18:02] Loaded 24 Bytes of File into Memory Block.
[2014-11-16 21:18:02] Ready to run attack...
[2014-11-16 21:18:05] Showing rejected results too. (Slower Scan)
[2014-11-16 21:18:06] Running NOW!
[2014-11-16 21:18:06] XOR-ing Ciphertext w/Key Length 1 ...
[2014-11-16 21:18:06] Rejected {Ç} Text <+76,_6,_>_,:<-:+_2:,,>8:>
[2014-11-16 21:18:06] Key$ 80
[2014-11-16 21:18:06] Rejected {ü} Text <*67-^7-^?^-;=,;*^3;--?9;>
[2014-11-16 21:18:06] Key$ 81
[2014-11-16 21:18:06] Rejected {é} Text <)54.]4.]<].8>/8)]08..<:8>
[2014-11-16 21:18:06] Key$ 82
[2014-11-16 21:18:06] Rejected {â} Text <(45/\5/\=\/9?.9(\19//=;9>
[2014-11-16 21:18:06] Key$ 83
[2014-11-16 21:18:06] Rejected {ä} Text </32([2([:[(>8)>/[6>((:<>>
[2014-11-16 21:18:06] Key$ 84
[2014-11-16 21:18:06] Rejected {à} Text <.23)Z3)Z;Z)?9(?.Z7?));=?>
[2014-11-16 21:18:06] Key$ 85
[2014-11-16 21:18:06] Rejected {å} Text <-10*Y0*Y8Y*<:+<-Y4<**8><>
[2014-11-16 21:18:06] Key$ 86
[2014-11-16 21:18:06] Rejected {ç} Text <,01+X1+X9X+=;*=,X5=++9?=>
[2014-11-16 21:18:06] Key$ 87
[2014-11-16 21:18:06] Rejected {ê} Text <#?>$W>$W6W$24%2#W:2$$602>
[2014-11-16 21:18:06] Key$ 88
[2014-11-16 21:18:06] Rejected {ë} Text <">?%V?%V7V%35$3"V;3%%713>
[2014-11-16 21:18:06] Key$ 89
[2014-11-16 21:18:06] Rejected {è} Text <!=<&U<&U4U&06'0!U80&&420>
[2014-11-16 21:18:06] Key$ 8A
[2014-11-16 21:18:06] Rejected {ï} Text < <='T='T5T'17&1 T91''531>
[2014-11-16 21:18:06] Key$ 8B
[2014-11-16 21:18:06] Rejected {î} Text <';: S: S2S 60!6'S>6  246>
[2014-11-16 21:18:06] Key$ 8C
[2014-11-16 21:18:06] Rejected {ì} Text <&:;!R;!R3R!71 7&R?7!!357>
[2014-11-16 21:18:06] Key$ 8D
[2014-11-16 21:18:06] Rejected {Ä} Text <%98"Q8"Q0Q"42#4%Q<4""064>
[2014-11-16 21:18:06] Key$ 8E
[2014-11-16 21:18:06] Rejected {Å} Text <$89#P9#P1P#53"5$P=5##175>
[2014-11-16 21:18:06] Key$ 8F
[2014-11-16 21:18:06] Rejected {É} Text <;'&<O&<O.O<*,=*;O"*<<.(*>
[2014-11-16 21:18:06] Key$ 90
[2014-11-16 21:18:06] Rejected {æ} Text <:&'=N'=N/N=+-<+:N#+==/)+>
[2014-11-16 21:18:06] Key$ 91
[2014-11-16 21:18:06] Rejected {Æ} Text <9%$>M$>M,M>(.?(9M (>>,*(>
[2014-11-16 21:18:06] Key$ 92
[2014-11-16 21:18:06] Rejected {ô} Text <8$%?L%?L-L?)/>)8L!)??-+)>
[2014-11-16 21:18:06] Key$ 93
[2014-11-16 21:18:06] Rejected {ö} Text <?#"8K"8K*K8.(9.?K&.88*,.>
[2014-11-16 21:18:06] Key$ 94
[2014-11-16 21:18:06] Rejected {ò} Text <>"#9J#9J+J9/)8/>J'/99+-/>
[2014-11-16 21:18:06] Key$ 95
[2014-11-16 21:18:06] Rejected {û} Text <=! :I :I(I:,*;,=I$,::(.,>
[2014-11-16 21:18:06] Key$ 96
[2014-11-16 21:18:06] Rejected {ù} Text << !;H!;H)H;-+:-<H%-;;)/->
[2014-11-16 21:18:06] Key$ 97
[2014-11-16 21:18:06] Rejected {ÿ} Text <3/.4G.4G&G4"$5"3G*"44& ">
[2014-11-16 21:18:06] Key$ 98
[2014-11-16 21:18:06] Rejected {Ö} Text <2./5F/5F'F5#%4#2F+#55'!#>
[2014-11-16 21:18:06] Key$ 99
[2014-11-16 21:18:06] Rejected {Ü} Text <1-,6E,6E$E6 &7 1E( 66$" >
[2014-11-16 21:18:06] Key$ 9A
[2014-11-16 21:18:06] Rejected {ø} Text <0,-7D-7D%D7!'6!0D)!77%#!>
[2014-11-16 21:18:06] Key$ 9B
[2014-11-16 21:18:06] Rejected {£} Text <7+*0C*0C"C0& 1&7C.&00"$&>
[2014-11-16 21:18:06] Key$ 9C
[2014-11-16 21:18:06] Rejected {Ø} Text <6*+1B+1B#B1'!0'6B/'11#%'>
[2014-11-16 21:18:06] Key$ 9D
[2014-11-16 21:18:06] Rejected {×} Text <5)(2A(2A A2$"3$5A,$22 &$>
[2014-11-16 21:18:06] Key$ 9E
[2014-11-16 21:18:06] Rejected {ƒ} Text <4()3@)3@!@3%#2%4@-%33!'%>
[2014-11-16 21:18:06] Key$ 9F
[2014-11-16 21:18:06] Rejected {ı} Text <~bcy.cy.k.yoixo~.goyykmo>
[2014-11-16 21:18:06] Key$ D5
[2014-11-16 21:18:06] Rejected {Í} Text <}a`z.`z.h.zlj{l}.dlzzhnl>
[2014-11-16 21:18:06] Key$ D6
[2014-11-16 21:18:06] Rejected {Ó} Text <KWVL?VL?^?LZ\MZK?RZLL^XZ>
[2014-11-16 21:18:06] Key$ E0
[2014-11-16 21:18:06] Rejected {ß} Text <JVWM>WM>_>M[]L[J>S[MM_Y[>
[2014-11-16 21:18:06] Key$ E1
[2014-11-16 21:18:06] Rejected {Ô} Text <IUTN=TN=\=NX^OXI=PXNN\ZX>
[2014-11-16 21:18:06] Key$ E2
[2014-11-16 21:18:06] Rejected {Ò} Text <HTUO<UO<]<OY_NYH<QYOO][Y>
[2014-11-16 21:18:06] Key$ E3
[2014-11-16 21:18:06] Rejected {õ} Text <OSRH;RH;Z;H^XI^O;V^HHZ\^>
[2014-11-16 21:18:06] Key$ E4
[2014-11-16 21:18:06] Rejected {Õ} Text <NRSI:SI:[:I_YH_N:W_II[]_>
[2014-11-16 21:18:06] Key$ E5
[2014-11-16 21:18:06] Rejected {µ} Text <MQPJ9PJ9X9J\ZK\M9T\JJX^\>
[2014-11-16 21:18:06] Key$ E6
[2014-11-16 21:18:06] Rejected {þ} Text <LPQK8QK8Y8K][J]L8U]KKY_]>
[2014-11-16 21:18:06] Key$ E7
[2014-11-16 21:18:06] Rejected {Þ} Text <C_^D7^D7V7DRTERC7ZRDDVPR>
[2014-11-16 21:18:06] Key$ E8
[2014-11-16 21:18:06] Rejected {Ú} Text <B^_E6_E6W6ESUDSB6[SEEWQS>
[2014-11-16 21:18:06] Key$ E9
[2014-11-16 21:18:06] Rejected {Û} Text <A]\F5\F5T5FPVGPA5XPFFTRP>
[2014-11-16 21:18:06] Key$ EA
[2014-11-16 21:18:06] Rejected {Ù} Text <@\]G4]G4U4GQWFQ@4YQGGUSQ>
[2014-11-16 21:18:06] Key$ EB
[2014-11-16 21:18:06] Rejected {ý} Text <G[Z@3Z@3R3@VPAVG3^V@@RTV>
[2014-11-16 21:18:06] Key$ EC
[2014-11-16 21:18:06] Rejected {Ý} Text <FZ[A2[A2S2AWQ@WF2_WAASUW>
[2014-11-16 21:18:06] Key$ ED
[2014-11-16 21:18:06] Rejected {¯} Text <EYXB1XB1P1BTRCTE1\TBBPVT>
[2014-11-16 21:18:06] Key$ EE
[2014-11-16 21:18:06] Rejected {´} Text <DXYC0YC0Q0CUSBUD0]UCCQWU>
[2014-11-16 21:18:06] Key$ EF
[2014-11-16 21:18:06] Rejected {­} Text <[GF\/F\/N/\JL]J[/BJ\\NHJ>
[2014-11-16 21:18:06] Key$ F0
[2014-11-16 21:18:06] Rejected {±} Text <ZFG].G].O.]KM\KZ.CK]]OIK>
[2014-11-16 21:18:06] Key$ F1
[2014-11-16 21:18:06] Rejected {‗} Text <YED^-D^-L-^HN_HY-@H^^LJH>
[2014-11-16 21:18:06] Key$ F2
[2014-11-16 21:18:06] Rejected {¾} Text <XDE_,E_,M,_IO^IX,AI__MKI>
[2014-11-16 21:18:06] Key$ F3
[2014-11-16 21:18:06] Rejected {¶} Text <_CBX+BX+J+XNHYN_+FNXXJLN>
[2014-11-16 21:18:06] Key$ F4
[2014-11-16 21:18:06] Rejected {§} Text <^BCY*CY*K*YOIXO^*GOYYKMO>
[2014-11-16 21:18:06] Key$ F5
[2014-11-16 21:18:06] Rejected {÷} Text <]A@Z)@Z)H)ZLJ[L])DLZZHNL>
[2014-11-16 21:18:06] Key$ F6
[2014-11-16 21:18:06] Rejected {¸} Text <\@A[(A[(I([MKZM\(EM[[IOM>
[2014-11-16 21:18:06] Key$ F7
[2014-11-16 21:18:06] Rejected {°} Text <SONT'NT'F'TBDUBS'JBTTF@B>
[2014-11-16 21:18:06] Key$ F8
[2014-11-16 21:18:06] Rejected {¨} Text <RNOU&OU&G&UCETCR&KCUUGAC>
[2014-11-16 21:18:06] Key$ F9
[2014-11-16 21:18:06] Rejected {·} Text <QMLV%LV%D%V@FW@Q%H@VVDB@>
[2014-11-16 21:18:06] Key$ FA
[2014-11-16 21:18:06] Rejected {¹} Text <PLMW$MW$E$WAGVAP$IAWWECA>
[2014-11-16 21:18:06] Key$ FB
[2014-11-16 21:18:06] Rejected {³} Text <WKJP#JP#B#PF@QFW#NFPPBDF>
[2014-11-16 21:18:06] Key$ FC
[2014-11-16 21:18:06] Rejected {²} Text <VJKQ"KQ"C"QGAPGV"OGQQCEG>
[2014-11-16 21:18:06] Key$ FD
[2014-11-16 21:18:06] Rejected {■} Text <UIHR!HR!@!RDBSDU!LDRR@FD>
[2014-11-16 21:18:06] Key$ FE
[2014-11-16 21:18:06] Accepted { } Text <THIS IS A SECRET MESSAGE>
[2014-11-16 21:18:06] Key$ FF
[2014-11-16 21:18:06] Textstring <SECRET> matched !!
[2014-11-16 21:18:06] Number of Accepted Keys found = 1
[2014-11-16 21:18:06] Brute-force Session ended.

[BFEND]
$\endgroup$
13
  • 1
    $\begingroup$ Why brute force? Doesn't it make more sense to spend time on frequency analysis? If you know the length of the key and have some idea about the plaintext, you can look at the xor difference of ciphertext pairs and find the key a lot faster. $\endgroup$
    – user13741
    Nov 17, 2014 at 17:47
  • $\begingroup$ A non-answer but there are wildly simpler methods to decode XOR encoded data. If your key is N bytes long, xor the first N bytes with the next N bytes and you will end up with the XOR of two bits of plaintext, very not random, repeat along the message. Additionally, if your message is fairly long, simple frequency checking like can be done for simple substitution ciphers will work. for an 8 byte key you can take every 8th byte and consider that a stream with a simple cipher barely more secure than rot13. $\endgroup$
    – John Meacham
    Nov 17, 2014 at 18:18
  • 2
    $\begingroup$ "Now this may all be laughable in 2014 though where most cryptographers and even I use 2048 to 8192-bit (256 to 1024 Bytes) Keys for XOR encryption" - No cryptographer in 2014 is using anything like a vigenere cipher. $\endgroup$
    – bmm6o
    Nov 18, 2014 at 0:33
  • $\begingroup$ Are you assuming a someone is using the same one-time-pad key multiple times? $\endgroup$
    – Guut Boy
    Nov 18, 2014 at 13:39
  • $\begingroup$ @GuutBoy: Yes, I assume that someone is repeating a key of a certain length to xoring a complete message or file of any length. $\endgroup$
    – xorcoder
    Nov 19, 2014 at 17:48

1 Answer 1

Reset to default
2
votes
$\begingroup$

This question as stated actually has a fairly interesting and unintuitive answer.

Assuming an 8 byte 64 bit xor key and your test for printable ascii characters then after a megabyte of correct data your chances of having the right key are... about one in four billion. This is completely independent of how much data you have or verify, 1/2^32 is the maximum probability you can achieve of having the right key.

The reason for this is that you must consider each bit independently of the rest, you are effectively running 8 xor brute force searches in parallel on each bit position. Since in your range the high order bit is always zero, so the brute force will quickly come to an answer for that position. bit zero can be distingushed because 0x7e and 0x7f differ by that bit and one is in and one is out of the acceptable range. However, for all 4 bits in the positions of 1-4, you can never find the correct xor key by brute force. The reason is that if you take a printable character and flip any of those four bits, you will still get a printable character. Since your key is 8 bytes long and each byte has 4 unknowable bits the only way to get those 32 bits right is by sheer luck. Hence, a 1/2^32 chance of having the correct key.

Now, what are the chances of having the right key if it passes the test AND you find your search string? actually not that much better at all depending on your search string. Because there are many xor patterns that will force almost any series of bytes to match the search string. You can see this just by xoring a section of your crypto with the search string and taking the result as your key, yay, you found your search string! Now, it is complicated a little in that repeated characters must map to repeated characters when the key is cyclicly applied but that would only be an issue with long search strings with repeated characters. Strangely enough, the longer the document you verify through the worse your chances of being right are because there are more opportunities for false matches! longer search strings will help

$\endgroup$
3
  • $\begingroup$ Maybe I should have mentioned it, but in my brute-force tool I don't include 0x7F (dec 127) in the common ASCII range, because that's the Delete character actually and hardly used in common text anyway. But I do check for 0x0A and 0x0D which represent LF (Line Feed) and CR (Carriage Return) which are included in almost every textfile. If I want to check for 0x7F character I would switch to the extended ASCII range table $20..FF (#32..255) in my bfxor program. For more info on special function characters see the ASCII table: asciitable.com $\endgroup$
    – xorcoder
    Nov 19, 2014 at 18:16
  • $\begingroup$ Yeah, not allowing delete is good because it lets you distinguish bit position zero, 0b01111111 is out of the acceptable set and 0b01111110 is in it. In order for a pure accept/reject test to work you need to make sure that for each bit position there is some case where flipping it changes whether it is in the accept or reject state. If flipping a bit always preserves the state, then your brute force method won't be able to figure it out. $\endgroup$
    – John Meacham
    Nov 19, 2014 at 20:46
  • $\begingroup$ That said, what you can do to alleviate this problem is take a histogram of your candidate plaintext, text has a very characteristic frequency histogram, even though flippng those middle bits will still result in ascii, it will end up with a pretty random histogram if wrong. So first check for ascii, then take the histogram and measure how far away it is from normal text and you will have a much better chance of being sure you have the right key. more data does help here. You can even use the histogram data to guide your brute force search to speed it up. $\endgroup$
    – John Meacham
    Nov 19, 2014 at 20:50

Not the answer you're looking for? Browse other questions tagged or ask your own question.