4
$\begingroup$

Since OTP have to be agreed upon in advance, they may be longer than the plaintext. So in this case, how is the encryption done? Is the OTP truncated to the same length of the plaintext before encrypting or is some kind of padding used - how does it work?

I am talking about the case where Alice & Bob exchange a book of One Time Pads. Each page of the Pad is used for one plaintext encryption. So each page is of a fixed length & is always longer than the plaintext which it encrypts. So how is the difference in length handled?

As per Dan Boneh's book, a scheme which leaks the length of the plaintext cannot satisfy the definition of perfect security. If we only use that much part of the OTP same as the length of the plaintext, then we are essentially leaking the length of the plaintext because then ciphertext is same length of the plaintext. So how is this handled? I am looking for an authoritative source on how this is handled? Is it via padding? If so, how is the padding done?

$\endgroup$
7
  • $\begingroup$ @kelalaka What does "Halt the messaging" mean? What does "face the key reuse" mean? The wikipedia example with Hello as plaintext seems to use a key which is the same length as the plaintext $\endgroup$
    – user93353
    Nov 2 '20 at 8:27
  • $\begingroup$ @kelalaka - they key is not depleted. I am asking for the case where the key is longer than the plaintext. $\endgroup$
    – user93353
    Nov 2 '20 at 8:31
  • $\begingroup$ @kelalaka - No, I am not asking how the OTP is working. So the rest of your comment doesn't make sense to me. $\endgroup$
    – user93353
    Nov 2 '20 at 8:37
  • $\begingroup$ @kelalaka - I am asking where your sender & receiver have a whole book of one time pads. Each page of the book is supposed to be for a particular day. So each page is a fixed length OTP. In this case, if the plaintext is smaller than the OTP, how is that handled $\endgroup$
    – user93353
    Nov 2 '20 at 8:39
  • $\begingroup$ You might get away from the length issues by doing the following: Let $N$ be the number of all possible messages and $M$ the message space. Define a bijective mapping $\phi: M \to Z_N$. The your pad book can simply be strings of elements in $Z_N$. To OTP-encrypt $m$: apply $\phi$ and perform addition of encoded message and the pad mod $N$. To decrypt do the reverse: substract then decide. This would still be an OTP but without the maximum lengths considerations. $\endgroup$ Nov 2 '20 at 12:29
5
+50
$\begingroup$

In OTP, one party generates a uniform randomly key, writes it in a roll of paper, or a book, or CD, or USB. They transmit it in person with reliable people to the other side.

The OTP keystream obviously is a long stream to long-time use, i.e. one can encrypt many messages over time without using any bits again. If a predetermined size exists to achieve the perfect secrecy, the long stream must be divided into chunks.

  • OTP with hiding the maximum possible length of the message;

    Wikipadia defn;

    One-time pads are "information-theoretically secure" in that the ciphertext provides no information about the original message to a cryptanalyst (except the maximum possible length of the message).

    Let both parties agree on a maximum length of the messages in advance, say $t$.

    Let the keystream is represented by $k_i$ and the message to be encrypted be $m$ with length $\ell$. Then the encryption is performed with the first $\ell$ part of the message. The remaining part is padded, here 10..0 bit padding is used since it is easy to apply even by hand.

    \begin{align} c_i &= k_i \oplus m_i , \quad\text{for } 0\leq i < \ell\\ c_{\ell} &= k_1 \oplus 1\\ c_i &= k_i , \quad\quad\quad\;\; \text{for } \ell < i < t\\ \end{align}

One time pad - how is the difference in length between the plain text & the OTP handled?

Two cases we have;

  1. The OTP keystream is shorter: in this case, one should not send reusing the keystream. Otherwise, two(or many)-time pad use occurs, and that OTP is no longer informationally secure and can be broken.

    One can break the messages into parts. This, however, may leak the information about the message length is longer than $t$ if the adversary observing the message traffic and two consecutive message sending is unusual.

  2. The OTP keystream is longer: The 10.. padding as above.


10..0 padding (bit padding)

The padding simply works as adding 1 to the message then adding as many as 0s to fill the message size and possibly none. Consider only 16-bit length fixed messages;

message1 = 1010110          wiht padded 1010110100000000
message2 = 101011101100101  wiht padded 1010111011001011

The unpadding (removing the padding) starts from the end of the message, remove the trailing zeros if there are any, and then one 1.

Note that to work with the fixed messages, the length of the message must be one bit less than the fixed size. Otherwise, one cannot decide that the padded message 1010111011001011 is message2: 101011101100101 or 1010111011001011.

Other paddings

The bit padding works for bits, there are other paddings that works in the binary case;

  • ANSI X9.23 : Block-based padding, the remaining bytes in the last block is filled with 00 and finally the length of the padding is added.
  • ISO 10126 : Same as above, instead of 00s random bytes are added
  • PKCS#5 and PKCS#7 : can only support a message size of fewer than 256 bytes.
  • ISO/IEC 7816-4: Identical to the bit padding, the byte 80 is added then the remaining bytes are set to 00

Historical paddings:

In short, currently none.

  • Currently, the first describer is Frank Miller in 1882. the OTP is patented by Gilbert Vernam in 1919 (U.S. Patent 1,310,719) this patent doesn't include any padding.

  • The Venona project doesn't mention either

  • Shannon doesn't define either

$\endgroup$
15
  • $\begingroup$ In your method, the ciphertext will leak the length of the plaintext because you are using the keylength which is same length as the plaintext & keeping the rest for future use. As per Boneh, if the ciphertext leaks the length of the plaintext, then it's not perfect secrecy $\endgroup$
    – user93353
    Nov 2 '20 at 8:55
  • $\begingroup$ That is not the standard definition of perfect secrecy. - so Dan Boneh is wrong? He writes that for Perfect Security, the Cipher text shouldn't leak the length of the Plaintext & he calls the One Time Pad as Perfect Security $\endgroup$
    – user93353
    Nov 2 '20 at 9:10
  • $\begingroup$ Yes, your wiki agrees with Boneh. A One time Pad leaks only maximum possible length of the plaintext & not the actual length of the plaintext $\endgroup$
    – user93353
    Nov 2 '20 at 9:20
  • 1
    $\begingroup$ As I said the bit padding in fixed-length requires that messages must be 1 bit less than the fixed length size so that one can add the 1... $\endgroup$
    – kelalaka
    Nov 2 '20 at 11:11
  • 4
    $\begingroup$ No. In the bit padding, the 1 is always added, 0s added as many as possible even none. Ending with 1 means there was no need to add any 0s. Seeing 0s means there are 0s on the padding after the 1. $\endgroup$
    – kelalaka
    Nov 2 '20 at 11:15
2
$\begingroup$

Imagine the OTP and the message are like the hook and loop sides of Velcro tape. The OTP is the hook tape, and you have a stack of fixed length rolls of it. Each roll is like a page in a codebook, and the stack is the whole book.

enter image description here

In order for you to encrypt the message, you need to cut a length of the hook tape to match the loop tape (message), then stick them together. Once you have cut a length off of your hook tape roll, it is gone and you can no longer use it, just like you can no longer use those bits of your OTP.

You have less hook tape in that roll than you did before. If you have enough hook left over for more pieces of loop, you can use it, or you can choose to just not use it anymore and go onto a new roll.

If you are padding the message to hide the true length, the loop tape is just longer, so you need more hook tape.

Just like you can choose how to use the hook tape according to those rules, you can choose how you use the OTP bits, there is no predefined choice.

$\endgroup$
4
  • $\begingroup$ In order for you to encrypt the message, you need to cut a length of the hook tape to match the loop tape (message) - is that always the case? If so, then you are leaking the length of the plaintext. As per Dan Boneh's book, if you leak the length of the plant text, than that scheme cannot satisfy our definition of perfect security $\endgroup$
    – user93353
    Nov 5 '20 at 3:29
  • $\begingroup$ I have updated the question to add this. $\endgroup$
    – user93353
    Nov 5 '20 at 3:31
  • $\begingroup$ @user93353 look 2 paragraphs further $\endgroup$ Nov 5 '20 at 4:11
  • $\begingroup$ I am looking for some authoritative source for how this is handled $\endgroup$
    – user93353
    Nov 5 '20 at 4:39

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.