Ways of proving an encryption algorithm

Question

2.54/5 (4 votes)

See more:

I am writing an article on encryption.

As part of the article I am putting forward a custom encryption scheme that will serve as an example.

I'm not suggesting that it's a new or better encryption method or that anyone actually use it, but I know the onus is on the author of an algorithm to prove how secure it is, and I'd like to cover that in the article.

I don't actually want to prove the encryption, I just want to explain the steps that would be required - if only to show why it's way more effort to create your own encryption than using a pre-existing implementation.

I'd like to do this clearly, without the reader needing to know mathematical notations.

What I have tried:

I am already covering some of the basics that are used to attack an encryption - statistical analysis of symbol distribution, rendering hash tables, common-header attacks, plaintext-ciphertext collisions, that sort of thing.

I can show comparisons with the clear data to prove all the bytes have changed, and histogram analysis of the symbols in the encrypted file shows that every byte value (0 - 255) is used, and used about the same number of times, and that you can't reveal the key by trying to guess at the data and XORing that with the encrypted values (the algorithm uses an IV, block-cipher-chaining, padding, inversion and two separate key streams)

Can anyone think of more ways to attack a cipher?

Posted 15-May-16 11:48am

Simon Bridge

Updated 16-May-16 14:28pm

v2

Add a Solution

Comments

Sergey Alexandrovich Kryukov 15-May-16 18:52pm

It may cause some perplexity that you are writing an article on so incomplete topic, so you even ask for help. This is a normal thing, only, in the case you get the solution, who is going to be the author of that article?

Now, what fact do you want to proof? By proof, you should consider not "experimental" proof, but fully reliable theoretical one. If you want to proof that the encryption/decryption round-trip cycle gives you original data for each and every input data set, this is one thing. If you also want to proof that "breaking" of the encryption is not cryptographically feasible, this can be a very difficult problem, probably very difficult. And yet, this is important to prove, because otherwise the algorithm may be dangerously insecure. I think it's needless to explain how expensive the security breach can be.

Actually, I'm afraid your request would be totally useless without sharing all the detail of your algorithm.
But you need to get the idea how difficult is the proof problem. In particular, such fundamental hypothesis as existing of one-way function is not yet proven: https://en.wikipedia.org/wiki/One-way_function#Theoretical_implications_of_one-way_functions...

—SA

Simon Bridge 16-May-16 18:52pm

Hi Sergey,

You seem to have missed my point. Did you not read the question? or did I state it poorly?

I don't actually want to prove the algorithm, I just want to be able to explain to readers what would be involved in proving one, and as part of my due diligence, I thought I would be valuable to get some input from the community at large before launching with what I already know.

I'm not so naive as to believe that I could develop a cryptographically secure algorithm during my lunch hour, however I have built an example that covers the basics. The idea is to explain the basic internal workings of a cryptographic system that:
1) doesn't require a degree in pure mathematics to understand.
2) is coded clearly using modern coding practices, without any unsafe code or overuse of bitwise operators.
2) doesn't require you to try and work out the awful mess of code that I have seen in every published implementation I can find...(I think cryptographers - they actually write obfuscated code by hand)
3) introduces the concepts of hash-tables, cipher-block-chaining, initialization vectors, symmetrical transforms, etc in a way that can be understood by a developer.

As for the one-way-algorithm, why on earth would I reinvent the wheel there, when I can use any of the implementations already in .NET? I'm not proposing a new one-way algorithm, I use SHA-512 as the one-way-function. We could debate whether there is actually such a thing as a one way function, since computer systems are intrinsically deterministic and therefore cannot actually add entropy, but that's way off topic.
I was considering generating a challenge like this one:

http://web.mit.edu/kenta/www/three/aes/challenge.html

I know it's not proof, but there is some value to it.

Sergey Alexandrovich Kryukov 16-May-16 19:12pm

I'm sorry if I missed something. Please pay attention that the question title "How do I prove an encryption algorithm" is in the striking contradiction with "I don't actually want to prove the algorithm..." I'm not sure if you have any explanation of this contradiction even now.

Let me also note that your title mentions encryption. "Cryptographic algorithm" does not have to be "encryption". In your comment you mention SHA-512 and hash tables, which is not related to encryption.

As a result, it's quite hard to understand what you really trying to achieve. You last comment only makes thinks looking as everything is messed up. I really cannot understand what you are trying to discuss. As to you 1-2-2-3 items... (sigh...) — do be serious.

Your "As for the one-way-algorithm, why on earth would I reinvent the wheel there..?" is weird, to tell the least. How are you asking? How suggested anything you would need to do? You are the one who put forward the initial, you are the only one who know what you would do or would not.

And I think it's needless to explain that any help would be impossible without very basic thing: knowing your algorithm in all the detail.

—SA

Simon Bridge 17-May-16 0:26am

I have improved the question I hope since you posted this.

I am struggling a little to work out what you are trying to say, please bear with me:

You said:
"Please pay attention that the question title "How do I prove an encryption algorithm" is in the striking contradiction with "I don't actually want to prove the algorithm..." I'm not sure if you have any explanation of this contradiction even now."

My Explanation: (so you can be sure I have one)
I appreciate your point, and I have changed the title, however: I don't believe it's a contradiction to want to know how something is done, so you can explain it to someone else, without actually doing it. I explained I was writing an article, and that I wanted to know how 'something' (it doesn't matter what) was done so I could explain it in the article, so I asked the question "how do I do this thing" - there is no contradiction there.

You said: "Let me also note that your title mentions encryption. "Cryptographic algorithm" does not have to be "encryption". In your comment you mention SHA-512 and hash tables, which is not related to encryption."

I am going to assume you are not just splitting hairs on the definitions of "Encryption, Decryption and Cryptography" (which would be small and petty)

The common term here is "crypto" which comes from the Latin for "hidden" - here is a link to the Wikipedia page on "Cryptographic Hash Functions" Cryptographic Hash Functions - I don't take everything written on Wikipedia as gospel, but clearly hash functions are related to cryptography, encryption and decryption. In fact, all the hash implementations in .NET are in the System.Security.Cryptography namespace.

You said:
"As a result, it's quite hard to understand what you really trying to achieve. You last comment only makes thinks looking as everything is messed up. I really cannot understand what you are trying to discuss. As to you 1-2-2-3 items... (sigh...) — do be serious.

Your "As for the one-way-algorithm, why on earth would I reinvent the wheel there..?" is weird, to tell the least. How are you asking? How suggested anything you would need to do? You are the one who put forward the initial, you are the only one who know what you would do or would not."

I'm sorry I just can't work this statement out. What are "1-2-2-3 items", and why are you sighing? what was I not serious about? Are you actually trying to say that I am the one not making sense?
[EDIT]
I just realized I doubled up the 2 in my dot-points, that's what you meant by 1-2-2-3 items, but I was being serious: you don't think that clear, easy to read code is more valuable than code that makes sense to nothing but the compiler?

You posted: " particular, such fundamental hypothesis as existing of one-way function is not yet proven: https://en.wikipedia.org/wiki/One-way_function#Theoretical_implications_of_one-way_functions...
"
I think you were trying to say that despite the existence of lots of functions that are very difficult to invert, no one has yet proven that there is such a thing as a truly one way function. It's a bit like the debate on altruism. I agree, I think.

You said:
"
And I think it's needless to explain that any help would be impossible without very basic thing: knowing your algorithm in all the detail."

I don't think it is necessary for you to know the exact implementation of one specific algorithm, to explain the basic steps required to prove any algorithm. This is a simple case of abstraction that any developer should be able to grasp easily.

Sergey Alexandrovich Kryukov 17-May-16 8:38am

To be brief, I disagree with all your items, and the point about "cryptography" and "encryption" needs explanation, but I though you understand the point.

All notes like which "would be small and petty" are only good in certain context, but not when you are asking help on some subject. In this case, in the title you ask about encryption. This is something used to encrypt some data, which one can decrypt. With cryptographic hash, there is no decryption. Both things are parts of "cryptography". There is no a place for "small" here.

And, again, "I don't think it is necessary for you to know the exact implementation of one specific algorithm". Do you understand the situation? You ask a question, I answer. And you think I don't need to know what I'm asking? And disagree when I say that it's needed? Well, it means that you know the solution of your problem (which I don't even understand after all your words) better. Then why asking a question?

—SA

Simon Bridge 17-May-16 22:38pm

I explained why I asked the question - as part of my due diligence, in case someone had some ideas I had never thought of. I'm not so arrogant to believe I know everything about everything.

I actually don't want your help on this at all since you seem to lack sufficient written English to be able to understand what the question is or clearly explain your answer, and you immediately resort to snide smug remarks and can't support anything you say with references, facts or even a cogent argument.

I mean, really, as a reply to a comment I spent a very long time writing and trying to keep fair and neutral, your response is: "to be brief, I disagree with all your item" - so, you either don't even understand the concept of pluralisation, or you couldn't be bothered typing the "s" - get off your high horse.

If I could block you from answering or commenting on any question comment or article I submit, - I would.

Sergey Alexandrovich Kryukov 18-May-16 9:22am

Sorry for not understanding your "written English" and my typo. :-)
This is really bad, but what can I do if I already misspelled?

No need to be rude. You just lost patience. You apparently behave as if I attacked you. I wonder why.

I really don't understand what you want to achieve. And I hardly cannot understand 1) what do you mean by the proof (proof of what), and, more importantly 2) what do you want to explain to your readers without presenting the proof itself (but I'm not sure if this is what you want), and 3) what do you want from readers of your question without presenting us your algorithm. I simply cannot understand all that.

—SA

Simon Bridge 18-May-16 18:42pm

My point is that for anyone who wants to publish a symmetrical encryption algorithm, and have it generally accepted, there is an onus on the author of said algorithm to provide some proof, or reassurance, that information encrypted by this method will not be easily recovered without the key. This is never definite proof however.

There are common steps that are followed for any algorithm, regardless of its implementation, that measure the strength of the cipher. I know a few of these, but by no means do I have a complete understanding of the process. By asking this question I hoped to improve my knowledge and understanding and then be able to articulate that to my peers.

There really isn't room here to either post the code or describe in detail exactly how my simple example of a basic encryption scheme works, and because I want to know the process on a high level I find it would be counter-productive to do so.

For example (a poor one but the best I can think of right now) - if I wanted you to explain to me the road rules in your country, would you really need to know what make and model of car I was driving?

If you really want to know how it is implemented, I could email you the code or you could wait until the article comes out.

Apologies if I was rude before, and I appreciate that you put more effort into writing clearly, it does make a big difference. It's a personal bugbear of mine that so few people put effort into their written English. English is an ambiguous language at best, and when it is written down, you don't have the body language and tone of voice that makes up 70% of the communication, and you don't have the opportunity to say things differently or ask for a correction. So maybe I'm a bit twitchy on the subject and prone to impatience.

PS. You can always edit a comment after you posted it to remove typos if necessary. Just saying.

Sergey Alexandrovich Kryukov 18-May-16 19:21pm

No problem, forget it.

(But, by the way, your considerations about English I pretty interesting. I would agree with you mostly, but it's hard to impress me with its complexity. (I'm a real fan of good language, by the way.) It's considered as one of the simplest to learn (except, perhaps, pronunciation); and maybe this is one additional factor to its popularity. I don't know many languages, but I know a bit more about some. Probably some languages are infinitely more complicated, even when the native speakers naturally underestimate their complexity. Ambiguity of English is a wonderful expressive device. Look at just the great name of the famous book, "Avoid boring people" :-)

Now you are making clearer that your concern is about some measure of the strength of algorithm. You probably know that this issue is the hardest thing. Roughly speaking, it's possible that the algorithm looks hard to break, but nobody knows is some unknown backdoor solution exists. (By the way, this is why I mentioned one-way functions: there are candidates which most mathematicians consider as "very likely" to be real one-way ones, and even have serious arguments that no backdoor is possible, but still, cannot say there is a firm proof.) But "definitive proofs" do exist for many practically important statements, and only such cases can be really considered reliable.

No, I don't know any general steps "regardless of its implementation". I never heard of such things. And I would dare to predict: you won't find people who know such thing. If you prove me wrong, I'll be very impressed and thankful.

—SA

Simon Bridge 17-May-16 22:46pm

Also, you don't even understand how encryption works if you don't think hashes are involved in decryption. Yes, a hash is a one way function and by itself is neither encryption nor decryption, but when you use a hash to derive part of a symmetric key sequence, you use the same hash computation in the encryption pass as you do for the decryption pass. When you use a hash to sign a digest, you must regenerate the same hash to validate it.

Sergey Alexandrovich Kryukov 18-May-16 9:21am

I did not mean that, but right, I understand your point.
—SA

Garth J Lancaster 15-May-16 21:22pm

Thinking back to my days of working with Banks, Government agencies here in Aus, maybe someone like SANS may have resources that you can use Simon

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)