[Question][Lecture] Way to circumvent Kasiski's method

[Allgot]

Name: Jinseo Lee

Hello!

I do understand that today session's purpose is to let us know that how classical cryptography are, but I just want to discuss a new cryptography scheme for just fun, which can circumvent Kasiski's algorithm.

How about using infinite, not repetitive keys such as transcendental number (e.g., pi, e) with an offset?

For example, if we decide to use pi with offset 0, then the encryption process will look like:

plaintext: hello world keys: 31415 92653 ciphertext: kfpmt fqxqg

Since there is no explicit repetition between numbers, I think it is immune to Kasiski's method naturally. Also we have offsets, we can avoid brute-force attacks as well. (think about pi with 3,000 as the key)

Will there be any problem with this scheme, except the fact that we still have to exchange the key in advance?

[KihongHeo]

Jinseo, thanks for starting the discussion. That is an interesting approach to circumvent Kasiski's method.

What would be a drawback when your scheme is used in practice?

Everybody, any idea?

[m-spitfire]

Just to clarify, when we say $\pi$ with $k$ as offset we mean adding number $k$ to each digit of pi? @Allgot

[727yubin]

Calculation of these irrational numbers may be computationally expensive (more expensive than what we want), but in the case of pi Chudnovsky algorithm is O(n (lg n)^3) which should be OK...

One real-world drawback would be selecting a meaningful irrational number that can be "efficiently passed" as a key? For example, telling someone that the key is pi, e, sqrt(2), would be easy, but telling someone that the key is some weird irrational number that needs a formula for itself would be a drawback, I imagine.

[m-spitfire]

I think this comes to the same thing we discussed in the class: functions as keys. As Yubin also said, calculating those "functions" could take more resources than we need.

[Allgot]

@m-spitfire What I mean by offset was the start position of the key ;)

So, if the offset is 3 and the basis is pi, then the key should be

15926535...

[Allgot]

@727yubin I see, that could be one crucial drawback..!

[KalasLavas]

Unless offset is very large, I think it would be possible to simply bruteforce it.

I am not really sure how easy would it be to generate digits starting from large arbitrary position tho.

[KihongHeo]

Guys, sounds really good. Then, let us think about two things:

• Forget about irrational numbers (pi, e, etc). What happens if we use a random number?
• Forget about computation cost. Assume the generation is so efficient. Then, what happens? Is it then practical?

[KalasLavas]

I think it would be fine for one message if key is large enough, but for multiple messages encrypted with same key, character on nth position would be encrypted in same way. It would be possible to perform letter frequency analysis in this case.

[tanapthetimid]

• Forget about irrational numbers (pi, e, etc). What happens if we use a random number?

I think the issue with random number is we have no way of encoding and sending infinite length truly random numbers since it would require infinite data size. I think the point about irrational numbers is that they have a finite size formula which can be stored and transferred, that can generate (seemingly) patternless and non-repeating number of infinite precision.

[Allgot]

Okay, now I get that if computation(generation) is efficient without any restriction (for example requring a further information), then it is vulnerable to brute-force attack since the adversary(attacker) also can easily give it a try!

And that must be the reason why the modern cryptography schemes focus on devising such algorithm which cannot be solved without additional information(hints)...!

[Allgot]

I think it would be fine for one message if key is large enough, but for multiple messages encrypted with same key, character on nth position would be encrypted in same way. It would be possible to perform letter frequency analysis in this case.

Oh.. multiple messages with the same key...! Then the same method is again applicable :(

[KihongHeo]

Very nice. Encryption of multiple messages with the same key is a big problem as we discussed today. => Then why not use fresh keys for every new message? (assume key generation is so efficient)

[Allgot]

Actually I excluded the key exchange for the sake of simplicity and also because every classic methodologies have the same problem, but the main drawback of using fresh keys for new messages is that we required to exchange the key for every communication.

This can cause unnecessary overheads and also expand the space to attack.

[Re-st]

Very nice. Encryption of multiple messages with the same key is a big problem as we discussed today. => Then why not use fresh keys for every new message? (assume key generation is so efficient)

I think the freshness of keys can depend of the algorithm used to generate numbers. According to wikipedia there are some functions that are used to generate keys in MacOS. It seems that guessing the functions by the generated output are almost impossible in practical sense. (I have no confidence in if the generated keys are used for vigenere cipher, but maybe generating lots of numbers recursively and attaching them may make long enough pseudorandom number for a key in vingenere cipher) There are some easy functions, like ENIGMA, which were able to be solved by even the first computers.

[KihongHeo]

Great.

You folks have already introduced many things that will be covered during the next few lectures (e.g., pseudorandom, block cipher, etc.). Looking forward to more discussion tomorrow.