Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.

Close

#3 Proposal of critical and not-so-critical imrovements

open
nobody
None
5
2012-05-30
2012-05-30
one-time-man
No

Hello.

My proposed security model may be somewhat different from the one you adopted.
But even so, treat this as a friendly exchange of thoughts. All of my proposed improvements are aimed at decreasing the amount of information the adversary may extract from simple intercepts (more important) and various other attacks (less important).

1. "NEVER SUPPLY THE SERIAL NUMBER OF PAD YOU USED" RULE

The most important flaw I noticed in your protocol - is that you supply the "position where Alice started reading in her key file" in plaintext. This lets the adversary Eva obtain information on how much data was already transferred - just by looking at plaintext intercepts. By looking at current statistics of intercepts, Eva would be able to estimate for how long Alice and Bob have been using this one-time-pad. This lets Eva estimate the date when the physical exchange of one-time-pads happened - and therefore narrow the guess about real identities of Alice and Bob and the place where the physical exchange took place. There is an old, old principle of one-time-pad encryption - way older than World War I - "NEVER SUPPLY THE SERIAL NUMBER OF PAD YOU USED". Because it lets adversary extract a lot of inrofmation from traffic analysis. I saw one of the more recent restatements of this rule here, page 5: http://users.telenet.be/d.rijmenants/papers/one_time_pad.pdf

It is not necessary to cupply the position where Alice started reading in her key file. It's quite enough to supply the ID used to check if both have compatible key files (you use 4 bytes).

This is especially true if you make sure that after the generation the pad file haven't got two identical 4-byte-arrays. Then you can even search the position in pad file by the 4-byte ID supplied in the message.

2. REMOVE THE POSSIBILITY OF MESSAGE LENGTH ANALYSIS

You add the random amount of bits to the message. But this doesn't destroy the statistical distribution of message lengths. The length now is the sum of two random variable - one with original distribution of message lengths P1(n) and another with umiformly random distribution of lengths P2(n). The probability density function of the resulting random variable is just a convolution of densities P1 and P2. Adversary may easily reconstruct the original density distribution by deconvolving the observed density with the density P2 fixed in your protocol.

A better approach to removing the statistics of lenghts - is quantization. That is, you should add the message up to some preset length quantum. The best choice is the network packet length.

For example, if you chose quantum to be 512 bytes, then all messages shorter than 512 should be made 512-bytes-long by adding zeros. All messages between 512 and 1024 bytes in length whould be made 1024-bytes-long, et cetera. This would reduce the observable probability density distribution to few points (512, 1024, 1536 bytes and so on) which is much less information than the distributions available with steps of 1 byte, as you have now. Moreover, since it is Pidgin and mostly short message communication - almost all messages would be less than 512 bytes long and adversary would be able to extract exactly 0 (zero) bits of statistical information from intercepts.

There is even a method to do it (to add up to big packets) without the unnecessary depletion of pad. You should place some marker at the end of the original message, encrypt it with pad, and then just add NEWLY GENERATED random bits until the message is 512 bytes long. The prerequisite for such an algorithm is to have statistics of newly generated random bits to be exactly the same as the statistics of the bits in pad. This can be done by using the same PRNG that was used to generate the pad. Both Alice and Bob must have this PRNG.

3. IMMEIDIATE DESTRUCTION OF PAD

This is another very old rule of one-time pad encryption, which you are violating in your protocol. Pad MUST be completely and irreversibly destroyed by sender IMMEDIATELY AFTER the encryption and by recipient IMMEDIATELY AFTER the decryption.

There are many well-known situations in XX century history when violation of this rule has led to deadly serious consequences for everyone involved. I won't be telling these stories. It is quite obvious what types of attacks take advantage of undestructed pads. Armed people break into the door, and get all the Alice's pads she ever used. With these pads they are able to decrypt all the intercepts they PREVIOUSLY collected.

Therefore, you should wipe the bits you used from the pad. Sender should do it right after encryption, and recipient - right after decryption. Bits should be wiped securely. Because if you just write zeroes to the file, it would not completely reorient the magnetic domains on the hard drive - some orientation would remain. I.e. the magnetic moment vector of current bit would not redirect from completely downward (0) to completely upward (1) direction. The vector will have some small components along other axis that would show that it was downward before the last reorientation. Bruce Schneier recommends wiping a drive seven times. The first pass overwrites the drive with the bit pattern "00", the second with "11", and the next five with a randomly generated bit pattern. I agree with that.

What I propose is to overwrite the bits of pad right after they were used for encryption OR decryption.

The algorithm may be something like this:

----- for encryption:
1. Read the needed bits of the pad into RAM.
2. Encrypt the message.
3. Overwrite these bits of disk with zeroes, then with ones, then with random bits 5 times.
4. (ideally) Change the size of pad file so that no traces remain about the fact that pad was bigger before this encryption.

----- for decryption:
1. Read the needed for decryption.
2. Verify the ID used to check if both have compatible key files.
3. Decrypt the file and check the CRC hash.
4. Only if steps 2 and 3 were successful - erase the used bits of pad on disk. If steps 2 or 3 failed, then just do nothing.

4. MASKING THE SENDING TIMES

Adversary can extract information from knowing the moments when Alice of Bob are sending their messages. You can mask these moments by constantly sending the empty messages. Empty messages should be automatically rejected by recipient decryption algorithm - because the ID would not match. Even if ID will accidentally match, the CRC would not match.

Developing the automatical rejection of such messages will be also useful in cases when the adversary floods the channel with random idle messages. Recipients should be able to easily and automatically reject these messages without any inconvenience to their own messaging.

Empty messages should be sent at time moments governed by Poisson distribution. The parameter that sets average frequency of sending is called rate constant. Rate constant of Poisson should slowly fluctuate with time according to random walk process. I.e. every 5 seconds you should add (with 50% probability) or subtract (with 50% probability) a very small fixed value to the rate constant. This way it would deviate from its initial value quadratically with time, so you should just reset it to some random value (within set bounds) after EQUAL periods of time (20 minutes). The lower bound of rate constant should be several times faster than the normal human frequency of messaging.

This would effectively bury the statistics of real messages in the flow of empty messages.

All empty messages should be created with NEWLY GENERATED random bits, so that they would not deplete the pad (see section 2, last paragrah).

5. CONCLUSIONS

I understand that Sections 2 and 4 are not very critical for your project. But Section 1 and, especially, Section 3, are really critical for the whole concept of one-time-pad encryption as it was seen by previous generations, and fixes are fairly easy to implement.

Good luck.

Anonymous

SHA-256 hash of my real name is:
9E599BB3CFF38169A1644BE6B767AE73DF390CC6E32BBC7D7E6C87CF6A0566BC

Discussion