The flaw: or what is an enterprising blackhat/NSA type to do, now?

[cmacq2]

Hi. I just read about your algorithm and since I have some time to kill I thought I'd try and give it some thought. I am not exactly a cryptographer, more of a noob with an outside fascination for the Maths wizardry (as in: any sufficiently advanced Math is like abracadabra to me) and related interests.

I base my understanding not on your source code (there's a lot of it to digest, and with crypto details tend to matter and warrant close scrutiny), but on your high level algorithm design/overview as posted on your blog.

Since you claimed a breakthrough in paradigm, my curiosity peaked. Curiosity led to my mind picking up, and I think I might just have spotted a bit of a flaw in your algorithm. Again, note I'm no expert so please: gently and graciously correct me where I am wrong.

With that aside, let me paint you a scene. Imagine you are Bob. Imagine you want to store photographs (of cats, naturally) confidentially on a server hosted by Alice. Imagine Bob and Alice use your crypto in a scheme like this: Bob encrypts his cat picture, and submits it to Alice.

Imagine Eve. Eve runs a malicious scheme to subvert the crypto: she managed to redirect traffic from Bob to her servers before passing it on to Alice, and vice versa: a classic Man In the Middle.

Now, nothing to worry yet: Bob's pictures are encrypted so if they aren't cats, Eve still doesn't know she's hit paydirt. Still, Eve is crafty. She notices something about your algorithm:

Given the key body length(L) is a power of 2, and M is an integer to tell us where we are in the "key > body":

We just take the byte at position M of the key body, we XOR that byte with the byte to be encrypted(X). We increase the byte at position M and "jump to" (M+X)%L

Eve notices this:

• Let key be the array of bytes of length L, M the index into that array, and X an array of bytes which constitutes the message to be encrypted. Let C be the encrypted result (an array of bytes constituting the cypher text)
• The first byte of C, C[0] is just this: C[0] = key[M] XOR X[0].

Eve thinks aha: if I know X[0], then I know key[M]. But, I don't know key[M]. Except... Hang on: files are not random collections of bytes. They have structure. PNG, JPEG, GIF, you name it all files have a clear an marked structure, and in particular most of them have a structure starting at the beginning to tell whatever thing reads those files what's inside.

So Eve can recover the first byte by induction: assume that the file format being uploaded is limited to one of three options: JPEG, GIF, PNG and over time collect many copies of encrypted upload to prove/disprove the hypothesis. (Proving it is a matter of validation by checking the assumptions against statistics: how often do the structures 'recovered' match exactly with the hypothesis?)

In particular, if Eve can trick someone into uploading a known plaintext she can trivially recover the first byte. In particular, if Eve can craft a scenario in which Bob is forced to upload a known file, Eve can simply replay the algorithm to recover his key and then decrypt all Bob's pictures! This scenario is not that outrageous/ludicrous: she is the (wo)man in the middle, so she can 'lie' to Bob about the state of Alice's server.

Your switching/jumping steps don't matter. They are clever enough, but they are fully predictable if you know how the algorithm works and you have a known plaintext to work with (so the X bytes are all known):

• At that point the key must be updated: key[0] ++, M = (M + X[0]) % L.
• Well, Eve thinks I can cook up my own malicious implementation which takes a known plaintext and its corresponding cyphertext, do this funky dance routine and recover the key and output that.

Known plaintext attacks are not just a theoretical concern. They are, in fact one of the most important things to defend against because nearly everything you want to encrypt has a known structure: network protocols, cryptographic signatures for checking message integrity and authentication, file archives, files like ODF documents (just a fancy ZIP file with lots of known XML and CSS).

Because your crypto algorithm uses the key directly in this way, essentially by XOR'ing with the key, you 'leak' the key into the cypher text: making it possible for all the evil Eve's of this world to recover them with enough persistence.

In particular, to this noob it seems that there are, still, a few easily discerned cardinal rules of good crypto:

• If you use symmetrical key crypto (like this scheme), you can only use the key once, then you have to throw it away. If you don't, then known plaintext attacks, statistical analysis and WW II era math will crack your key. That is because if you use the same key repeatedly, fundamentally there is an inverse operation that extracts the key from the cypher text (as described above) because the key leaks into it. If you fail to throw away your key, you have no forward secrecy and therefore effectively no cryptographic protection anymore when old messages are decrypted because it means the key is effectively recovered. As a result symmetric key crypto is... not very practical, even if it is the only provably secure (not just cryptographically secure) method. The correct method is known as the One Time Pad.
• If you use asymmetrical crypto (private + public key): do not, ever, share your private key.
• In fact, do not use your private key. Instead: derive a 'session' key pair (private + public) from your private key and present those: that's like throwing away your key afterwards in symmetrical key crypto. If you do this you get forward secrecy: when an old message is broken, they may have your old 'session' key but you stopped using those any more long since, and hence your keys are still safe and so is your crypto. This is, at least to this noob, essentially like an "One Time Pad for asymmetrical key crypto".

[ikizir]

Thank you cmacq2,

This is exactly what I wanted when I begun to develop everything transparently here in GitHub. I want to see the flaws of the algorithm. But the one you mentioned, is not a concern. The algorithm protects against "known plaintext attack" by design. Here is how:

When we create a key, we create it with its original 8 byte "Salt(or iv or nonce, call it as you wish)" value embedded on it. This salt value is only and only used to encrypt other salt values. When a packet is about to be transmitted; a new 8 byte salt value is created providing any byte of new salt value is not equal to the original salt value at the same position(Because we will xor them) The packet is encrypted with that new salt value&key body combination. We XOR every byte of new salt value with every byte of the original salt value at the same position. And we write this "encrypted" salt value to packet header. Now, we are sure: Two random number xored with each other: Impossible to gather any meaningful information from this.

We transmit our packet to receiver. The receiver first xors every byte of the encrypted salt value with every byte at the same position of key's original salt value and obtains the salt value to be used to decrypt the data. Then using the actual salt value and key body, decrypts the data.

As long as, the attacker can't obtain the plaintext AND the salt value; known plaintext attacks are useless. Because, every time, a new packet generated, every time, a completely different path will be followed and a completely different output will be obtained. The information gathered by a known plaintext in one packet, are meaningless for other packets, since, at least 2^64 random data is embedded on it!(more than 2^64 but i just put the salt value on table) I hope, I could explain why "known plaintext attack" is useless. I am still developing the algorithm; there is a little bug(not exactly an unnecessary issue); but, you can confirm what I tell you if you examine the actual code.

[Fbonazzi]

Your assumption that an attacker cannot know plaintext and salt is completely unjustified: the salt is not secret, and by design. Remember you are sending the salt over the network. So an attacker will know the salt. And they will be able to recover the key if they know the plaintext.

[ikizir]

Fibonazzi,

Can you please explain me how and why the salt is not secret? The original salt is part of the key. If you know it, you know the key. The salt of every packet is tranmitted with the packet in "xored form" with the original salt.

[Fbonazzi]

Notice that it's really difficult to follow your logic without a clear algorithm specification to explain the steps. The confusion also helps preventing you from seeing the issues with your algorithm. Please write out a clear and detailed step-by-step explanation of the algorithm (you should have done it before writing a single line of code).

It is not clear at all if the key and salt are related. I will try to understand by asking a few questions. Your encryption function takes 5 parameters:

1. uint8_t *K
2. uint8_t *Salt
3. uint32_t KeyCheckSum
4. size_t InOutDataLen
5. uint8_t *InOutBuf My understanding:
6. K is the key.
7. Salt is the salt.
8. KeyCheckSum is deterministically derived from the key (and as such you could even derive it inside of the encryption function without passing it as a parameter).
9. InOutDataLen is the plaintext length.
10. InOutBuf is the plaintext (which apparently is modified in place by the function - probably a bad idea)

So you are feeding 3 pieces of information to your function:

1. Information about the key (actual key and checksum)
2. Information about the plaintext (actual text and length)
3. The salt

The decryption function takes the same 5 parameters, and as such it will need the same 3 pieces of information: key, salt and ciphertext.

The key distribution problem is inherent to symmetric encryption and as such is out of scope of an encryption algorithm. The ciphertext is safely transmitted over the public network, since it's encrypted.

Now my question is: how does Alice communicate the salt to Bob?

If the salt must be communicated through a separate, secure communication medium, it is not a salt, but it is a "secondary" key. If it is a secondary key then you might as well use a single key. If the salt is transmitted over the same public network as the ciphertext, then it is public information, and any attacker will be able to freely intercept it.

[cmacq2]

The problem is, as I see it:

If the salt is unique for each encrypt() operation, then you need to know it in order to decrypt(), so it must be embedded in the cypher text, so it can be recovered (trivially). So the salt doesn't protect you against known plain text attacks, after all.

If the salt is linked to the key (i.e. lifetime of salt == lifetime of key) then it is functionally, part of the key. So there would be no difference between a 128 byte key + 8 byte salt and a 136 byte key.

What 'salts' are for is to spike cypher texts so that if you have many encrypted messages, a single successful decryption of a given byte string does not mean you can stuff the result in a dictionary and then speed up subsequent decryption of the same byte string using a dictionary look up. It is useful to prevent dictionary/rainbow style attacks against a dump of a password database. It's not useful to prevent decryption of a password if you already know the password (plain text attack) because you are no longer after the password but after the key used to encrypt the password (so as to decrypt all the other passwords, using the cracked key).

[ikizir]

You "crypto guys"; you really must have some "issues" with the reality. What I tell you is a very simple fact. Every "sane" developer will understand what I wrote above. But you still insist to speak meaningless wonkie junkie humpie "I know a lot you know nothing; Here are the definitions of cryptology Gods" shit. I don't consider your "cryptology rules" as serious. I am telling you my methods. I am asking you a simple question. You respond me like little children: "You can't play like that. We define the rules". Sorry, I define the rules here. If you don't like it, go somewhere else to play. Or if you want to play: Here are my rules. Explain me how will you obtain the salt given the information I've provided. Or I won't loose my precious time with you anymore.

[Fbonazzi]

...are you serious? wow.

Anyway, I really did not understand. Can you clarify the answer to this question: how does Alice communicate the salt to Bob?

[ikizir]

Anyway, I really did not understand. Can you clarify the answer to this question: how does Alice communicate the salt to Bob?

You see: You have "issues". I wrote you twice! Twice! In readme too! Three times! You just don't read what I wrote above. In this page.

[cmacq2]

Maybe he meant, salt is a nonce prepended to the plaintext ... and that because of the jumping the key is now protected against a plaintext attack because it's not 100% plaintext before encryption, and after decryption the nonce is simply stripped to recover the plaintext intact?

[cmacq2]

@ikizir maybe, it's a "RTFM" situation but I got my understanding of your algorithm from your blog post

[ikizir]

@cmacq2 This is not problem. Thank you for being honest.

[gipi]

Hi @ikizir , could you show a piece of code that shows the use of your algorithm with several packets?

In the code as is I don't see example of it, the salt is used only once.

[Fbonazzi]

Look, I'm only trying to understand.

When you wrote

When we create a key, we create it with its original 8 byte "Salt(or iv or nonce, call it as you wish)" value embedded on it.

Does it mean that the original Salt is just a part of the key? If it's part of the key, it's not a salt.

A new 8 byte salt value is created providing any byte of new salt value is not equal to the original salt value at the same position [...] We XOR every byte of new salt value with every byte of the original salt value at the same position. And we write this "encrypted" salt value to packet header. The packet is encrypted with that new salt value&key body combination.

So now we take the packet header, XOR it with the message, then XOR the result with the plaintext and recover the key?

[ikizir]

@gipi, once I stabilize the code, I will write all those. And I will even give the code I am using for my own software. But actually, we are still trying to test it and improve it. Today, the first time, two "professional looking" guys wrote to my private e-mail and offered help. They look serious because, one, from India, is talking about working to prevent side channel attacks, which I know practically nothing about. The other, from Russia, he will help me to apply some tests. A bit of patience.

[ikizir]

@Fbonazzi I will tell you everything as even a "cryptology expert" can understand: ABCDEFGH ---> This is the original salt value embedded in the key. It is ONLY used to be XORed with salt values to be transmitted.

Every time we want to encrypt a data, we create a new Salt value. Let's say, 12345678 We encrypt the data with Key + Salt[12345678] Now we have encrypted data How we will secretly transmit our Salt value to receiver?

We XOR our Original salt value ABCDEFGH with actual salt value 12345678 and we obtain [xxxxxxxx] We transmit xxxxxxxx+Encrypted data

The receiver has also the key; ABCDEFGH is part of the key. He doesn't need any other info., He first XOR ABCDEFGH with xxxxxxxx and obtains actual salt value: 12345678 Then, he decrypts the data with Key + Salt[12345678]

Is it OK?

[Fbonazzi]

Thanks for the explanation, I understood almost everything.

We encrypt the data with Key + Salt[12345678]

What does Salt[12345678] mean? What kind of operation is it? What does Key + (...) mean? Is it a binary string concatenation?

[ikizir]

OK Fibonazzi. I won't loose time with you.

[mastercoms]

@ikizir Please don't do this. Fbonazzi and many others just want to understand, and you owe that explanation to them, or at least link to an explanation that answers their specific questions. You say this is a transparent crypto process, so please, be responsible for being transparent to your community and making sure everyone knows what your crypto is. This hostile behavior only makes this crypto algorithm opaque, and will severely diminish community support and reviewing of your code and your algorithm.

[ikizir]

I gave detailed answers of their questions. Very clear and net answers. If you insist on the same question, Anyone who doesn't understand what I wrote above "SHOULD NEVER TRY TO USE THIS ALGORITHM". Because, he is not able to understand the very basic principles of programming or logic. Simple. This issue is closed.

[stylemistake]

@Fbonazzi according to his README, salt is public (and random), but it's hidden behind a XOR with the salt inside the key. @ikizir Was that hard to explain? Information should be available in many ways (including the issue section), especially because your README is huge, unstructured, and in general hard to follow.

[ghost]

[mastercoms]

@stylemistake Thank you!

[AFulgens]

@stylemistake so... the salt is functionally part of the key

[stylemistake]

@AFulgens well, yes, salt inside the key is the key. But there's also a salt in the ciphertext, which is not a part of the key, and is indeed a salt.