Skip to main content
Engineering LibreTexts

2.3: How to Demonstrate Insecurity with Attacks

  • Page ID
    7322
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    How to Demonstrate Insecurity with Attacks

    We always define security with respect to two libraries - or, if you like, two library templates that describe how to insert the algorithms of a cryptographic scheme into two libraries. If the two libraries that you get (after filling in the specifics of a particular scheme) are interchangeable, then we say that the scheme satisfies the security property. If we want to show that some scheme is insecure, we have to demonstrate just one calling program that behaves differently in the presence of those two libraries.

    Let’s demonstrate this process with the following encryption scheme, which is like one-time pad but uses bitwise-AND instead of XOR:

    Construction \(2.8\)
    截屏2023-03-04 16.28.35.png

    I haven’t shown the Dec algorithm, because in fact there is no way to write one that satisfies the correctness requirement. But let’s pretend we haven’t noticed that yet, and ask whether this encryption scheme satisfies the two security properties defined previously.

    Claim \(2.9 \quad\)

    Construction \(2.8\) does not have one-time uniform ciphertexts (Definition 2.5).

    Proof

    To see whether Construction \(2.8\) satisfies uniform one-time ciphertexts, we have to plug in its algorithms into the two libraries of Definition \(2.5\) and see whether the resulting libraries are interchangeable. We’re considering the following two libraries:

    截屏2023-03-04 16.29.03.png

    To show that these two libraries are not interchangeable, we need to write a calling program that behaves differently in their presence. The calling program should make one or more calls to the CTXT subroutine. That means it needs to choose the input \(m\) that it passes, and it must make some conclusion (about which of the two libraries it is linked to) based on the return value that it gets. What \(m\) should the calling program choose as input to CTXT? What should the calling program look for in the return values?

    There are many valid ways to write a good calling program, and maybe you can think of several. One good approach is to observe that bitwise-AND with \(k\) can never "turn a 0 into a 1." So perhaps the calling program should choose \(m\) to consist of all 0 s. When \(m=0^{\lambda}\), the \(\mathcal{L}_{\text {ots\$-real }}\) library will always return all zeroes, but the \(\mathcal{L}_{\text {ots\$-rand }}\) library may return strings with both \(\theta\) s and 1s.

    We can formalize this idea with the following calling program:

    截屏2023-03-04 16.29.45.png

    Next, let’s ensure that this calling program behaves differently when linked to each of these two libraries.

    截屏2023-03-04 16.30.08.png

    When \(\mathcal{A}\) is linked to \(\mathcal{L}_{\text {ots\$-real }}, c\) is computed as \(k \& 0^{\lambda}\). No matter what \(k\) is, the result is always all-zeroes. Therefore, \(\mathcal{A}\) will always return true.

    In other words, \(\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {ots } \$ \text {-real }} \Rightarrow\right.\) true \(]=1\).

    截屏2023-03-04 16.30.27.png

    When \(\mathcal{A}\) is linked to \(\mathcal{L}_{\text {ots\$-rand }}, c\) is chosen uniformly from \(\{0,1\}^{\lambda}\). The probability that \(c\) then happens to be all-zeroes is \(1 / 2^{\lambda}\).

    In other words, \(\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {ots\$-rand }} \Rightarrow\right.\) true \(]=1 / 2^{\lambda}\).

    Since these two probabilities are different, this shows that \(\mathcal{L}_{\text {ots\$-real }}^{\Sigma} \not \equiv \mathcal{L}_{\text {ots\$-rand }}^{\Sigma}\).In other words, the scheme does not satisfy this uniform ciphertexts property.

    So far we have two security definitions. Does this encryption scheme satisfy one but not the other?

    Claim \(2.10\)

    Construction \(2.8\) does not satisfy one-time secrecy (Definition 2.6).

    Proof

    This claim refers to a different security definition, which involves two different libraries. When we plug in the details of Construction \(2.8\) into the libraries of Definition \(2.6\), we get the following:

    截屏2023-03-04 16.30.53.png

    Now we need to write a calling program that behaves differently in the presence of these two libraries. We can use the same overall idea as last time, but not the same actual calling program, since these libraries provide a different interface. In this example, the calling program needs to call the EAVESDROP subroutine which takes \(t\) wo arguments \(m_{L}\) and \(m_{R}\) How should the calling program choose \(m_{L}\) and \(m_{R}\) ? Which two plaintexts have different looking ciphertexts?

    A good approach is to choose \(m_{L}\) to be all zeroes and \(m_{R}\) to be all ones. We know from before that an all-zeroes plaintext always encrypts to an all-zeroes ciphertext, so the calling program can check for that condition. More formally, we can define the calling program:

    截屏2023-03-04 16.31.16.png

    Next, we need to compute its output probabilities in the presence of the two libraries.

    截屏2023-03-04 16.31.41.png

    When \(\mathcal{A}\) is linked to \(\mathcal{L}_{\text {ots- }}, \underline{c}, \mathrm{is}\) computed as an encryption of \(m_{L}=\) \(0^{\lambda}\). No matter what \(k\) is, the result is always all-zeroes. So,

    \[\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {ots-L }} \Rightarrow \text { true }\right]=1 \]

    截屏2023-03-04 16.36.37.png

    When \(\mathcal{A}\) is linked to \(\mathcal{L}_{\text {ots-R }}, c\) is computed as an encryption of \(m_{R}=\) \(1^{\lambda}\). In other words, \(c:=k \& 1^{\lambda}\). But the bitwise-AND of any string \(k\) with all 1s is just \(k\) itself. So \(c\) is just equal to \(k\), which was chosen uniformly at random. The probability that a uniformly random \(c\) happens to be all-zeroes is

    \[\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {ots-R }} \Rightarrow \text { true }\right]=1 / 2^{\lambda}\]

    Since these two probabilities are different, \(\mathcal{L}_{\text {ots-L }}^{\Sigma} \not \equiv \mathcal{L}_{\text {ots-R }}^{\Sigma}\) and the scheme does not have one-time secrecy.


    This page titled 2.3: How to Demonstrate Insecurity with Attacks is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek (Open Oregon State) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.