Score:0

Does this encryption scheme have any major vulnerabilities?

br flag

Recently I asked a question of whether there is any cryptosystem that satisfies a number of properties (read the properties). Continuing to the promise I gave there, this is my attempt to construct it. I expect this attempt to satisfy all of the properties, although maybe not provably. The thing that I'm asking here is whether or not there are some easily noticeable vulnerabilities in it.

Modified RSA-OAEP

I keep the confidence for this one from seeing similar modifications that more experienced people/users give, for example in post given by poncho and some comments to it, a user who has also appeared in the comments of my first question. (https://crypto.stackexchange.com/questions/204)

Let $2^{k-1}<N<2^k$ be our modulus and $e$ and $d$ the public and private exponents. I will explain the encryption. First we pad the message like in OAEP, but a little different. We pad our (fixed-length) secret to $k$ bits using random bits until the end, and apply OAEP transformation to it: We xor the first $(k-k_0)$ bits using pseudo-random bits seeded by last $k_0$ bits, then hash it and xor the hash with the last $k_0$ bits. If we got a number greater or equal to $N$, we try again. Now we raise the number to the power $e$ modulo $N$. If we got a number greater or equal to $2^{k-1}$, we try again. The probability of success is $\frac{N}{2^k}\frac{2^{k-1}}{N}=\frac{1}{2}$, it is constant. Every time we try again we generate new random padding bits.

This should allow any person to decrypt the encrypted message with their own private key and still use the result, not knowing if it is really decrypted or just garbage noise. This is all assuming that the initial secret message is also a random stream of bits, but in my examples of usage it will be.

The Attempt

Every participant have their private and public keys and a unique public ID number (which can be set to equal the public key). I will again explain only the encryption, decryption should be obvious as before.

Say we have to encrypt message $m$, $s$ bits long. Agree on an instance of HMAC hashing algorithm with key-length of $a$ bits and $b$ bits of output. Agree on helping block size, equaling $c$ in bits. Generate two random blocks of bits, with the length of the first one being $a$ and length of the second one being $c$ bits. Call these blocks $B1$ and $B2$. Encrypt $B1||B2$ using the modified RSA-OAEP. Append $r$, random $b$ bits, to the end of $m$. Apply OAEP on $m||r$, but using HMAC keyed by $B1$: We xor $m$ with pseudo-random stream of bits seeded by $r$, then hash the masked $m$ using HMAC and xoring $r$ with that hash. The output of this OAEP is $s+b$, call that block $P$. Pad $P$ with as few random bits as possible so that the length is a multiple of $c$. Call that new padded block $P'$ and the length of the padded string $s'$. Now $P'$ has $\frac{s+b+s'}{c}$ blocks. Add these blocks together modulo $2^c$, call the sum $S$. Let $S'=s'-S-B2\;(\text{mod }2^c)$. Append $S'$ to $P'$. The receiver is now able to easily detect where the ciphertext ends, knowing the beginning, by adding blocks of $c$ bits together, starting from the number $B2$. The receiver will know to stop when the current sum is between $0$ and $c-1$. If $c$ is large enough, the probability that the receiver will stop at a wrong time will drop to something negligible.

The sender should append the receiver's ID to the original message and then sign all that with RSA-PSS, for example. Then append the signature to the message, after the ID. Now that should be defined to be $m$. From here, we proceed to the protocol from the previous paragraph. By doing this, the receiver is unable to unpack and repack the message and send to someone else and pretend that the original sender sent the same message to someone else.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.