This message is mostly for mike:
I post it in the public forum because it may be of interest to others in here.

In one of the papers you posted in your web site you talk about strategies to decipher protected zip files with very few known plain-text bytes. From the text I am led to believe that you implemeted the code for the algo.

Is that code available or did you write a more detailed description of the code?

I tried to implement it myself based and your paper, but, not surprisingly, I have not been very successful.

Thanks

Well, technically the code belongs to AccessData, but the algorithm has been implemented by at least two other competitors, ElcomSoft and LostPassword. If you just want to break a file, I suggest using one of the three tools; if you're more interested in the algorithm, I'd be happy to answer any questions you have about the paper and/or coding issues. I don't think I'm allowed to just hand over my code, though.

By the way, the stuff I've got is the crufty development code, the "first draft" if you will. It works, but it's not at all pretty.

I am planning on writing a much less "academic" paper for tsehp's site that's targeted more toward the cracker audience, but I'm not making any promises about when I'll get it out.

--mike

You know, now that I think about it, doing an interactive discussion here might be better in some ways, because people can ask about points where I'm not clear. Perhaps then it would be easier for me (or someone else that implements it from this discussion) to write the tut.

So here goes:

First off, you NEED to read appnote.txt. Find an HTML version here:

h**p://www.pkware.com/support/appnote.html

Get really familiar with the Local File Header and Decryption sections. Decrypt a few small files by hand for which you know the password.

In the paper, I make some assumptions about the way the archive was created. The specification allows each archived file to have its own password; it also allows archived files to be deleted from the archive leaving the rest in place. But I assume that all the files were added at once to the archive using the same password and that none have been deleted. Also, I assume that there are at least five files. I'll show why all that's important a little later.

The important things to notice in the LFH are the encryption flag and the CRC. The encryption flag lets you know whether this particular archived file is encrypted, while the CRC is used in the password check. We won't use it in the attack, but it's a sanity check to make sure we did it all right after the attack is over.

When a file is encrypted in WinZip, the first 10 bytes of "file data" are generated by rand(). rand is a truncated linear congruential generator. A TLCG has a static seed value, i.e.

static int32 seed;

At each call to rand, seed is updated to be

seed = (M*seed+B) & 0x7FFFFFFF;

Then the top 16 bits are returned.

return (seed >> 16);

WinZip throws away the bottom seven bits:

rand() >> 7 == seed>>23

The first part of the attack tries to determine what the seed value is. It turns out that the first byte of each encryption header is direct ouput from rand(). I'll explain why later.

WinZip only initializes the seed once per session, so we assume that after generating ten bytes for the first encrypted file, it goes on to generate ten bytes without updating the seed for the second encrypted file, and so on. We take the first byte of five encryption headers and assume they all come from the same seed.

So we start trying every possible seed and check every ten outputs, starting with the first, to see if it gives the right bytes.

Let me know if you get this part working, and we'll go on from there.

Once you have the seed, then you can generate all the "random" bytes that get encrypted.

Now we need to look more closely at the encryption.

I wrote in the last part that the first ten bytes of "file data" plaintext are generated by rand; this isn't exactly true. They're generated by rand and then encrypted using the password. Then the low word of the CRC is added to the end as password check bytes. This makes 12 bytes total. You'll notice that the difference in size between an encrypted file and a plaintext file is always tewlve bytes.

Zip encryption works by beginning in an initial state, generating a byte, updating the state with the plaintext character, and XORing the plaintext with the ouptut byte to produce a cyphertext byte.

Some pseudocode:

The way this cipher uses passwords is by encrypting them first and throwing away the corresponding ciphertext; that way the password mixes up the state in a deterministic way.

So the process goes like this:


If you look at steps 8, 9, and 10 you see why the encrypted file is 12 bytes bigger.

But look at steps 1, 2, 3 and 6, 7, 8. The output of rand is encrypted twice using the same key!

Since A XOR B XOR B == A, the first byte of output gets decrypted. The rest of the bytes don't, since the cipher gets updated with the stuff it's encrypting. The second time around, it got updated with the once-encrypted output.

Next time: more about the encryption and the beginnings of the second part of the attack.

May I ask a question as the only real crypto stuff I have done is learning to decrypt older cyphers such as playfair etc (by han.

I tend to spend my time in the PE file structure insetad.

Could the fact that files found in zip files usually have a predictable header of some sort be used to speed up the brute forcing of the password ?

Kilby...

Only if they're stored. The compression mangles them otherwise. Huffman coding translates common bytes to short bit strings and uncommon ones to longer bit strings. In PKZip, it applies to the first 32K of the file. (I'm oversimplifying here, but the point still holds.) So unless you know the first 32K, predicting the starting bytes is very hard.

If they're stored, of course, you can decrypt the 12 "random" bytes, check the crc, and then check the header bytes you know. If you have enough of them (11 or 12) you can use the kocher-biham attack.

Ah thanks for that Kilby and Mike. You just answered a question that has been on my mind for quite sometime. Considering almost all executables now have the same stub for the first hundred bytes then the PE\0\0. Why not use that informatino to your advantage when breaking zip =]. Guess that explains why you cant.

Snatch

Hmmm, this sounds like a good time for me to go back to homophones (nope it dosn't involve sex), and playfair cypers and their old fashoned friends.

Thanks for the explination (even if it would have been obvious if I had actually thought about it)

Kilby...

If it's an executable that's archived, chances are you can find another copy of that exe on the web. Then you compress it using the same zipper and compression setting to get the compressed plaintext for use in the biham-kocher attack.

If people aren't implementing this or having questions or anything, then I'm not going to spend time on it right now. Post to this thread when you'd like me to pick it up again.

If you'd like a walk thru of the biham-kocher attack, I can do that, too.

Hi Mike. The thread IS interesting and, at least I am following it.
For my particular cipher problem, though I need to implement the kocher-biham attack in a modified form.

Let me explain my specific problem so you can tell me if it is feasible:

I have a series of ZIP files. Each one contains a RAR file in a huge series of 7 RAR from .RAR to .R05.

Only the first ZIP is password protected, but contains the first RAR, which is necessary to unRAR the rest of the files.

If I look at the plaintext of the other RAR files, which are ZIPed but not protected, the first 50 bytes of the sequence are not perfectly conserved.


However there is a stretch of ~20 bytes that is present in the same position in each of the other RAR files, and I can more of less safely assume is present in the plain text of the ZIP protected file. Those bytes contain info about the names of the files in the RAR directory.

The comercial applications available on the web do not crack the password.
I think my best chance is to manually implement a kocher-biham attack using the 20 known plain text bytes and the correspondent 20 cipher bytes, until I learn the internal state of the keys up to that point. then work backwards and forward to decypher the rest of the file, which should produce a viable RAR file.

Several people in this board may guess which files I am talking about.
An alternative approach would be to ask CrackZ for the password to the files, but that would spoil half the fun.

Crypto is not my strong point, that is why I asked you for help.

Hi naides,

What do u mean by the commercial protection do not crack password? I thought Advanced Zip password Recovery or something liek that do this kind of thing? crack winzip password :>??

Cheers,

P.S : sorry for the off topic question, but i am just curious over the fact you stated...

Binh81

I tried several commercial Zip password crackers and they just did not work.
Notice that those apps require at least 12 bytes of known plain text, but I I think they pretend the partial known plain text was located at the begining of the cipher text. I cannot guess the first 50 bytes of the plain text, only the next 20 bytes.

naides,
Try this. Use the plaintext attack in AZPR. The first file is the encrypted one and the plaintext file is the next one. Use data offset 6, size of plaintext 18. This should generate the 3 keys in a few hours.
jsteed

Hello naides !

I've two ideas which might help you with your problem.

Take a look at the TECHNOTE.TXT included with RAR. It will describe the RAR structure very well. There are many static bytes in the header, you can calculate even 12 bytes if you need them.
The program AZPR has an option where you can enter up to four plain text bytes if the file was archived with no compression. And since I don't really think a ZIP program can compress RAR data, the RAR is probably only stored in the ZIP and the first four bytes are "Rar!"

I hope this helps you.

When you say "plaintext", do you mean compressed plaintext or uncompressed plaintext? Or are they stored? (DakienDX--often Zip can compress even very random-looking files by a few bytes. I hope in this case it couldn't.)

If it's compressed and you know 12 bytes of compressed data or if it's stored and you know 12 bytes of stored data then you can break it, no matter what the offset. You just need to tell AZPR the offset and tell it what bytes to expect.

Tried that. The RAR static bytes are not contiguous. Interspaced with them are dwords containing CRC checks of the stored stream, which are unique to each RAR file structure.





Tried that, did not work

Hello naides !

If you've a multi-volume RAR file, the first 20 bytes in each RAR are (at least should be) the same.
Since you said that only one file is password protected and the others are not, take the first twenty bytes from them as plaintext.

What files are you talking about? You said you could ask CrackZ for the password. Perhaps I've the files too and can help you with them, even if I might know the password.

I did put the first 20 bytes of the other RAR files as plain text but the AZPR did not find the keys based on it. That is when I took a closer look at the plain text of the other RAR files after being compressed by ZIP (by the way, ZIP does compress them a little bit) and found some conserved bytes and some mutant bytes. ( I am referring to computer files as DNA sequences, because the resemblance is more than superficial).

I have AZPR version 3.52, which I think is the last version available. Mike suggests

" You just need to tell AZPR the offset and tell it what bytes to expect"

The problem is I have not found an option in the program which allows me to instruct AZPR to do just that.

The files in question are the SentinelLM 7.2 SDK published by Crack Z a few months back. He had reasons to restrict its access and password protected the first RAR.

It is not that I will die if I don't get those files, I am more for the challenge of it

I've never actually used AZPR. I've always used Conrad's implementation:

http://www.unix-ag.uni-kl.de/~conrad/krypto/pkcrack.html

Full source to make it do whatever you want. The original b-k paper is included.

Hello naides !

I've the files (and the password ), but I'll give it a try.
I'm using the plaintext attack with 20 bytes of known data (first 20 bytes of .R00)
It says it will take 6 hours with background priority. So I'll see what has come out in a few hours. (or a few more, I'll need some sleep )

"You just need to tell AZPR the offset and tell it what bytes to expect" - You can select this option if you coose a binary plain-text file and AZPR asks you if you just want to use a part of the file as plain-text. Then you can enter at which offset to start and how much data to use.

Hello naides !

4h 38m 16s - No Password Found

I'm going to look what plain-text is really encrypted, maybe the data was somehow compressed and I used the wrong plaintext for the attack.

Yup, I have had the same problem over and over again.
I wrote to CrackZ some time ago and asked if he had done any thing special to the files previewing this seemingly simple attack and he told me he did not.

The plain text in all not encrypted RAR files from R00 to R05 is conserved, either you look at the unpacked RAR files or the ZIP files, so I found it unlikely that there was anything unique to the encrypted RAR file.

However, I think I may have a clue what is going on: AZPR indeed finds the 3 keys, but when it makes some comparisons with CRCs or other goodies containded in the R00 plain texts, things do not add up and it just simply toss them and report that no keys were found. That is why, I think, if I had a biham-kocher implementation I could have more control over the attack. BUT I AM USUALLY WRONG.

Ok... here is my contribution to this thread. Ive added 5 files to 2 zips. One with a 4 letter pass, and the other with no pass. Ive added 3 .txt files, one .exe and one .htm

wnopass.zip 34.447 bytes
wpass.zip 34.507 bytes

Now using WinHex I had a look at LFH. It is at least 30 bytes.

wnopass.zip
504B0304 1400 0200 0800 E78C 7427 56191BD2 FC020000 000A0000 0700 0000

wpass.zip
504B0304 1400 0300 0800 E78C 7427 56191BD2 08030000 000A0000 0700 0000

There are 2 differences between the files. The general purpose bit flag (GPBF) and the compressed size. The compressed size is explained in the decryption section of APPNOTE.TXT

So, 5*12=60 and 507-447=60

Then I had a look at GPBF. Converting the values to binaries we have 00000010 (2), 00000011 (3). Bit 0 is the one on the right.

cool =]

Another important info is the CRC, D21B1956

DECRYPT...

Each encrypted file has an extra 12 bytes stored at the start of the data area

I guessed the data area was just after the name of the file. As the bytes changed from wpass to wnopass... So I copied the 12 first bytes.

win.exe
FB2C0BC08E09ACBBB25BA643
t138.txt
82B60700981FB93565B8E3D4
t141.txt
BEC82314CC928320A1665624
winzip crack.txt
BE8B41ED52EA1987B4CF2A04
PKZIP Application Note.htm
80A085ACC314EE770660C61D



And how we do that? We must code a bruteforce using this code?



btw Ive added both files so everyone can check it out =]

Hi AirWolf! Thx for posting.

WinZip throws away the low seven bits of the 16-bit output of rand. The first ten bytes in each 12-byte encryption header are the high-order bits of rand output encrypted twice under the same password.



Yes.

There's a few tricks you can use to make it go faster:

1. When the first password-protected file is added to the archive, it calls srand(time(NULL) ^ getpid()). Knowing what year it was created restricts your search a lot.

2. Each byte of rand's output reveals some bits of the internal state, so you can use (say) the first output byte to restrict your search, too.

3. Since the generator is linear, we can find new constants to use that automatically skip ten bytes, so there's only one function call, multiply, and add instead of ten.

Brute forcing 31 bits, though, will only take a few minutes.

Hello naides !

With 60kb of plain-text the attack takes only 1 minute.
AZPR can't find the password, but it shows the keys and decrypts the ZIP file.

Here are the first 256 bytes of plain-text. Using them it should take about 15 minutes to decrypt the file.

8Ch, BCh, 65h, 50h, 9Dh, 3Fh, FCh, F6h, 79h, 0Eh, 72h, B0h, 83h, 94h, 16h, 39h, B8h, 16h, 29h, 72h, 70h, A7h, 68h, D1h, E2h, 56h, DCh, DDh, DDh, 39h, B8h, BBh, 14h, 8Ah, BBh, 6Bh, 71h, 29h, EEh, 4Eh, 71h, 77h, 28h, EEh, 2Eh, FBh, FBh, EFh, CEh, BEh, D8h, 7Dh, F6h, 99h, D9h, BCh, C8h, 24h, 33h, D7h, 9Dh, 4Ch, 26h, C9h, F7h, FEh, 5Ch, C9h, 4Ch, 94h, 0Ch, 1Ch, C9h, 09h, 90h, 00h, 97h, CFh, 4Eh, 40h, 00h, 3Ah, E0h, FFh, 4Ah, F4h, 5Ah, CEh, 9Bh, 30h, 5Ah, C0h, FFh, 9Dh, E0h, FEh, 27h, CBh, 77h, 8Ch, A5h, FFh, C4h, 86h, 0Ch, C0h, FAh, AFh, ECh, 64h, E2h, ECh, 62h, 6Fh, 6Ch, E1h, 28h, 29h, F8h, 9Fh, 8Eh, F1h, FFh, 4Bh, 87h, FEh, FFh, D0h, 69h, 43h, B9h, A1h, ECh, 5Eh, F0h, FFh, 7Fh, C5h, ECh, 50h, A3h, 20h, BEh, FFh, 55h, 5Ch, F0h, BFh, 11h, B3h, 53h, 72h, FEh, FFh, 15h, 43h, A1h, 06h, C7h, 7Eh, FFh, ABh, B8h, F0h, 7Fh, 23h, E6h, C1h, 80h, 38h, C3h, 60h, 5Ch, 00h, F7h, 70h, 38h, C0h, AAh, 25h, 02h, 00h, CEh, E1h, 0Bh, 85h, BEh, 10h, CFh, 25h, EDh, 27h, 36h, 3Ch, 00h, 10h, F0h, FFh, 1Ah, A0h, F6h, FFh, 59h, 63h, 32h, B4h, B1h, C7h, 82h, A8h, AAh, 7Eh, 00h, 8Fh, ABh, A0h, A7h, 3Ch, 7Fh, D8h, D8h, 30h, EAh, CCh, 7Ah, 6Bh, D9h, 94h, C6h, FEh, 47h, 1Bh, A2h, D1h, A8h, BAh, F6h, 77h, 89h, 4Dh, E9h, E8h, 67h, C7h, B9h, F7h, B8h, CAh, DFh, F5h, 7Bh, ADh, FEh, 48h, 77h, E0h

As you'll notice, it's not the same as in the other RAR files.

AirWolf--I'm posting this from someone else's computer; I haven't looked at your zip file to make sure you got the right headers, although I think you did.

Remember that you're only checking every tenth byte!

win.exe
FB2C0BC08E09ACBBB25BA643
t138.txt
82B60700981FB93565B8E3D4
t141.txt
BEC82314CC928320A1665624
winzip crack.txt
BE8B41ED52EA1987B4CF2A04
PKZIP Application Note.htm
80A085ACC314EE770660C61D

In this case, your bytes for filtering are FB, 82, BE, BE, and 80.

Do something like this

Hey mike =] Thanks for all the info...

I tried to use your bruteforcer and I got nothing :/ I even tried to change the bytes to filter... Can u check it for me?



From lcc-win32.hlp -- The time function returns the number of seconds elapsed since midnight (00:00:00), January 1, 1970

So if I set my clock to 1/1/2002, call time(NULL). Then set my clock back to 9/4/02, today , call time(NULL) again, I can for sure garantee that my seed is between this two values ?




Can you give some examples?

Now about the code..

for(k=0; k<9; k++) rand(); // Why you do that? Trick #3 maybe?

It should be srand(time(NULL) ^ getpid()).
The high byte of the process ID on win9x is 0xFF. I think that process ID's don't go much above 255 on NT.

No. Winzip calls rand 10 times for each file and then encrypts them twice under the same password. Encrypting twice *decrypts* the first byte. So we check the first byte of the ten for each file and throw away the other nine.

Yeah. See the next post.

Here are the twelve-byte headers again (you missed one byte on the first one):
9DFB2C0BC08E09ACBBB25BA6
82B60700981FB93565B8E3D4
BEC82314CC928320A1665624
BE8B41ED52EA1987B4CF2A04
80A085ACC314EE770660C61D

I ran my brute-forcer and after about 1/2 second it came up with this sequence for the seeds. Notice that I knew the high 8 bits to start guessing since

0x9D<<23 = 0x4E800000.

I've shown them below with every tenth seed shifted down 23 bits:

4E92F010 9D
EC620E93
72987F0A
A739C9A5
C0F815D4
E486AD47
206E72EE
4E2C7DF9
610248D8
5301243B
C173DE12 82
1CFDCC8D
7929AD1C
ADF9076F
32820476
FF31E961
00B1A6A0
22342AE3
F5976A1A
95DD4875
DF2CD964 BE
D88AA297
317BD2FE
C8B89DC9
89412968
2F9AC28B
D4A44322
ED74DD5D
DAABBAAC
3DBD1EBF
DF56FE86 BE
794F3B31
5184F130
2F388B33
190F892A
70E52B45
0EC470F4
54B61BE7
B522A70E
0A486199
40051DF8 80

Is anyone still interested in this thread?

Maybe i don't get it, anyway i don't understand all this crypto talk, just 2 "advanced" for me.

Why not just bruteforce it 2 unzip the contents without entering the right password? i once wrote a little tool in Delphi that let u unzip/unrar without entering a password it also handled RARselfextracting files.
If remember it right it could handle WinRAR 2.8/2.9 2.9Selfextract
and WinZip 8.0/8.1beta, thats as far as i got before i found me some new stuff to play with.

BTW, it was a simple memory patcher modyfied a bit. With the Zip's and RAR's it played with WinZip memory, and with RAR's...
I don't remember abt the selfextracting RAR(probaly something with the caption title of the file).

The keyspace is 12 bytes or 8*12=96 bits. That's 4 billion times harder to brute force than the distributed.net rc5 challenge.

...again i have learned, do not involve urself into stuff u absolutely not have a clue about. :-)

- who do not ask do not learn -
or something like that....

wrong

right!

This is very very intersting thread even though it is old
Does anybody still interested???

I'm happy to continue as long as someone is interested enough to ask questions and try things out for themselves.

"Nobody" is always interested

http://www.google.com/search?hl=en&ie=ISO-8859-1&q=winzip+encryption+vulnerability&meta=

Have phun

Hmm... I have one passworded zip file which contains 4 files.
I have 1 file which included passworded zip file.
I tried to zip this file to same option so I can use it for PKCRACK
When I tried to make zip file, the filesize does not match with passworded zip file.

So... let say, in the that passworded zip file, the file shows 290.262 byte.
I think I have to make a new zip file which contains 290.250 byte file.
But I cant make 290.250 byte file somehow!!

I tried all method to make zip file but it goes other byte which means it would not work with PKCRACK.

What can I do now!?

Pkcrack is not the only method... there are better ones available.

If you know the better one, how come you did not give a hint?
I also tried AZPR but it was useles...

The non encypted file was name with non-english letter.
I think AZPR cant recognize non-english letter (it was Korean).

Please share the information

Thank you very much!

There are three attacks on zip files. The first is password guessing. If you know the password was korean, then you might try a dictionary attack with a korean wordlist. You should reverse-engineer the app to see if it actually does anything with korean letters though, since many zip programs don't use unicode. It may have translated all the characters to underscore or something stupid like that.

The second attack is the known-plaintext attack, or Biham-Kocher attack. To mount this, you need a copy of one file that's in there and the same zipper program using the same compression method. This lets you get the password and decrypt the other files you don't have.

The third attack is an attack on the random number generator, or Stay attack. This one works if there are more than four files and the zipper uses InfoZip's random header generation method. Since InfoZip was open source, most people used their code for implementing that.

It sounds as though you have a zip file with four archived files inside. If you know one file, you can use the known-plaintext attack. The Stay attack only works if the zipper used InfoZip's method for generating headers, and it's really iffy unless you have five files. You'd have to reverse-engineer the zipper to find out.

Naides: I'm happy to answer questions, but this thread died a couple years ago, and I'm not sure what people want to know. So if you have a question about any of the attacks, ask it and I'll see what I can do to clear it up.

I also though about the answer will be known-plaintext attack.
But the problem is, I dont know what program and compression method used for encypted zip.
I think I tried most of known zip program and compression method but I was not able to make same compressed size.

Let say, one file's compressed in encypted zip was 29,600,480 byte
Based on that information, I think I have make a zip which includes 29,600,468 byte compressed file.
But I cant make that file somehow.

Is there anyway to figure what the encypted zip was made by??

PS: Im very sure that the file is exactlly same because when I compared the file's CRC with encypted zip and the zip file that I made were same.

No, there isn't. And unless you know which program it was, the compression varies too much from one program to another to be able to use the attack.