0
$\begingroup$

Why I care: I want to implement some secure sessions for communicating over internet and since I am a complete amateur in this and don't want to spend a lot of time learning about cryptography or about specific libraries (as I am doing this only for fun), I want to have minimal preparation from programming side. From mathematical side, I am good at it, so spending extra time thinking (as opposed to googling and reading documentations) is not a problem.

My conjecture/question: The interesting part comes when I realised that having only one asymmetric cipher (block or stream), call it $X$, is enough for all basic cryptographic needs. In other words, all other basic cryptographic categories (others types of ciphers, hash functions and signatures, no others) can be reduced to this algorithm; you could make a hashing algorithm using only $X$, and a signing algorithm using only $X$. This would mean that combining algorithms like RSA+ChaCha+Poly1305 or whatever not is obsolete when speed is irrelevant. I don't aim higher than internet communication. FHE and similar is out of scope. Then, isn't it enough to implement only $X$ when time and speed is not relevant? Why do people then invent all these algorithms, other then speed reasons?

My proof:

Turning a stream cipher into a block cipher:

Just process a stream of fixed length with a stream cipher and call it a block cipher.

Turning a block cipher that acts on a set of arbitrary size to a block cipher that acts on a set of size of a power of $2$.

Let $A$ be the set $\{1,\dots,N\}$. Let $X$ be a block cipher with two functions $E$ and $D$ (encryption and decryption function) that map elements from $A$ to $A$. Let $2^k$ be the greatest power of $2$ less or equal to $N$. Let $B$ be the set $\{1,\dots,2^k\}$. Let $x$ be a number from $A$. The sequence $x,E(x),E(E(x)),...$ is assumed to be random and uniformly distributed on the set $A$ (also a looong cycle, since this is an asymmetric cipher), which yields that a number from $B$ occurs, in average, after every $\frac{|B|}{|A|}$ elements. We can take the first such occurence as the image of the new function $E'$ that now maps from $B$ to $B$. Define $D'$ to be the inverse of $E'$. The pair $(E',D')$ is a new block cipher that acts on a set of size $2^k$, in other words on blocks of $k$ bits. It is as safe as $X$ because if we can break this crack this cipher then it means we can find the outcome of the original cipher applied a few times, say $m$ times. Then we can just reapply the cipher $m-1$ more times on an encrypted message and then use this crack to undo it $m$ times. Since $m$ is expected to be less than $k$, this is feasable.

Turning a block cipher of size $2^k$ into a stream cipher.

Let's assume $k$ is even (it's simpler to explain the concept). Technically, I am only ecnrypting and decrypting a message of arbitrary size, which is not exactly a stream cipher. Firstly, expand the message to have a length that is a multiple of $\frac{k}{2}$. Think of this message as of a sequence of blocks of size $\frac{k}{2}$. We can encrpyt in-place pairs of these blocks: first and second block together, then second and third, and so on... until the end. Up until now, this resembles a stream cipher. We can optionally add some random beginning to the message if the message was too short originally. We can also, optionally, reverse the order of these blocks and apply the same encrypting sequence. Now, we can either decrypt the whole message or nothing: If we lose a part of it, we can't decrypt anything. Just like the initial block cipher is meant to behave. This is as safe as the original block cipher because if we can crack the whole message, then we can re-run the encryption and produce all of the inter-products, including the decryption of the last 2 blocks that the encryptor encrypted.

Turning a block cipher into a hash function.

I edited this part, because the first idea was wrong...
Create two key pairs and throw the private keys away, and hardcode the public keys in the algorithm. Just like int the previous part, prepare the blocks. Now encrypt the first $k$ bits in-place first with one key, then with the other, remove $l<<k$, $l|k$ "random" (pseudo-random, seeded by some simple hash of the message) bits from this produced $k$ bits and concatenate the rest of the bits. Continue doing this until there is only $k$ bits left, then call it the strong hash. This is as safe as the cipher, because if we suppose we found another message with the same output, then while we are rehashing both of them at the same time, at some moment we will produce the same $k-l$ bits (after removing random $l$ bits). Here is why it is hard: Those $k-l$ bits can be filled to $k$ bits in at most $2^l\binom{k}{l}$ ways (which we can bound to a small number), then most of them will not produce the same $k-l$ bits which helps in bounding it, then even if we could decrypt another combination of $k$ bits (which maybe could be possible because they resemble the original $k$ bits), the decrypted $k$ bits would have to be decrypted again, but now they don't resemble the original $k$ bits, so we would basically have to crack the cipher at this point. We use two different cipher (two different public keys) because we want to eliminate any malleability.

Turning a block cipher into a signature function.

We can first calculate the hash of the message and then encrypt the hash. This is obviously safe, as this is how current algorithms work.

I apologize for using different tags, I just didn't know what to use.

$\endgroup$
6
  • 3
    $\begingroup$ Commonly asymmetric primitives also have an overhead when it comes to encryption, does that count? Furthermore, RSA / OAEP is dependent on a full domain hash. Finally, RSA requires very high key sizes to go over 128 bit security and it is not protected against quantum computers. $\endgroup$
    – Maarten Bodewes
    May 17 at 8:15
  • $\begingroup$ @MaartenBodewes I had no idea about these things. When I mentioned "asymmetric block ciphers", I assumed a pair of functions (E,D) whose domain and co-domain are the same set. You could think of E and D as of the public and the private key. If it is implemented using some other primitives, I don't care. I just wanted to reduce everything else to X, so I can learn how to use only, say, RSA and then play with my code instead of reading more about the library. I don't know what overhead and full domain hash are. RSA needing big keys is not a big concern to me, some other algorithms don't, perhaps $\endgroup$
    – donaastor
    May 17 at 8:20
  • $\begingroup$ "all needs" is definitely aiming too high, since it includes more than just the basic things. For example, an arbitrary asymmetric encryption scheme can not be used to achieve fully homomorphic encryption. $\endgroup$
    – tylo
    May 17 at 9:27
  • $\begingroup$ @tylo ok, yeah, that's true. I know about FHE, I took an interest in it, I still forgot about it, I will now edit to be more specific about what I meant. $\endgroup$
    – donaastor
    May 17 at 10:01
  • 1
    $\begingroup$ To be honest, answering this question seems to require an explanation of almost all of cryptography, which is a bit broad for a question. $\endgroup$
    – Maarten Bodewes
    May 17 at 18:10

2 Answers 2

2
$\begingroup$

Beware that beside RSA, we don't know many "asymmetric block ciphers" per the question's definition (essentially trapdoor permutations), thus building over this won't allow substitution with something faster, or resistance to hypothetical Cryptographically Relevant Quantum Computers.

In anything applied even at experimental scale, there's always some limit to how far speed is irrelevant can hold. The approach suggested will hit that wall, I believe for two things

  • Textbook RSA decryption and signature is several decimal orders of magnitude slower than symmetric crypto, thus you'll end up needing hybrid cryptography for passable speed.
  • RSA key generation is again some decimal orders of magnitude slower than RSA itself, and key establishment with forward security (a standard feature of modern SSL/TLS that many would say has become basic) using RSA (or built on top of some asymmetric encryption scheme) seems to require key generation at each session.

Finally, the RSA trapdoor permutation is far from ideal. It has fixed points ${0,1,n-1}$, and more generally a multiplicative property. Thinking of it as an asymmetric substitute to a large block cipher is a recipe to disaster, tried and tested during the first decades of RSA, and counting, as chronicled at some point by Dan Boneh. Solutions abound, but at least those common or with a proof of security assume a hashe. Thus "you could make a hashing algorithm using only" (the RSA trapdoor), while possible, is adventurous beside slow.

$\endgroup$
1
$\begingroup$

For the same key sizes, symmetric encryption protocols are safer than asymmetric protocols.

Informally, the cryptanalysis algorithms used to decipher RSA try to identify the prime values used to create a value N, while (I may very well be wrong here) algorithms used to break symmetric encryption schemes are based on brute force identification of the plaintext message, based on a known-plaintext attack, and in the detection of some patterns in the bit distribution of ciphertext.

The difference in the security of these algorithms is such that an AES encryption with 128 bits of key size is about as hard to decipher as a RSA key with 2048 bits of key size.

Ultimately, in my opinion,it all comes down to performance. If you plan on using huge RSA keys then you wouldn't need any other encryption schemes; but you'd be paying a huge price in bandwidth use and latency.

This is all assuming you plan on generating a new key for each session. Otherwise, if someone would eventually identify your secret key, then all info you've sent (and will send) are compromised.

You could counter that by having HUGE key sizes. Again, it's a matter of performance.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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