Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am a beginner in cryptography. I designed an password based encryption-decryption algorithm, which uses a random salt and a password to encrypt a message. I'm using SHA-512 for hashing, matrix operations for shuffling, bitwise XOR for mixing data and retrieving. The length of the salt and the ciphertext is 256 letters.

To my knowledge, the avalanche effect means that a slight change in any of the following:

  • cipher
  • password
  • salt

must change the output drastically.

In my implementation, if I change the salt or the cipher, I don't see any big changes in my output. However when there is a slight change in password, the output changes drastically.

So, my questions:

  • Is my understanding of the avalanche effect generally correct? If not, what should it be?
  • What can I do to best produce the avalanche effect in my (or any) cipher? should I reduce the salt length less and generate a smaller ciphertext to create an avalanche effect? If not, then how can I achieve this?
share|improve this question

migrated from stackoverflow.com Nov 30 '11 at 13:20

This question came from our site for professional and enthusiast programmers.

    
Out of curiosity, what are you using the hash for? – bdares Nov 28 '11 at 4:17
    
Welcome to Cryptography Stack Exchange. @Avinash, your question was migrated here because it is more on-topic here than on Stack Overflow. Please register your account here to be able to comment and accept an answer. – Paŭlo Ebermann Nov 30 '11 at 13:27
1  
If you want any constructive answers, you should show how your cipher currently works (in mathematical formulas, preferable). Then we can have a look to see how to improve it. – Paŭlo Ebermann Nov 30 '11 at 13:35
    
I've removed comments along the lines of "don't design your own cipher" - here on crypto it's perfectly acceptable to try, although you should understand it is all at your own risk of course :) I've also edited the question a little to focus more on the avalanche effect in the absence of the relevant cipher constructions. If anyone feels that is unnecessary, feel free to roll back and or improve on what I've done. – user46 Nov 30 '11 at 13:51
up vote 6 down vote accepted

Don't bother with changing the actual cipher algorithm. Read about Kerckhoffs's principle: you should only change things like the key and the IV, not the actual algorithm.

In order to test your avalanche, flip one bit in your key. That should change about half the bits in your output.

For cipher design, Applied Cryptography has already been suggested. As well as that you need to look at introducing Diffusion and Confusion into your algorithm. Also it is well worth while studying existing algorithms to see how they go about things. I started by designing my own simple Feistel cipher, that way a lot of the surrounding structure is already done for you. It also simplifies the design, in that the F function does not have to be invertible. That allows you a lot more flexibility in that area.

The warning about not using your own design for anything other than a learning exercise is a good one.

share|improve this answer
    
Thanx a lot.... – Avinash Nov 28 '11 at 14:28
    
Cypher/cipher is a UK/US thing. – rossum Dec 5 '11 at 12:19

I think it's awesome that you are building your own encryption-decryption algorithm. You will learn a lot about crypto that way. So far, everyone who builds a crypto encryption-decryption algorithm builds something horrifically flawed in one way or another -- very educational -- the first time.

terminology

If I understand your question correctly, you have a perfectly reasonable question about the avalanche effect, but most of the people on this site are so confused about your non-standard terminology that they can't even understand what you are asking.

If I understand your question correctly, you're building a encryption-decryption system that takes plaintext as input, stores data as encrypted files, and then later allows someone with the correct password to decrypt those stored files and recover decrypted plaintext bit-for-bit identical with the original plaintext input.

As you probably already know, a typical encryption program creates encrypted files that begin with an initialization vector (IV) that was freshly generated by a cryptographically secure random number generator when the encrypted file was created. The encryption program then chops up the input file into plaintext blocks of some fixed blocksize, uses some block cipher mode of operation in "encryption mode" to process each block (and the encryption key) through a block cipher to eventually end up with a encrypted block of the same blocksize, which is appended to the encrypted file. There's often some fiddly bits at the end related to "padding" and "message authentication".

Later the decryption program chops up the encrypted file into encrypted blocks of the same fixed blocksize, feeds each block (and the encryption key) through the block cipher using the same block cipher mode of operation in "decryption mode" to recover the plaintext block, and concatenates all the plaintext blocks together to recover a file bit-for-bit identical with the original plaintext file.

I'm using SHA-512 for hashing

OK, SHA-512 is an excellent hashing algorithm. If you're using this as part of the internal round function, or to generate subkeys from the main encryption key, it would work; it just seems unnecessarily complicated.

If you're using SHA-512 as a key derivation function (KDF) to generate the main encryption key from the password, many people would say it isn't complicated enough.

matrix operations for shuffling

That's kind of unusual, but that could work.

bitwise XOR for mixing data and retrieving.

Practically all modern encryption algorithms use lots of bitwise XOR operations. Many modern encryption algorithms are designed to use only modular additions, rotation with fixed rotation amounts, and XORs (ARX) in the inner loop (round iteration).

I'm pretty that an inner round function that uses only XOR, or only rotation, or only modular addition, will be fatally insecure no matter how many round iterations are used.

(I don't know enough to tell anything about the security of your particular combination of XOR and matrix operations).

The length of the salt and the ciphertext is 256 letters.

I assume you meant to say "The length of the initialization vector (IV) and each ciphertext block is 256 letters."

A "salt" is used in one-way cryptographic hashing -- see Can you help me understand what a cryptographic "salt" is? . An "IV" is used in two-way cryptography -- both encryption and decryption. Both "salt" and "IV" are freshly generated random values that are assumed to be publicly known, but the terminology hints that they will be used in different kinds of systems.

Pretty much everyone sets the length of the IV equal to the blocksize, so that's great.

My understanding is that practically all ciphers developed before the 1997 AES contest announcement used a block size of 64 bits (8 bytes) or less. Some cryptographers apparently thought that wasn't enough, but as far as I know everyone now seems to think a blocksize of 128 bits (16 bytes) is adequate.

A blocksize of 256 bytes would work; it just seems unnecessarily large.

the avalanche effect

When running each block of plaintext through the block cipher (in some encryption mode), the avalanche effect means that a single bit change in any of the following:

  • data in the plaintext block
  • password
  • IV

must change the output ciphertext block drastically (about half the bits).

When running each block of ciphertext through the block cipher (in some decryption mode), the avalanche effect means that a single bit change in any of the following:

  • ciphertext block
  • password
  • IV

must change the output "plaintext" block drastically (about half the bits).

In my implementation, if I change the salt or the cipher, I don't see any big changes in my output.

I'm guessing you meant to say one of two things:

  • "if I change a single bit near the beginning of the encrypted file (i.e., in the IV or in some early ciphertext block), I don't see any big changes towards the end of my output plaintext file."

This lack of change always happens when using the (secure) Cipher Block Chaining (CBC) or some other modes of operation. So it isn't necessarily a problem.

However, this can be a problem if you thought you were using using the (secure) Propagating Cipher Block Chaining (PCBC) mode, where this lack of change indicates a bug in implementation.

Also, this lack of change is the expected result when using the (insecure) Electronic Codebook (ECB) mode.

No matter what mode of operation you select, the decryption program should print out big scary warnings that the file failed the MAC authentication check whenever any single bit of the encrypted file is damaged.

  • "if I change a single bit in a single encrypted ciphertext block in an encrypted file, I don't see any big changes in the corresponding plaintext block in my output plaintext file."

Yes, this indicates a serious flaw -- the block cipher algorithm doesn't have a good avalanche effect. This is a sign that the algorithm does not have sufficient mixing. This generally means the system is vulnerable to chosen-ciphertext attack and similar attacks.

What can I do to best produce the avalanche effect in my (or any) cipher? should I reduce the salt length less and generate a smaller ciphertext to create an avalanche effect?

I assume you meant to ask "should I reduce the size of the IV and the blocksize to create an avalanche effect?"

That's generally not necessary.

The most common approaches to produce the avalanche effect are listed in the Wikipedia block cipher article:

I don't know any block cipher that produces a full avalanche after a single round. People designing block ciphers try to pick some number of rounds sufficient to make the block cipher resist all the standard cryptographic attacks, which is more than sufficient to produce a full avalanche.

People designing a block cipher typically pick one general block cipher design scheme, and make the block cipher program iterate it over and over the selected number of rounds. Some of the most popular general block cipher design schemes are:

  • substitution-permutation network
  • Feistel cipher
  • Lai-Massey cipher

Each of these requires some internal non-linear function. Early block ciphers often use some complicated internal function on each round that almost achieves avalanche in a single round. Modern ciphers often use a very simple, fast internal function each round (a few ARX functions) with just enough nonlinearity to eventually achieve avalanche after a large number of rounds.

share|improve this answer
    
Side note: The khazad cipher has full diffusion after a single round. I've made toys that do it too, it's certainly possible, and discovering ways to do so is fun. – Ella Rose May 16 at 23:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.