0
$\begingroup$

how does 7z perfectly "restores" the missing random encryption key parts used to generate the different encrypted file?

I watched this in a loop. Every time the encrypted file contents differs, but as expected it always decrypts perfectly:
cat >test7z.sh; chmod +x test7z.sh; ./test7z.sh

#!/bin/bash

strData="abc123"; 
strFlBN="test3"; 
echo $strData >$strFlBN.txt; 
for((i=0;i<10;i++));do
  7z a -p$strData $strFlBN.7z $strFlBN.txt >/dev/null;
  xxd -p $strFlBN.7z |tr '[:lower:]' '[:upper:]' |sed 's@....@& @g'
  ls -l $strFlBN*;
  rm $strFlBN.txt
    
  7z x -p$strData $strFlBN.7z >/dev/null;
  if [[ "`cat $strFlBN.txt`" == "$strData" ]];then echo "=== OK $i ===";fi
  rm $strFlBN.7z
done

Related: 7zip : Why does encrypting the same file with AES-256 not give the same output?
But this is just about how the different output is generated.

$\endgroup$
6
  • 1
    $\begingroup$ I don't get it how it differs from the linked question and asnwers. $\endgroup$
    – kelalaka
    Commented Apr 23 at 16:54
  • $\begingroup$ I didnt understand there how the missing part is recovered to decrypt. I mean, if the encrypted differs, then it means something different happens everytime it is encrypted. so how this difference is perfectly restored by using the same password? that is out of my understanding. $\endgroup$ Commented Apr 23 at 17:13
  • $\begingroup$ In CBC mode, there can be two different parameters for the encryption; the Key and Nonce ( in some modes IV). The Nonce itself is invented to randomize encryption (the formal name is probabilistic encryption) under the same key. So, we can use the same key for a long time. The Nonce is usually prepended to the encrypted file since it is needed first and must not be secret. One must keep the key secret all the time! $\endgroup$
    – kelalaka
    Commented Apr 23 at 17:47
  • $\begingroup$ ohhhhh!!! :O. so part of the key (the random part auto generated that we never see in normal usage) is stored in the file! It is also called salt right? if it is just that, it answers my question, thx! :) $\endgroup$ Commented Apr 23 at 17:54
  • $\begingroup$ It is not exactly part of the key, they can be completely generated independently. You need both to decrypt correctly. IV/Nonce is not meant to be as secret as the Key. It is a public parameters that boost the encryption. $\endgroup$
    – kelalaka
    Commented Apr 23 at 18:01

2 Answers 2

2
$\begingroup$

First, it is worth clarifying that

encrypted file is different every time

is a feature, not a bug. If encrypting the same message $m$ (under the same key $k$) yielded the same ciphertext, an adversary could easily detect this. You might not think this is a big deal, but

No partial information about a message (except an upper bound on its length) may be efficiently computed, given a ciphertext.

is a typical security requirement in cryptography. Being able to infer that two messages are equal would be some partial information, which cryptographers would not view as being secure. In certain situations this can lead to actual leakage of the plaintext as well (see for example this), but the attack is a little complex.

Still, to be on the safe side, we assume the attacker has more power, in particular that they are able to query $m\mapsto E_k(m)$ for arbitrary $m$. In this model, you can do plaintext recovery for "deterministic" form of CBC (meaning with IV reuse). So to avoid that attack, we introduce (randomized, or non-repeating more generally) additional (non-message) quantities.

As for how IV's work, the main idea is to utilize a block cipher, which encrypts $E_k: \{0,1\}^n\to \{0,1\}^n$ for block size $n$. Something like $n = 128$ is common. There are many techniques to extend this to larger messages (see for example here). Cipher Block Chaining does the following

  1. split $m\in\{0,1\}^{k\times n}$ into $k$ message blocks $m_0,\dots,m_{k-1}\in\{0,1\}^n$ (if $m$ doesn't have this length, you can pad it with 0's to have this length. Sometimes more intelligent padding is preferrable though, generally padding which encodes the length $k$ into the message), then
  2. first choose $IV\gets\{0,1\}^{n}$, e.g. a random value, then
  3. encrypt the first block as $c_1 = E_k(m_0\oplus IV)$, and
  4. encrypts further blocks as $c_{i+1} = E_k(m_{i+1}\oplus c_i)$.

This is to say that the randomization $IV$ is used to ensure that even if you encrypt the same first message block $m_0$ twice, you're actually encrypting $IV_0\oplus m_0$, and $IV_1\oplus m_0$, which for different IVs will differ. This means when one naively decrypts you get back $IV\oplus m_0$, but the IV is transmitted as well, so can be removed, perfectly recovering $m_0$.

$\endgroup$
0
$\begingroup$

I don't know your background in math/cryptography but here is a "math" example that can help you understand the notion of "Every time the encrypted file contents differs, but as expected it always decrypts perfectly:"

(Warning: The following example is really different from what you are asking but it is just made to give you a general intuition)

The example is a "probabilistic version" of RSA, gotten from this paper.

$\textbf{KeyGen}:$

  1. Choose two large primes $p$ and $q$.
  2. Compute $n = p\cdot q$ and $\phi(n) = (p-1)(q-1)$, where $\phi(n)$ is the value of Euler's totient function of $n$.
  3. Choose an integer $e$ such that $1<e<\phi(n)$ and $gcd(\phi(n),e)=1$
  4. Compute $d$ such that $d\times e \equiv 1 \ mod \ \phi(n)$
  5. The public key is $(e,n)$, and the private key is $d$.

$\textbf{Encrypt:}$ To encrypt a message $m$, choose a random number $r$ in $0<r<n$, and compute: \begin{equation*}c = (c_1,c_2)=(m^{r+e}\ mod \ n,m^{re} \ mod \ n)\end{equation*}

$\textbf{Decrypt:}$ To decrypt a ciphertext $c$, compute: \begin{equation*} m = c_1^d\cdot c_2^{-d^2} \ mod \ n \end{equation*}

As you can see, the scheme above will produce for the same message $m$, different encryptions $c = (c_1,c_2)$ each time since it in the encryption step, it chooses a different random number each time.

However, someone possessing the private key $d$ can obtain $m$ by running the decryption algorithm and will always get the same value $m$ even if in the generation of $c$, different $r$ were used.

TLDR/Non-math response: Each time the encryption will use randomness in order to make the scheme "more secure" (e.g. if you know that the candidate "Alice" always encrypts to "123", that would not be safe in a electronic election). However, in the decryption, the randomness manages to "cancel out" and you always get the same message.

$\endgroup$
3
  • 1
    $\begingroup$ 7zip uses CBC mode not RSA. $\endgroup$
    – kelalaka
    Commented Apr 23 at 17:58
  • 1
    $\begingroup$ Interesting randomized RSA variant. This is tangential to your response, but I took a look at that paper and I have a hard time believing their security proof. Theorem 1 claims a reduction from IND-CPA security to the "RSA problem." They clearly do not mean the traditional RSA problem, which is an unforgeability game (given $m^e$, compute $m$), because the proof is written as if the RSA problem is some kind of distinguishing game. Also, the reduction algorithm only gets $(n,e,d)$ and nothing else from this "RSA problem" game, and has other values appearing from nowhere. Weird. $\endgroup$
    – Mikero
    Commented Apr 23 at 20:44
  • 1
    $\begingroup$ Actually, in their scheme $c_1^e / c_2 = m^{e^2}$, so the scheme publicly leaks a deterministic function of the plaintext. It cannot be CPA secure. (Of course it might still be a reasonable example to demonstrate randomized encryption, as in your answer here.) $\endgroup$
    – Mikero
    Commented Apr 23 at 20:52

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