# Thread: Simple encryption (RC4 like)

1. Check out some RC4 like encryption:

Code:
```  int tab[256];
for (int i = 0; i < 256; i++)
tab[i] = i;

int a = 0;
int b = 0;

int x = 0;
int y = 0;

int c;
while ((c = getc(input)) != EOF) {
a = tab[x = (x + 1) & 255];
b = tab[y = (y + a) & 255];

tab[x] = b;
tab[y] = a;

putc((c ^ tab[(a + b) & 255]), output
);
}```
Small and fast code. With simple key (tab) generation can be used to hide info. And with proper key initialization can be used as a nice encryption solution!

2. RC4 is really a nice algorithm, and I admit I like elegant and simple to remember encryption algorithms like i.e. RC4 and TEA/XTEA, and projects to spread them, like Ciphersaber does for RC4.
However, to use RC4 in real life scenario it's needed to apply some good practices (most for patching the weak key schedule), at least: non linear combination with initialization vector (i.e. passing them in a good hash) and discard some of first outputs of the stream.
Probably today it is wiser to switch to use AES or other AES contest finalists, like Serpent and Twofish, which have withstood more analisys since more widely adopted in recent years, in hardware as in software based solutions.

3. By the way, I have a few ideas for my own encryption.

For example, with RC4 we use XOR with pseudo random number generator. The behavior of this generator is depends on its initial state which defined by the key. During encryption/decryption, the internal state is changes according to the algorithm. However, the state NOT depends on input data. My idea is to use a context sensitive permutator - i.e. the state changing WILL depend on actual data. Thus if we not correctly decrypt part of a code - all further decryption becomes impossible. It is like with compression - change some byte somewhere in a compressed stream - all followed data will be garbage.

4. Originally Posted by encode
My idea is to use a context sensitive permutator - i.e. the state changing WILL depend on actual data
That is a cool idea but if not perfectly implemented it opens the door to possible chosen plaintext attack scenario.

5. Afaik, for encryption entropy coding is necessary, but not vice versa.
That is, feeding 64k of key sequence to the model and then compressing
the data should be as good as any widespread encryption without its
speed impact. Probably even better as there're already built hardware
crackers for well-known encryption schemes. And encryption support in
compressor is necessary anyway - at least, removal of predictable fields
at the start of compressed data.

Ideal solution is when you need to process the full archive and compare
the data crc to check if the key was right. So its especially bad with
LZ compressors because they tend to have some "forbidden" sequences
making possible the key testing without complete decoding.

6. Originally Posted by Shelwien
And encryption support in
compressor is necessary anyway - at least, removal of predictable fields
at the start of compressed data.
Are you have knowledge of this area? encryption schemes developed even with known-text attacks in mind. in particular, they encode random word before actual text, which makes this no problem

Originally Posted by Shelwien
LZ compressors because they tend to have some "forbidden" sequences
making possible the key testing without complete decoding.
again, its standard to include check code (at least winzip has and it uses fipsapproved library). this check code allows to validate password in a exactly specified amount of time (say, 1/30 sec), so we control process instead of relying on non-controlled things

dont forget that our goals not only security but also reliability. what if user missplelled password - does he need to wait 3 hours to know this? what if two passwords used in same archive - does we need to double decoding time? for intruder, decreasing time required to check one password from 3 hours to 1/0 sec, will mean that he need to perform, say 10^90 operations instead of 10^95

7. > > And encryption support in compressor is necessary anyway -
> > at least, removal of predictable fields
> > at the start of compressed data.
>
> Do you have knowledge of this area? encryption schemes developed even with
> known-text attacks in mind.

Actually, for encrypted archives, plaintext attacks are possible in most cases
because of redundancy of most practically used file formats.

> in particular, they encode random word before actual
> text, which makes this no problem

I kinda talked exactly about that.
But still, usually some additional modifications are needed to
make a compressor stronger against plaintext attacks.
Like, rar blocks have 78 bit header with known data layout
and value intervals. Or, eg, most of my rangecoders have
a zero byte at start of compressed data. In both cases
this presents a possibility of faster plaintext attack.

> again, it's standard to include check code (at least winzip has and it uses
> fipsapproved library). this check code allows to validate password in a exactly
> specified amount of time (say, 1/30 sec), so we control process instead of
> relying on non-controlled things

Well, you know, I think nobody cares about (non-existant) cryptographic
strength of winzip. Also, for example, rar imho does exactly what you
said about waiting 3 hours and I never heard that its a "reliability"
problem.

> don't forget that our goals not only security but also reliability. what if
> user missplelled password - does he need to wait 3 hours to know this?

1. User always can add some small file at start of archive.
And I don't see any reason for special efforts to limit the checkup time.
Actually, password-protected archive is "unreliable" by default.

2. What I actually talked about is that its best when decompression
process is made a part of key checkup. So you can design such an archive
format that crc check would be possible after decoding the first data
block or something, if you really need this "reliability".

> what if two passwords used in same archive - does we need to double
> decoding time?

Of course not, with the suitable archive format.
(Like, it can have explicit support for multiple passwords and
a field with password# in the file header - certainly not a
password hash or anything like that).

> for intruder, decreasing time required to check one password from
> 3 hours to 1/0 sec, will mean that he need to perform, say 10^90

1. You know, its quite a difference actually. Compare it with the
old DES-based unix crypt and new MD5-based. Here, DES bruteforce runs
at 800k passwords/s and MD5 at 5k/s - only 2 orders difference
instead of your 5, but from the practical point of view the result
is that having DES hashes means I have access to the compromised
system without any expensive resources, and with MD5 it means
I have to run bruteforce for half a year.

2. Decompression may be even faster than decryption, but well-known
cryptoargorithms are relatively simple anyway, and don't need much
memory to work. That makes a difference too, because for AES and the
like something like this: http://nsa.unaligned.org/index.php
always can be built easily enough.

So, basically, I'm trying to say that its actually _much_ cheaper to
find a key to a "normal" archive wrapped into a container with
some standard encryption, than to some home-brewed scheme like ppmd
model updated with 64k of key permutations before actual compression.

Anyway, encryption strength shouldn't be measured by the cost of
cracking the specific archive with strong passphrase. Instead,
its better to assume that there're 100 archives and some of them
are encrypted using the words from a accessible 100k-word dictionary.

And I think you shouldn't implement any encryption at all, if you think
that "script kiddy protection" is enough as there're better standalone
tools.

8. >Like, rar blocks have 78 bit header with known data layout
and value intervals.

at the start of encrypted data, random-chosen word (called Initialization Vector) is encrypted. because encryption of the following data depends on this word, this makes plaintext attacks impossible

>Well, you know, I think nobody cares about (non-existant) cryptographic strength of winzip.

probably you mean old scheme. now winzip uses properly implemented aes

>Also, for example, rar imho does exactly what you

there are crackers that try 30 passwords per second. probably they use redundancy of first bytes of compressed stream

9. > > Like, rar blocks have 78 bit header with known data layout
> > and value intervals.
>
> at the start of encrypted data, random-chosen word (called Initialization
> Vector) is encrypted. because encryption of the following data depends on this
> word, this makes plaintext attacks impossible

Well, its a terminology question, but I think it doesn't.
Its a technique similar to "salt" in password hashes and it only
blocks simultaneous checks for multiple archives.
And what I called "plaintext attack" is a high probability of key value

> > Well, you know, I think nobody cares about (non-existant) cryptographic
> > strength of winzip.
>
> probably you mean old scheme. now winzip uses properly implemented aes

I know, but its a relatively easy target anyway.

> > Also, for example, rar imho does exactly what you
> > said about waiting 3 hours
>
> there are crackers that try 30 passwords per second. probably they use
> redundancy of first bytes of compressed stream

Yes, and it won't be possible in proper implementation.
Also I don't think thats a real maximum speed.
But even if it is, nowadays there're multicore CPUs and
GPU SDKs available.

10. Originally Posted by Shelwien
Its a technique similar to "salt" in password hashes and it only blocks simultaneous checks for multiple archives.
In case of stream ciphers or block ciphers used to generate an encryption stream (i.e. CTR and derived modes) salting is also fundamental for security because when the same key is applied without salting, the same stream is generated.
That allows to xor (or other linear combination) two messages encrypted with same stream to simply remove the stream and let the two message xored each other, which are quite simple to separate with linear analisys since are not likely to be cryptographically strong pseudorandom.

Originally Posted by Shelwien
And what I called "plaintext attack" is a high probability of key value discarding without decompression involved.
If I not misunderstood the point, its not an issue, since its due to the key derivation function to set an arbitrary and provable computational complexity amount for each password tested.
In that way the legitimate use can validate the password (test against a known string) in a negligible "time ticket" without waiting for decompression / decryption of data while the attacker will need to spend the "time ticket" 2^n times where n is the size of keyspace, easily resulting in an infeasible computational complexity.

Originally Posted by Shelwien
> probably you mean old scheme. now winzip uses properly implemented aes
I know, but its a relatively easy target anyway.
That depends on the scenario.
Zips AE (WinZip 9) and AE2 (WinZip 10, backward compatible) were developed to protect data, and does it well (its no longer possible to trivially bruteforce the password, and there are no known shortcuts to compromise the password in a computationally feasible way), but were designed to let some metadata (notably, filenames) in clear to keep possible (and simple) some advanced archive handling operations.
Tadayoshis cryptoanalisys shows it was not an optimal design choice (from the security point of view), and it is insecure for some scenarios, but AFAIK it demonstrated solid in protect what it was meant to protect...
the problem is that the user should be aware of what does this solutions secure and what not, while chosing instead a proven no-compromise solution like GPG/PGP (or other archive formats with different encryption strategies) will guarantee the data is secure under any conceiveble scenario... until used correctly, too often it is the user the weakest link of data security!

11. >> Its a technique similar to "salt" in password hashes and it only blocks
>> simultaneous checks for multiple archives.
>
> when the same key is applied without salting, the same stream is generated.
[...]
> are not likely to be cryptographically strong pseudorandom.

Well, right, though youd need two files encrypted with same password
for that, and were talking about archive encryption here, so the data
_would_ be cryptographically strong even with simple LZ compression.
But anyway I bet you know that this is not the point here

>> And what I called "plaintext attack" is a high probability of key value
>
> If I not misunderstood the point, it s not an issue, since its due to the key
> derivation function to set an arbitrary and provable computational complexity
> amount for each password tested.

Right, and actually Roshal said the same thing when Id asked him to
But still, I dont understand whats the reason to keep the
"proved encryption strength" when you can easily raise it to much
higher level by insignificant archive format fix.

As for now, with this "provable computational complexity" key initialization
thing, massively parallel computing and precomputing of key sequence are
easily available, and even rainbow table approach is possible, though itll
work really good only with large enough known plaintexts.

> In that way the legitimate use can validate the password (test against a known
> string) in a negligible "time ticket" without waiting for decompression /
> decryption of data while the attacker will need to spend the "time ticket" 2^n
> times where n is the size of keyspace, easily resulting in an infeasible
> computational complexity.

As I already said, theres no sense in talking about cracking the
specific archive encrypted with a strong key.
I think that if youre able to try around 10^7 keys using the cheap
equipment, then it doesnt matter how theoretically strong is this
encryption scheme.

http://elcomsoft.com/edpr.html
Besides, hardware acceleration using GeForce 8 video cards is now available
not only for NTLM, but also for LM hashes. Further optimization for 8800
series cards has been performed (we have achieved 120 million LM passwords
per second and 350 million per second on GeForce 8800 ULTRA).
So, my point is that simple (though maybe computationally hard)
encryption schemes are easy targets for massively parallel cracking,
which is rather cheap these days.
But involving actual decompression into key check procedure afaik
is a really good countermeasure, because massively parallel hardware
implementation of the whole decompression process would be several
orders more expensive than something like AES.

> Quoting: Shelwien
> > probably you mean old scheme. now winzip uses properly implemented aes
> I know, but its a relatively easy target anyway.
>
> That depends on the scenario.
> Zips AE (WinZip 9) and AE2 (WinZip 10, backward compatible) were developed to
> protect data, and does it well (its no longer possible to trivially bruteforce
> the password, and there are no known shortcuts to compromise the password in a
> computationally feasible way),

Well, Im not interested in winzip anyway so cant say much.
But anyway its default is zip2 encryption and even in AES256
mode available crackers work 2x faster than for rar.
So guess its no wonder that I never seen a "live" encrypted winzip
archive.

> Tadayoshis cryptoanalisys shows it was not an optimal design choice (from the
> security point of view), and it is insecure for some scenarios, but AFAIK it
> demonstrated solid in protect what it was meant to protect...

Well, Id not call that a cryptoanalysys, if youre talking about
http://www.cs.jhu.edu/~astubble/dss/winzip.pdf
as it doesnt consider the bruteforce password recovery at all.

Its not a open format so theres a high enough possibility of
some design flaw in implementation... like that way of license
key generation for rar where strong algorithm was used, but
adjusting the _name_ to match the key digest was still easily possible.

And anyway I dont believe that these GUI crackers for zip and rar
are really optimized.

12. Check out the simplest algo by myself:
Code:
```
#define KEY 101 // or any other prime number
#define A 3 // (KEY * i) should be always bigger than 255

// buf[] - data buffer
// n - data size

for (int i = 0; i < n; i++)
buf[i] ^= (KEY * ((i + A) + n));```

13. An improved version:
Code:
```
for (int i = 0; i < n; i++)
buf[i] ^= ((KEY * (i ^ n)) % 251);```

14. Well, here's a test:

Code:
```
#include <stdio.h> const int KEY = 101;
// or any other prime number
const int A   = 3;   // (KEY * i) should be always bigger than 255
void main( void ) {
FILE* f = fopen( "data1.bin", "wb" );
FILE* g = fopen( "data2.bin", "wb" );
int n = 1<<20;
for( int i = 0; i < n; i++ ) {
putc( (KEY * ((i + A) + n)), f );
putc( ((KEY * (i^n)) % 251), g );
}
}```

And so, we see that data1.bin's period is 256 bytes
and data2.bin's 251 - that's really cool for
encryption. Its real pity that rar doesn't use such
a scheme for encryption... or else I could get access
to some useful things...

As a practical measure, you could at least try to
compress your key sequences with paq8 or something,
though of course its not a replacement for a real
cryptoanalysis.

Also, don't forget that % is the same as division.
Meaning too slow.

Though I guess it could be implemented like this:

Code:
```
#define vecmod(a,b) (a-((__min(1,byte(__min(a,b)-b))-1)&b))
for( i=0; i<16; i++ ) {
result.b[i] = vecmod( result.b[i], 4*62 );
result.b[i] = vecmod( result.b[i], 2*62 );
result.b[i] = vecmod( result.b[i], 1*62 );
}```

That's from my bruteforce cracker for some md5 derivative
which works like hashbyte[i]="0..9A..Za..z"[md5byte[i]%62].
So that code above is used for remainder calculation and
what's most fun, its automatically vectorized into SSE2
by IntelC.

Edit: Damn, your code tag is weird.

15. Another solution:
Code:
```
// c - current char
// KEY - prime number
// i should be started at 1
// n - data size

c ^= ((i * i) ^ n) % KEY;
i++;```
It's about encrypting short strings. The algorithm can be described as a pseudo random number generator + XOR.
Generator should be heavily connected to the KEY.
Sequence of a repeated char like
0000000000000000000
Should be encoded as random numbers.
The size of a string does matter, thus:
ABC
and
ABCD
well be encoded in a completely different way. (The first encrypted ABC in both cases will be different)
Like I said it's about string integrity protection in executables/files. The 8-bit key is very weak, however we can use larger ones. What helps is that you should know there exactly the string was placed and how long it is. Without that the decryption is impossible. Now imagine how using hex editor to find and modify such strings within an executable.

16. > c ^= ((i * i) ^ n) % KEY;

That's bad too - i*i gives a skewed distribution.
At least read http://en.wikipedia.org/wiki/PRNG or something

> Like I said it's about string integrity protection in executables/files. The
> 8-bit key is very weak, however we can use larger ones.

Ah, then it doesn't matter how cryptographically strong the function is.
Though functions like yours do allow parameter determination by statistic analysis, but its usually not the weakest point in executable
protection anyway

> What helps is that you
> should know there exactly the string was placed and how long it is. Without that
> the decryption is impossible. Now imagine how using hex editor to find and
> modify such strings within an executable.

Nobody actually uses simple hexeditors for that... though hiew has a
crypt function with simple pseudocode that still allows to implement
functions like yours. But normally for tasks like that you just write
a script for ida which finds decryptor calls in executable by byte
patterns and decrypts the data.

So, fast and simple algorithms are actually bad for this purpose.
Instead, you should make some really complex and preferably asymmetric
algorithm (so that it'd be hard to reconstruct the encoder by decoder).
Then its best to write the protected parts using some interpreted
pseudocode - the weirder the better.

And still, all these measures only make cracking more expensive,
not completely prevent it.

17. It's against hex editor and dummy kids.

By the way check out my own anti-debug trick. The idea is simple, the code is encrypted using Key. Wrong Key = wrong decryption.
Key is generated at startup.

i = getmilliseconds();
sleep(123);
key = getmilliseconds() - i;

i.e. the application should run in real time, or it will be wrong decrypted.

On real machine the time difference may be not be exactly 123 - for example it may be bigger by a few milliseconds - due to function calls. The debugger/emulator may not reproduce the exact values. He-he... Simple and cool trick...

18. Originally Posted by Shelwien
Thats bad too - i*i gives a skewed distribution.
However, combined with XOR N and MOD KEY, it generates a pseudo random numbers - check for yourself.

Originally Posted by Shelwien
At least read http://en.wikipedia.org/wiki/PRNG or something

19. > It's against hex editor and dummy kids.

That reminds me some funny trick i've used in old days
Decrypt the encrypted part there

> By the way check out my own anti-debug trick. The idea is simple, the code is
> encrypted using Key. Wrong Key = wrong decryption.
> Key is generated at startup.
>
> i = getmilliseconds();
> sleep(123);
> key = getmilliseconds() - i;
>
> i.e. the application should run in real time, or it will be wrong decrypted.

Well, my congratulations, you've invented quite a common trick
Though it was really useful only in DOS times, and even then mostly
in the form of non-zero clock delta detection - you can't expect
it to work the same in different systems and different CPUs.
Also you need to avoid system calls in such situations as context
switch is unpredictable thing, and its better to use TSC (processor
clock counter accessible with a rdtsc command) for timing.
And finally, you'd have to wrap all this into infinite loop until
it'll be able to successfully decode what it needs and get a valid crc.
Or else your program will be really unstable.

However, it won't really help anyway as its a anti-tracing trick,
so you only need it in places where hacker would gain something
from single-stepping your program. And in places like that,
timer checks are really noticeable and easy to avoid - I've seen
it many times, but never had any problems with it.

Also there're emulators and many other tools available, so the only
way to make your program virtually uncrackable is to make it
really, really complex - it'll help much more than any of these
low-level tricks.

20. Well, I tested it on many CPUs - it works pretty accurate. However, the precision is about a few milliseconds. Note that we can divide the result by 2 or 4, to fight with such stuff. In addition, to override any problems, like you said, we can use an infinite loop - until we get a proper value.

21. And finally, the simplest pseudo random number generator:
Code:
```
int r = KEY * n; // seed

while (1)
c = (r *= 123456791) >> 24;```

22. Probably, Ill write a simple EXE-cryptor/protector/wrapper on Delphi.

OK, check some dummy prototype:
rash-test.zip (9 KB)

This small console program just decrypts and outputs some text:
Originally Posted by rash.exe
rash by encode
test done!
To generate the key for decryption, it uses timer/sleep trick described above. Wrong timing = wrong key = wrong decryption. Program will run infinite loop until proper key will be generated, thus if program froze, that means the key cannot be correctly generated.

Who interested, may disassemble, and/or run this tiny proggie and post the results here...

23. > To generate the key for decryption, it uses timer/sleep trick described above.
> Wrong timing = wrong key = wrong decryption. Program will run infinite loop
> until proper key will be generated, thus if program frozes, the key cannot be
> correctly generated.

Well, its exactly like I was saying before...
That is
1. Don't use delphi if you are really trying to protect anything -
it generates really readable/unoptimized assembler code.
2. Anti-debugger tricks don't have any sense if its possible to just
stop at the breakpoint set after all tricks. Actually the program
runs under debugger the same way as normally - at least if you're
not dumb enough to single-step a timed loop or something like that.

> Who interested, may disassemble, and/or run this tiny proggie and post the
> results here...

Code:
```
Comparing files rash.exe and RASH.EXE.ORIGINAL
00002F2C: 0C 0A
00002F35: 38 3A
00002F36: A2 AC
00002F37: 41 46
00002F38: E1 E8
00002F39: 97 D3
00002F3A: 33 00
00002F3B: 9D 00```

All it takes:
1. In the debugger I see that the second encrypted string
starts with 11 AF 5C E0
2. Run hiew32 rash.exe
3. Press F7, then 11 AF 5C E0 (search)
4. Press F3(Edit), F8(xor), enter the unencrypted string "test done!"
The result is: 65 CA 2F 94-F9 5E C3 28 8D F2
That's the key sequence.
5. Press Ctrl-F8 (set xor), enter "test failed!", F8(xor)
Result is: 11 AF 5C E0-D9 38 A2 41 E1 97 64 21
6. Also I see "0A 00 00 00" (=10), the string length - lets
change it to "0C 00 00 00"
7. F9(write changes), quit hiew32
8. Stating rash.exe, it says "test faile3З"
9. Repeating steps 2-7, just with "test faile3З" instead of "test done!"
And we get 11 AF 5C E0 D9 38 A2 41 E1 97 33 9D

So its even possible to replace the encrypted text with a _longer_
string while knowing nothing about the used encryption.

24. Cool!

Actually, there is no uncrackable software. Even such stuff like Cubase CX with its USB Keys already cracked. ALL popular games and software already cracked, be sure. And many of them spend lots of money to get descent protection... However...

The only difference in crack time 5, 50 minutes or 5 days...

OK, check out more advanced rash-test:
rash-testv2.zip

Note that I'm just playing with Delphi.

25. > Actually, there is no uncrackable software. Even such stuff like Cubase CX with
> its USB Keys already cracked. ALL popular games and software already cracked, be
> sure. And many of them spend lots of money to get descent protection... However...

You see, they buy SDKs for these hardware dongles and then use them
same way like you do with your prng, and think it'll protect something.
Real protection strength doesn't depend on money spent on it or
hardware used - it just has to be done properly.
For example, there's this utility called sockschain.
Its protection scheme is purely software. But all the critical
code/data blocks are protected with crcs, and license check and
crc checks are all written in lisp pcode (along with some necessary
initialization without which program won't work), for which they
have their own compiler. And that's enough - there're no
and there's demand for it.

> The only difference in crack time 5, 50 minutes or 5 days...

5 days is still too easy.
Protection has some sense only if hacker has to write some
complex custom tools like decompilers to crack it, and it
takes months.

Btw with your attempts it takes much more time to write a
post like this.

> OK, check out more advanced rash-test:

Don't see how's this more advanced...

> Note that I'm just playing with Delphi.

Well, you've added a data dependency, so now its bothersome to
decrypt/encrypt it in hiew (still possible though).
But its still easy to see decrypted strings in debugger, then
disable the decryption and write decrypted strings into .exe

27. Another fun-art by myself:
HEXEDIT.zip (522 KB)

An old HEX EDITOR wrapped with RASH. Don't know what's this, but it's fun!

The RASH stub decrypts and drops a temp file, after that, executes it. If you will close the executed program, the temp file will be automatically deleted.

28. Btw, here's what a certain program shows for your function.
I renamed some things though.

29. By the way, how I can find such debugger?

In addition, check out some cool anti-emulation tricks:

SMSW
Use the SMSW instruction:
Code:
```
XOR EAX, EAX
SMSW AX;
AND EAX, 1
MOV Key, EAX```
Many emulators seems to be unable to emulate SMSW correctly. We store the machine state into register, the first bit should represent a protected mode (1 = On, 0 = Off). Don't know about other bits and how they CPU independent.

Expensive key calculation
We can use recursive Fibonacci:
Code:
```
function Fib(I: Integer): Integer;
begin
if I >= 2 then
Result := Fib(I - 1) + Fib(I - 2)
else
Result := 1;
end;```
Key := Fib(N);

Page 1 of 2 12 Last

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•