Encryption challenge

encryption isn''t even close to my strong suit, but i believe that the strength of an encryption algorithm is partly based on how secure it is _even when the cracker has your algorithm_. if your encryption is easily broken when the algorithm is public then it''s not good encryption. the idea is that your algorithm _will_ get out. if it''s not secure under that condition = no good.

-me

In a way the encryption algorithm is already public (that's a mild hint). But if someone were to get a hold on my code then it wouldn't be secure anymore, so your point is well taken.

[edited by - YoshiN on December 2, 2002 8:47:18 PM]

obscurity is not security

A good encryption algorithm must be that even if you know the decryption algorithm, you can''t decrypt the packet without the key.

Then, even if you did that, it must be that the key can''t be discovered by any mathematical way, and beleive me, when you know cryptography, mathematics can do miracles.


______________________________
Oooh, you found the horadric cube!

Well the algorithm itself is really simple, I took the ascii value of every character and added a certain number to it (and that number fluctuated throughout the file), and then XORed it. It also uses a random number range and a random key each time (so the range and key are hidden in the file). If someone knows the algorithm, it''s useless without the range/key, but if you have a file and you know where they are hidden, then it''s easy from there, so I guess it''s not too secure.

quote:

---

Original post by YoshiN
Well the algorithm itself is really simple...

---

A good encryption scheme is secure even when the implementation of the encryption (and, in some cases, decryption) is in the public domain.

On the topic of encryption and security, I have to wonder what will happen when/if quantum computer come into being. Apparently the current encryption schemes will be easily cracked with the new computers. Though apparently there are quantum encryption schemes out there that may be uncrackable. Maybe I should learn more about encryption

Ok the following is not meant to sound harsh, it is just some advice, but I really hope you're not going to think that your cryptosystem is secure because no one here breaks it.

Posting that encrypted pic here is going to demonstrate whether it is a safe encryption or not. I can tell you this much - Unless you disclose at least precisely what algorithm you used, no one here will break it. In the thread where XOR encryption was broken, we all knew the algorithms. Posting that thing without telling us what the algorithm is, is equivalent to posting a file full of random garbage. If you fail to see even that, I already seriously doubt that you know anything about cryptography at all.

Read here why "contests" like this will prove nothing.

I will take the liberty of quoting some relevant pieces.

quote:

---

Cryptanalysis assumes that the attacker knows everything except the secret. He has access to the algorithms and protocols, the source code, everything. He knows the ciphertext and the plaintext. He may even know something about the key.

---

quote:

---

Unfair contests aren't new. Back in the mid-1980s, the authors of an encryption algorithm called FEAL issued a contest. They provided a ciphertext file, and offered a prize to the first person to recover the plaintext. The algorithm has been repeatedly broken by cryptographers, through differential and then linear cryptanalysis and by other statistical attacks. Everyone agrees that the algorithm was badly flawed. Still, no one won the contest.

---

And now, I really don't intend to sound harsh, but the fact that you're admitting that if your algorithm can probably be broken if it is known indicates that you aren't even familiar with Kerckhoffs principle. It embodies the entire philosophy of modern cryptography:

quote:

---

The security of a cryptosystem must not depend on keeping secret the crypto algorithm. The security depends only on keeping secret the key.

---

[edited by - mr BiCEPS on December 2, 2002 12:23:49 AM]

Oh I know that my encryption algorithm could never be 100% secure, and I have no doubt that a really talented person could crack it, perhaps even easily. But thanks for the link.

The strength of an encrpytion algorithm is not determined by ''IF'' it can be broken, but rather how long will it take using modern computers (with some Moores law applied over time) to brute force it open.

The XOR algorithm (which I think I might have posted in another thread) is a very simple algorithm. In the example I think I told you to stick some random numbers at the beginning of your data, and to effectivley encrypt it twice. I''ll explain why later.

Back to my main point: the reason why it is not ''secure'' is as follows:

There are 2^32 keys that can be used with that algorithm.

It would take a modern computer about 5 seconds to run through every possible key. Therfore, you algorithm is perfectly secure if the data inside is valuable for no more than 5 seconds.

Herin lies the weakness.

Most modern cryptosystems involves much larger keys, and implement algorithms that are time-consuming for a computer to solve. It could take an attacker 25+ years to try every single possible key for IDEA. It still suffers from the same weakness as the XOR algorith though-- if the encrypted data needs to be secure for more that 25 years, the algorithm may be useless.

So thats the theory..

It is unlikely that you need such a high level of data security, since anyone REALLY serious about hacking your copy protection could just reverse engineer a legit copy of the game, and look at the decrypted copy protetection data AFTER your program has loaded it in to memory..

That said, this is why the XOR code I gave you should be acceptable.

Yes, there are only 2^32 keys. However, it''s kind of hard to know if you''ve got the right password if you don''t know what the decrypted data should look like to begin with-- that''s why you''re supposed to add the random numbers to the beginning,etc..
This keeps your data more ''random''.

This is still not foolproof however...

If you''re plaintext data says ''Hello World'' (or ''JPEG''), and the attacker knows that there are some english words in the ciphertext somewhere, you''re SOL, because they can try all 2^32 keys and check the output against an english dictionary...

If you really wanted, you could use 64 or 128 bit keys.. Why not 1024 bit keys? Go as high as you want-- with each extra bit you''ll double the amount of time it takes somebody to brute-force a password.

But then you have another problem: Say you have a 1024-bit key... And the ''encrypter'' types in ''pass'' for his password... If you just copy the ''pass'' into the key you''re left with a 32-bit key again (cause the other bits were not set)(0x000000000pass = 0xpass).

So instead you should generate an n-bit hash out of the password, and use the hash as the key. A hash is simply a number that corresponds to some ''data''.

If you want to compute a 1024 bit hash do as follows:

For each letter in the alphabet generate a random 1024 bit number. The resulting array of numbers is called a hash table..
You cant really use random numbers, because the decrypting side needs to generate the exact same hash''s..

When the ''encrypter'' picks a password, start with an empty 1024 bit number (set to 0), and XOR the hash value of each letter in the password to the empty 1024 bit number..

ie: p = 1010 a = 1100 hash = 0110 ( 1010 XOR 1100)

Cheers,
Will

quote:

---

Original post by Anonymous Poster

I''m curious, how does this help? If you establish a one to one correspondence against some easily reproduced hash table, you still have the same number of variable ''key'' bits, you''ve just run a simple encoding step on the key (Which adds very little security to someone who understands the algorithm.)

This is kind of like why running rand() a bunch of times won''t generate a 1024 bit key. The ''key'' is still whatever you seeded the random generator with.

---

I couldn''t agree more, if the attacker is brute-forcing the algorithm through the applications own interface, or via code disection...

If they are brute forcing though the applications interface, the interface should force a 1 or 2 second ''wait'' before asking for, or accepting, a password... 2^32 * 2 seconds is a long long time.

If they have disected the code, then encryption of any sort will offer no protection. The attacker could simply work around any protection that they encounter.. I think I mentioned this earlier.

The benifit comes if the attacker only has access to the encryption algorithm, and is manaully generating keys (key = 0; key < 2^1024; k++). This is a different matter because the first 1024-32 of your bits aren''t 0, making the key harder to predict. But you are right, a four-byte password still has only 2^32 possibilites, regardless of how it is encoded. The enhancement here only makes the sequence less predictable.

rand() * rand() * rand()...Should be good enough (all things considered). If you''re aware of something I''m not, please let me know.

To ''prove'' it''s merit, reencrypt a JPEG (better yet, a file type that is not known) using the same method (random number header, etc..). Keep the hash table secret, but publish the source for the encrpytion algorithm. Use a 1024 bit key. See how long it takes for someone to decrypt it this time. I doubt you''d be getting a solution anytime today. Even if the password were ''pass'', you''ll still have to search at least 50% of the 2^1024 space before you get the answer.

I''m not saying this is a super secure algorithm-- I mention it only as an alternative to a=b, b=c, c=d, etc.. If you want something secure, go download blowfish or something.

Cheers,
Will

there is a far easier way to solid xor encrypotion.

the strength of any algorithm using daya mutated according to a sequence of numbers depends on the size of that sequence of numbers (the pad)

the reason being, within a finite amount of data, the contents of the pad repeat, simplifying decoding enormously



proposal:

one pseudo-random number generator which takes a DWORD input and gives a DWORD output

one arbitary string (the key) at least 4 bytes long

encoding/decoding steps

     index=0
     for the first (data.length-4) bytes of the data to be encoded
          put the dword at key[index%key.length] into the randomiser
          xor the dword at data[index] with the output 

not only is the size of the pad in the billions (brittish billions: thousands of gigabytes), but a key of maximum length X gives (approx) 2^(8*X!) unique pads of varying lengths

not only that but since the pseudo randomizer uses other numbers to mutate the seed, those other numbers could be updated each iteration with data from the source, increasing the length of the pad by many orders of magnitude

incidentally, the combined lengths of the possible encryption pads for a 32-bit key far exceed the number of atoms in the known universe. you would have to try each of them to decode any file as big as the pad.



the only weakness in this algorithm is the public key problem: the encoder has to send the key to the decoder somehow.

if you want ultra-security, Diffe-Hellman uses 2 keys: a public key for encoding and a private key for decoding. each is about 512 bytes but the maths is horrible.

if you want a fast, local encryption, it doesn't get much more secure than this.

********


A Problem Worthy of Attack
Proves It's Worth by Fighting Back

[MKH edit: fixed missing /code tag]

[edited by - Magmai Kai Holmlor on December 4, 2002 10:09:28 AM]

a

aw hell, the "edit" link has disappeared. sorry for the mess above

quote:

---

Original post by Cold_Steel
On the topic of encryption and security, I have to wonder what will happen when/if quantum computer come into being. Apparently the current encryption schemes will be easily cracked with the new computers. Though apparently there are quantum encryption schemes out there that may be uncrackable. Maybe I should learn more about encryption

---

Most public-key schemes rely on the relative "difficulty" of certain things, like factoring large numbers (in the case of the RSA algorithm) or calculating discrete logarithms in a finite field (in the case of ElGamal). It has been theorized that "quantum computers" could make these things pretty trivial.

Unfortunatly (for the cryptanalysts, at least) quantum computers are probably still decades away from being able to do anything like that.

Actually these "difficult problems" are a really interesting branch of mathematics. There are a few "levels" of difficulty with respect to types of problems. A P problem is one which can be solved in polynomial time and space (with respect to the size of the input data). An NP problem is one which cannot be solved in polynomial time (as far as we know). One example of this is the famous Travelling Salesman problem. A salesman has to visit n different cities on a single tank of petrol (i.e. he''s got a maximum total distance he can travel). Is there a path through all n cities which will allow the salesman to visit them all on his one tank of petrol?

It has actually been proven that if the Travelling Salesman problem can be solved in polynomial time, then all problems that fall in the NP category can be solved in polynomial time. That is, the Travelling Salesman problem is the "hardest" NP problem. And it''s not just the Travelling Salesman problem with is the "hardest". There is literally hundreds of problems which have been proved to be equivalent to the Traveling Salesman problem, in terms of difficulty.

The final category is called EXPTIME and consits of those problems which can only be solved in exponential time (with respect to their input size). It''s been proved that no problem in the EXPTIME category could ever be solved in polynomial time (unlike NP where that hasn''t proved to be the case, though most number theorists believe it to be so).

I''ve actually been reading Bruce Schneier''s "Applied Cryptography" recently, and it''s a real eye opener the sorts of things mathematics can do. You''ve got to be extremely careful not just how you implement your algorithm, but how you entire cryptosystem is implemented and managed. Overlook one small detail and your whole system can be compromised. It''s not just a matter of not telling people your key, but it''s how you store your keys, how you exchange data with other computers, how you treat computers you don''t entirely trust, how you dispose of things you don''t need anymore, etc.

I can see why security experts are so highly paid

If I had my way, I''d have all of you shot!

---

codeka.com - Just click it.

walkingcarcass - the edit link hasn''t disappeared, if you scroll across its just off the page

The simplicity of the algorithm is largely irrelevant. An xor scheme can be extremely secure if you use a highly-random, one-time pad - which it sounds like YoshiN did.

The excryption cannot be better than that, and it also cannot be any less convienent to use. By some other means, you must share that key with the recipient, and both of you must protect the pad from prying eyes.

If the length of the key is less than the length of the file encrpted, then statistical analysis can lead to clues as to what the key is. For example, the vowels e & a are very common in English text. Knowing that it''s a jpeg gives enough information to attack the encryption. You just concentrate on the header which has known byte values.
e.g. 0xFFD8 FFE0 xxxx 4A46 4946
So right off-the-bat if it''s less than a 32bit key or less, it''s cracked. If it was a 128bit key, it''s now a 96bit key. And there''s more header information. The next two bytes are the length of the FFE0 tag followed by "JFIF". Cracking the length will give a lot more information becase there are more tags in the header with fixed byte values. Odds are really good that the first byte is 0x00 so can assume we''ve cracked 40bits knowing that. The next byte is a mystery for now, but the next 4 bytes (another 32bits) come for free. Next, I would take the first two bytes of the key, and apply them to the next 32 bytes of the jpeg and look for the next tag, 0xFFDB. If this is uncovered, then I have a really good idea how long the key is - and it tells me the length of the 0xFFE0 tag, filling in the missing byte from either. You can continue this process on the rest of the header though it gets trickier from here on out, as the header format is less certain. There''s about 1536 very deterministic bits, and you might be able to push it to 4864bits if you get a little lucky with some assumptions about the header layout.

I do not think blowfish is a sufficent level of encryption to encrypt a straight jpeg. A key length of about 8kbits to 12kbits is called for.

No wonder it''s so easy to break the encryption of DSS''s. They''d have to use poly-megabit keys to stand a chance.

Those types of attacks can be thwarted by injecting a random amounts of random junk into the encrypted file (both of which are also determined by the one-time pad). I''m not sure how to attack this type of encryption, any ideas?

quote:

---

Original post by Magmai Kai Holmlor
The simplicity of the algorithm is largely irrelevant. An xor scheme can be extremely secure if you use a highly-random, one-time pad - which it sounds like YoshiN did.

The excryption cannot be better than that, and it also cannot be any less convienent to use. By some other means, you must share that key with the recipient, and both of you must protect the pad from prying eyes.

---

Yes, it can. If you are to decrypt such a thing, you must use the same pseudo-random number generator. It's called pseudo -random because it's output is totally predictable. So it isn't actually a one-time pad at all.

if you do something like this:

srand(process_key(key));
for (int j = 0; j < inp_size / sizeof(unsigned long); j++)
{
    output[j] = input[j] ^ rand();
}
  

you can xor the first 32 bits with the JPEG signature or whatever file type it would be, and then just seed the same random number generator with what you get, and just start decrypting from there, using the same algorithm.

For this to actually work, you need to have your own pseudo-random number generator, which must be kept completely secret, and thus be considered part of the key.

quote:

---

If the length of the key is less than the length of the file encrpted, then statistical analysis can lead to clues as to what the key is. For example, the vowels e & a are very common in English text. Knowing that it's a jpeg gives enough information to attack the encryption. You just concentrate on the header which has known byte values.
e.g. 0xFFD8 FFE0 xxxx 4A46 4946
So right off-the-bat if it's less than a 32bit key or less, it's cracked. If it was a 128bit key, it's now a 96bit key. And there's more header information. The next two bytes are the length of the FFE0 tag followed by "JFIF". Cracking the length will give a lot more information becase there are more tags in the header with fixed byte values. Odds are really good that the first byte is 0x00 so can assume we've cracked 40bits knowing that. The next byte is a mystery for now, but the next 4 bytes (another 32bits) come for free. Next, I would take the first two bytes of the key, and apply them to the next 32 bytes of the jpeg and look for the next tag, 0xFFDB. If this is uncovered, then I have a really good idea how long the key is - and it tells me the length of the 0xFFE0 tag, filling in the missing byte from either. You can continue this process on the rest of the header though it gets trickier from here on out, as the header format is less certain. There's about 1536 very deterministic bits, and you might be able to push it to 4864bits if you get a little lucky with some assumptions about the header layout.


I do not think blowfish is a sufficent level of encryption to encrypt a straight jpeg. A key length of about 8kbits to 12kbits is called for.

---

Blowfish and other modern symmetrical ciphers do not just encrypt eg. 128 bits, and then move on to the next 128 bits and do the exact same thing to them. If you don't belive me, download the source to blowfish and see for yourself.

There exists two known attacks on blowfish, both of them are only partial breaks, they will not retreive the plaintext. And none of them works on 16-round blowfish or more.

quote:

---

No wonder it's so easy to break the encryption of DSS's. They'd have to use poly-megabit keys to stand a chance.

---

Ok, I'm not sure what you mean with DSS, but symmetrical ciphers do not require poly-megabit keys to be secure at all.

edit: NOT fell out.

[edited by - mr BiCEPS on December 4, 2002 5:51:16 PM]

quote:

---

Original post by mr BiCEPS
Yes, it can. If you are to decrypt such a thing, you must use the same pseudo-random number generator. It''s called pseudo -random because it''s output is totally predictable. So it isn''t actually a one-time pad at all.

---

I wouldn''t consider a pseudo-random number to be "highly random". You need some non-deterministic generator, a giger-counter, noise-bits of the time-delay between key hits (as you suggest), etc... statistically verified for its randomness.

quote:

---

For this to actually work, you need to have your own pseudo-random number generator, which must be kept completely secret, and thus be considered part of the key.

---

That''s kinda risky though - it''s only secure until the algorithm is discovered.

With the one-time-pad “cipher”, the key needs to be as random as you can make it, and as long as the data you''re going to send. No pseudo-ness, no repetition, and you can never use that key again.

quote:

---

Blowfish and other modern symmetrical ciphers do not just encrypt eg. 128 bits, and then move on to the next 128 bits and do the exact same thing to them. If you don''t belive me, download the source to blowfish and see for yourself.

---

Certainly the key bit-requirement goes down as a more advanced cipher is used. An xor-pad is the worst-case scenario in terms of requisite key-length. Consider the reduction in difficulty when you have the first 1k of the original data file, though. You can work incrementally, drastically reducing the key-space every time you uncover a new byte. I have heard that blowfish is a really-good algorithm, I don’t doubt that. The problem is with the determinism in the source file. Now that I think about it, blowfish is certain to employ some scrambling technique (a rearrangement of the order of the data) – the question of its security for this application is how large the scramble-space is.

quote:

---

There exists two known attacks on blowfish, both of them are only partial breaks, they will not retreive the plaintext. And none of them works on 16-round blowfish or more.

---

If I had to guess, both assume no knowledge of the original file.
If I have a copy of the encrypted file and the original, how hard is it to figure out the key used? With a symmetric cipher, isn''t it easy?

quote:

---

Ok, I''m not sure what you mean with DSS, but symmetrical ciphers do not require poly-megabit keys to be secure at all.

---

DSS is Digital Satellite System - like Sony Mini-Dish or Dish Network, and now digital cable systems use similar encrypted mpeg2 transport streams. With a limitless supply of deterministic data, and potential access to the unencrypted output, I think it’s impossible to secure it using a symmetric cipher. And if you use an asymmetric cipher, the data’s not really protected, you just know the data is authentic. And now I see why they want the encryption built into TVs and speakers, which would only render "authenticated" sources.