5
$\begingroup$

I didn't find a direct solution for it. Can I modify encrypted data without accessing it?

If there is an example, I would appreciate it.

$\endgroup$
0
10
$\begingroup$

Can I modify encrypted data without accessing it? if there is an example appreciate it

  • If access means altering the data without decryption as an attacker then the answer is yes for messages without integrity.

    • Take OTP, execute bit flipping attack, done.

    • Take CTR mode, execute bit flipping attack, done.

    • Take CBC, execute bit flipping attack, done.

    • Similarly, take any stream cipher, modify one bit,

      Let $c_i = m_i \oplus x_i$ where $x_i$ is the $i$th bit form the stream cipher then

      $$c_i \oplus 1 = m_i \oplus x_i \oplus 1 = \bar m_i \oplus x_i$$ where the $\bar m_i$ is the bit complement of the bit $m_i$.

    Take CFB, execute bit flipping attack, done

    • and so on...

    These also called the ciphertext malleable.

    Note that the reason for this kind of attack is that they are at most CPA secure ( well OTP can have perfect secrecy with fixed length messages ) and that doesn't mean that the modifications are detectable. To mitigate this attack one needs at least integrity. The integrity may not be enough, since the attack in some cases reuse some part of the encryption and send it. Therefore, at least we need a Message Authentication Code (MAC), like HMAC, GMAC, CMAC, etc. With MACs, the attacker need also forge the message to execute such attacks on the encryption.

    Note that the bit flipping is the minimum attack. The attacker can modify more than one bit whenever it fits their aim.

  • If access means you want to operate on the encrypted data that the answer is yes for a very long time;

    • Textbook RSA is multiplicative so that you can multiply the ciphertext. Let $(n,e)$ be the public modulus with $d$ is the private exponent. Let the ciphertext $c = m^e \bmod n$ and $c' = 2^e \bmod n$ then $$c \cdot c' = m^e \cdot 2^e = (2m)^e \bmod n.$$

      One should keep track of the overflow that is when the modifications exceed the modulus the value will be rounded.

    • ElGamal can be both additive and multiplicative

    • Paillier encryption is additive where the multiplication of the ciphertext is the addition of the plaintext.

    • Goldwasser–Micali where multiplication of the ciphertext is the x-or of the plaintext.

    • 2DNF enables 1 multiplication and many additions.

      The above was before Gentry's Seminal work; Fully Homomorphic encryption that enables operation of arbitrary operations on the encrypted data. This was envisioned by On data banks and privacy homomorphisms. by Shamir et. al, immediately after RSA.

      The FHE simply having two homomorphic operations on the data so that arbitrary circuits can be computed;

      $$E(a) \boxplus E(b) =E(a \oplus b)$$ $$E(a) \boxtimes E(b) =E(a \times b)$$

      Note that for the plaintext and ciphertext operations different notation is used since the FHE schemes are not restricted to those. Some notable FHE libraries are;

    • HeLib, THFE, GSW, BGV, LTV, FHEW,....

    • There is a post about how these operations handled; Representing a function as FHE circuit

$\endgroup$
3
  • $\begingroup$ the linked post ("OTP can have perfect secrecy...") doesn't seem to address modifying the message on the fly, what am I missing? $\endgroup$ – ilkkachu Dec 17 '20 at 17:57
  • $\begingroup$ @ilkkachu the link for modification is on the bullet list. It is for the perfect secrecy. $\endgroup$ – kelalaka Dec 17 '20 at 18:12
  • $\begingroup$ Could the downvoter explain the reason! $\endgroup$ – kelalaka Dec 17 '20 at 20:32
8
$\begingroup$

If (and ONLY if) it was encrypted with a special "homomorphic" encryption scheme, then you can do the operations allowed by that scheme. Those are almost never used in practice currently (they're very slow, and an area of active research). This demo is quite good.

More commonly data is encrypted using an "Authenticated Encryption with Associated Data" (AEAD) system. AEADs will prevent ANY modification of the encrypted data.

There are also less secure (not IND-CCA) schemes that don't authenticate. Weak cryptography like that can have its ciphertext modified.

$\endgroup$
3
  • $\begingroup$ It's homorphic although I suspect you mistyped because it has some relation to the even more complicated term you've introduced me to!! $\endgroup$ – Modal Nest Dec 16 '20 at 22:31
  • 3
    $\begingroup$ @ModalNest actually, you're both wrong—the accepted term is homomorphic: three 'o's / no 'e's. $\endgroup$ – JamesTheAwesomeDude Dec 17 '20 at 0:21
  • $\begingroup$ If the encryption scheme is not standard one (like GCM, CCM, etc..), and also proven that it is not CCA secure, then I think we can modify the ciphertext. But in standard usage it is not possible. As mentioned by SAI Peregrinus a homomorphic function inherently support this. $\endgroup$ – SSA Dec 17 '20 at 6:32

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.