Variant of otp cipher with symmetric key solution

Section on Information and Communication Technology (ICT) - No. 16 (12-2020)
VARIANT OF OTP CIPHER WITH
SYMMETRIC KEY SOLUTION
Luu Hong Dung1, Tong Minh Duc1, Bui The Truyen1
Abstract
The paper proposes a solution to construct symmetric–key cryptographic algorithms
based on OTP cipher developed based on the cipher One – Time Pad (OTP). Advantages
of the algorithms built according to the proposed new solution is to have secure and efficient
implementation as OTP cipher, but the establishment, management - distribution and usage
of keys are exactly the same as the Symmetric key cryptosystems in practice (DES, AES,. . . ).
Index terms
Symmetric-Key Cryptography, Symmetric-Key Cryptographic Algorithm, Symmetric-
Key Cryptosystems, One - Time Pad Algorithm, OTP Cipher.
1. Introduction
ONE – Time Pad (OTP) is presented in documents [1], [2], [5], [7], [8]. On July 22,1919, U.S. Patent 1,310,719 was issued to Gilbert Vernam for the XOR operation
used for the encryption of a one-time pad. The basic principle of OTP cipher is to
use a pre-shared private key with the length equal to the length of the message to be
encrypted (plaintext), the bits of the ciphertext received from XOR directly the bits
of the plaintext with the corresponding bits of the private key. The theory of Claude
E. Shannon [10] has shown that OTP cipher is an encryption with “Perfect Secrecy”.
Given perfect secrecy, in contrast to conventional symmetric encryption, OTP cipher
is immune even to brute-force attacks. Trying all keys simply yields all plaintexts,
all equally likely to be the actual plaintext. Even with known plaintext, like part of
the message being known, brute-force attacks cannot be used with quantum computer
for this kind of encryption also becomes meaningless, the resulting ciphertext will be
impossible to decrypt or break if the following four conditions are met: - The key must
be truly random; - The key must be at least as long as the plaintext; - The key must
never be reused in whole or in part; - The key must be kept completely secret. However,
OTP cipher has high security and encryption speed as well as the ability to install easily
on devices with limited computing capacity and resources, but with requirements that
need to be met are outlined, this type of encryption few can be used in reality practice.
1 Le Quy Don Technical University
38
Journal of Science and Technique - Le Quy Don Technical University - No. 213 (12-2020)
The one-time pad has serious drawbacks in reality because it requires: Truly random,
as opposed to pseudorandom, one-time pad values, which is a non-trivial requirement.
If the key isn’t truly random then: a) From a known key, an attacker can find keys that
were used previously, or keys to be used in the future. b) The key bit chain will have an
iterative cycle, thereby creating a relationship between the plaintext and the ciphertext,
the attacker can take advantage of this association to break the code similar to Vigenère
multi-table (also known as the tabula recta) encryption.
The main reason OTP encryption makes practical sense is because the key is used
only once and cannot be smaller than the size of the encrypted message. Obviously,
instead of having to pass the private key from sender to receiver over a secure channel,
one can transmit the plaintext on it directly without having to worry about encryption.
In [3], the solution to develop a highly efficient and secure symmetric key system
from combining encryption using OTP cipher, one-time key with source systems such
as: RSA [9], ElGamal [4],... This solution, an encoded message is divided into bit
blocks of a specified size, the first block of data is encrypted with a exponentiation
algorithm, the remaining blocks are encrypted in OTP cipher using a disposable key
of the size corresponding to the data block, a shared private key (sender/encryption
side) and (receiver/decryption side) are a parameter set of the exponentiation algorithm
used to encrypt the first data block. The algorithms construct according to this solution
are capable of eliminating most known attacks in reality [11] while still having a high
level of safety and efficiency. However, encryption of the first plaintext block with
exponentiation algorithm has somewhat reduced the performance of these algorithms,
furthermore using the exponentiation cipher parameter shares a private key between the
parties send - receive has performed setup, the key management-distribution of these
algorithms is significantly different from other block ciphers such as DES, AES [12]...
This paper proposes a solution that allows creating variations of OTP ciphers. The
establishment, management-distribution of keys identical to the symmetric key system
being used in practice. In addition, the integrity of the encrypted message and trace-
ability is an important addition to the algorithms built according to this solution.
2. Variant of OTP cipher with symmetric key solution
2.1. Symmetric key solution
The symmetric key solution is built on the following two basic principles:
- Encrypt and decrypt messages as blocks of data by OTP algorithm;
- Use 2 different keys to encrypt/decrypt messages.
2.1.1. Encrypt and decrypt messages as blocks of data by OTP algorithm:
The P plaintext is encoded in the form of n blocks of data Pi of m-bits size:
P = {P1, P2, ..., Pi, ..., Pn}, i = 1, n, |Pi| = m bits
39
Section on Information and Communication Technology (ICT) - No. 16 (12-2020)
The one-time key KOT also includes n subkeys Ki whose size corresponds to the
size of the data block:
KOT = {K1, K2, ..., Ki, ..., Kn}, i = 1, n, |Ki| = m bits
The send-side encryption algorithm is to XOR the bits of the plaintext block Pi with
the corresponding bits of the subkey Ki:
Ci = Pi ⊕Ki, i = 1, n
So C ciphertext in principle also includes n blocks of data Ci of m-bits size:
C = {C1, C2, ..., Ci, ..., Cn}, i = 1, n, |Ci| = m bit ... Lmin ≤ LK ≤ 2L−LP . Which: Lmin is the minimum size enough
to ensure a safety threshold; LP is the plaintext size and L is the maximum size of
input data of the function F1. Then, the input data of function F1 is the bit string
serial concatenation of KS with P in the case of creating the value C0 or the bit string
concatenation of KS with C0 in the case of a need to create subkey K1. From here, it
can be seen that the private key is pre-shared between the sender/encryption side and
receiver/decryption side according to the symmetric key solution can be kept secret not
only a value but also a private key size.
The sender/encryption side, the Ki keys are generated by the same algorithm from
the encrypted data blocks and the subkey preceding the function F2:
Ki = F2(Pi−1, Ki−1), i = 2, n
F2 is a function with the following properties: a) random function; b) one-way
function. Similar to F1 function, the role of F2 function here can also be performed by
hash functions (MD5, SHA-1/256/512, ...) or block ciphers (DES, AES, ... ).
The receiver/decryption side, after creating: K1 = F2(C0, KS) will decrypt the first
block: P1 = C1⊕K1. From here, the next subkeys will be generated following the same
rules as on the encryption side:
Ki = F2(Pi−1, Ki−1), i = 2, n
Then the next block of code will be decrypt:
Pi = Ci ⊕Ki, i = 2, n
Note that the creation of the KOT subkeys on the sender side can be done before
or simultaneously with the encryption data blocks of the message. On the receiving
side, the creation of KOT subkeys and the decryption of the message need to be done
concurrently.
2.2. Variant of OTP cipher with symmetric key solution
Variations of OTP cipher with symmetric key solutions have a common form, in-
cluding algorithms: key generation, encryption, decryption - authentication. In which,
the key generation algorithm and the encryption algorithm on the sending side include
the implementation steps described as follows:
Input: P = {P1, P2, ..., Pi, ..., Cn} , KS
Output: C = {C0, C1, C2, ..., Ci, ..., Cn}
[1]. C0 = F1(P,KS)
41
Section on Information and Communication Technology (ICT) - No. 16 (12-2020)
[2]. K1 = F1(C0, KS)
[3]. C1 = P1 ⊕K1
[4]. C[0] = C0, C[1] = C1
[5]. for i = 2 to n do
begin
Ki = F2(Pi−1, Ki−1)
Ci = Pi ⊕Ki
C[i] = Ci
end
[6]. Retunr C
Note:
Operation "⊕" is an XOR (modulo 2 additions).
The key generation algorithm and the decryption - authentication algorithm on the
receiving side include the following steps:
Input: C = {C0, C1, C2, ..., Ci, ..., Cn} , KS
Output: M = {M1,M2, ...,Mi, ...,Mn}, true/false
[1]. K1 = F1(C0, KS)
[2]. M1 = C1 ⊕K1)
[3]. M[1] = M1
[4]. for i = 2 to n do
begin
Ki = F2(Mi−1, Ki−1)
Mi = Ci ⊕Ki
M[i] = Mi
end
[5]. M0 = F1(M,KS)
[6]. if (M0 = C0) then return {M, true}
else return {M, false}
Note:
- If the result is {M, true} messages are then verified for origin and integrity.
- If C is not changed during transmission from sender to receiver, the result will
42
Journal of Science and Technique - Le Quy Don Technical University - No. 213 (12-2020)
return {M, true} which is obvious, because both sender and receiver use the same
KOT key to encrypt and decrypt the message.
A variation of OTP cipher with the symmetric key solution when choosing the SHA-
256 hash function that plays the role of functions F1 and F2 will illustrate the creation
of a symmetric key encryption algorithm according to the proposed solution. In this
algorithm, the message is encrypted as n blocks of 256-bits data:
P = {P1, P2, ..., Pi, ..., Pn}, i = 1, n, |Pi| = 256 bits
The KOT key consisting of n subkeys Ki is also 256-bits in size. Shared private key
KS have LK sizes are selected customization within: 128-bits ≤ LK ≤ 264 − LP bit,
here: LP is the size of the message to be encrypted.
The sending ciphertext consists of n+ 1 blocks of 256-bits:
C = {C0, C1, C2, ..., Ci, ..., Cn}, i = 1, n, |Ci| = 256 bits
The key generation algorithm and the encryption algorithm on the sending side are
described as follows:
Input: P = {P1, P2, ..., Pi, ..., Pn} , KS
Output: C = {C0, C1, C2, ..., Ci, ..., Cn}
[1]. C0 = SHA256(P ||KS)
[2]. K1 = SHA256(C0||KS)
[3]. C1 = P1 ⊕K1
[4]. C[0] = C0, C[1] = C1
[5]. for i = 2 to n do
begin
Ki = SHA256(P ||Ki−1)
Ci = Pi ⊕Ki
C[i] = Ci
end
[6]. return C
Note:
- Operation "||" is the concatenation of two bit strings.
- SHA256 is a SHA-256 hash with an output size of 256-bits
The key generation algorithm and the decryption-authentication algorithm on the
receiving side include the following steps:
Input: C = {C0, C1, C2, ..., Ci, ..., Cn} , KS
43
Section on Information and Communication Technology (ICT) - No. 16 (12-2020)
Output: M = {M1,M2, ...,Mi, ...,Mn}, true/false
[1]. K1 = SHA256(C0||KS)
[2]. M1 = C1 ⊕K1)
[3]. M[1] = M1
[4]. for i = 2 to n do
begin
Ki = SHA256(Mi−1||Ki−1)
Mi = Ci ⊕Ki
M[i] = Mi
end
[5]. M0 = SHA256(M ||KS)
[6]. if (M0 = C0) then return {M, true}
else return {M, false}
Note:
If the result is {M, true} then the message is verified for origin and integrity.
Conversely, if the result is {M, false}, M is the fake message or C was changed during
the transmission.
2.3. Some reviews of the security of symmetric-key cryptography algorithms built
according to the newly proposed solution
Similar to OTP cipher, because the KOT key is used only once, differential and linear
attacks,... generally all known attacks with typical block ciphers like DES, AES,... does
not affect the proposed solution. Here, the security of the symmetric lock solution is
evaluated by its resistance to several types of attacks as follows:
2.3.1. Attack a shared private key:
Attack on a shared secret key, possible based on C0 value:
C0 = F1(P,KS)
or the value of the subkey K1:
K1 = F1(C0, KS)
However, it is easy to see that given the property of the one-way function, furthermore
the size of KS is a secret parameter, finding KS from C0, P and K1 (K1 can know
when P public) is completely unfeasible.
2.3.2. Brute-force attack when only the ciphertext:
If the KOT is a truly random bit string then no relationship between the plaintext and
44
Journal of Science and Technique - Le Quy Don Technical University - No. 213 (12-2020)
the ciphertext is generated. A brute-force attack can then translate a ciphertext into any
plaintext of the same length, and for the attacker the message is most likely encrypted.
That is, there won’t be any information in the ciphertext that would allow an attacker to
choose the correct plaintext from meaningful messages after it has been decoded using
the brute-force attack. Also, if the KOT is truly random, then from a known key, an
attacker cannot find other keys that were generated before or after.
According to the proposed solution, the one-time key KOT is a set of subkeys Ki
generated by the F1 and F2 functions according to the principle: a) each subkey Ki is
generated from the subkey preceding Ki−1 and the corresponding data block Pi−1 by
F2; b) The first subkey Ki is generated by the "key seed" C0 and the private key shared
by KS by the function F1. Thus, KOT is essentially a bit string created by concatenating
n strings (bit) Ki, each of which is the first m bit of the n base bit strings generated by
F1 or F2 with initial values or "seed" different. In a sense, the KOT bit string is made
up of n different base bit strings, by taking from each base bit string one substring (the
first m bits) and then concatenating these n substrings with together.
The reason base bit strings generated by the functions F1 and F2 here are functions that
generate random numbers or even pseudo-random functions but have a large repetition
period, so in limited bit strings Ki will not have a repetitive cycle, and so these bit
strings are truly random is absolutely certain. Again, the base bit strings are made up
of different initialization values, so they are independent of each other, leading to the
Ki substrings (the first m bits of the base bit sequence) also independent of each other.
Thus, KOT is a random and independent bit sequence, so in KOT there will be no
repeating cycle and therefore the randomness can be completely confirmed.
Therefore, the KOT generated according to the proposed solution met the critical
randomness requirement in the sense that: a) From a known key, an attacker cannot
find pre- or post-generated keys. b) The key bit sequence has no repeating cycle, so it
will not create a relationship between the plaintext and the ciphertext. Therefore, the
proposed solution algorithms cannot be defeated by brute-force attack.
2.3.3. Phishing:
The OTP cipher does not provide verification for an encrypted message, so an attacker
could block the ciphertext was sent and send the recipient a fake ciphertext of the
same size as the true message. In the case of decrypt to a meaningless plaintext, the
receiver may speculate that the tampering was made or caused by a communication
error. However, if decrypt to a meaningful plaintext, then the receiver has no way of
confirming whether the plaintext is true or fake. With algorithms built according to the
proposed solution, the receiver can fully verify the origin as well as the integrity of the
after decryption message when calculating: M0 = F1(M,KS) and check the condition:
M0 = C0. Furthermore, only the receiver can perform this verification (apart from the
sender, only the receiver can know about KS).
45
Section on Information and Communication Technology (ICT) - No. 16 (12-2020)
3. Conclusion
The paper proposes a solution to construct a symmetric key system developed from
OTP cipher. The advantage of algorithms built according to this solution is the security
and efficiency inherited from the OTP cipher, but the shared private key can be used
multiple times. Furthermore, the establishment, management-distribution and usage of
keys are done exactly like other symmetric key cryptosystems. These are very impor-
tant properties for these algorithms to be applied in reality. In addition, due to the
authentication of origin and integrity of encrypted messages, these algorithms are also
anti-phishing, the basic requirements that real applications place.
References
[1] Jeff Connelly. A Practical Implementation of a One-time Pad Cryptosystem, 2008.
[2] Neil J Croft and Martin S Olivier. Using an approximated one-time pad to secure short messaging service
(sms). In Proceedings of the Southern African Telecommunication Networks and Applications Conference.
South Africa, pages 26–31, 2005.
[3] Lưu Hồng Dũng, Nguyễn Vĩnh Thái, Tông Minh Đức, and Bùi Thế Truyền. Giải pháp phát triển thuật toán
mật mã khóa đối xứng từ các hệ mã lũy thừa và mã otp. PROCEEDING of Publishing House for Science and
Technology, 2017.
[4] Taher ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE
transactions on information theory, 31(4):469–472, 1985.
[5] Raman Kumar, Roma Jindal, Abhinav Gupta, Sagar Bhalla, and Harshit Arora. A secure authentication system-
using enhanced one time pad technique. International Journal of Computer Science and Network Security,
IJCSNS, 11(2):11–17, 2011.
[6] Alfred J Menezes, Paul C Van Oorschot, and Scott A Vanstone. Handbook of applied cryptography. CRC
press, 2018.
[7] Sharad Patil, Manoj Devare, and Ajay Kumar. Modified one time pad data security scheme: Random key
generation approach. International Journal of Computer Science and Security (IJCSS), 3(2):138, 2009.
[8] Sharad Patil and Ajay Kumar. Effective secure encryption scheme [one time pad] using complement approach.
International Journal of Computer Science and Security (IJCSS), 3(2), 2002.
[9] Ronald L Rivest, Adi Shamir, and Leonard Adleman. A method for obtaining digital signatures and public-key
cryptosystems. Communications of the ACM, 21(2):120–126, 1978.
[10] Claude E Shannon. Communication theory of secrecy systems. The Bell system technical journal, 28(4):656–
715, 1949.
[11] Mark Stamp and Richard M Low. Applied cryptanalysis: Breaking ciphers in the real world. John Wiley &
Sons, 2007.
[12] Advance Encryption Standard. Federal information processing standards publication 197. FIPS PUB, pages
46–3, 2001.
Manuscript received: 30-07-2020; Accepted: 10-10-2020

46
Journal of Science and Technique - Le Quy Don Technical University - No. 213 (12-2020)
Luu Hong Dung graduated in Electronics and Communications from Le Quy Don Technical
University in 1989, PhD at Le Quy Don Technical University in 2013; Currently working in
the IT department - Le Quy Don Technical University; Research direction: Cryptography and
information security. E-mail: luuhongdung@gmail.com
Tong Minh Duc graduated from Le Quy Don Technical University in 2000. Received a doctor-
ate from University of Electrical Engineering - Russia in 2007. Currently, he is a lecturer in the
Faculty of Information Technology - Le Quy Don Technical University. Research field: Image
processing, object identification, information security safety. E-mail: ducmta@gmail.com
Bui The Truyen graduated from Le Quy Don Technical University in 2000. He received a
doctor’s degree in analysis and information processing at Moscow Aviation Institute, Russia in
2008. Currently, he is a lecturer at the Le Quy Don Technical University. His research interests
are virtual reality simulation and information security. E-mail: truyenbuithe@lqdtu.edu.vn
BIẾN THỂ CỦA MẬT MÃ OTP VỚI GIẢI PHÁP KHÓA
ĐỐI XỨNG
Tóm tắt
Bài báo đề xuất giải pháp xây dựng các thuật toán mật mã khóa đối xứng phát triển từ
hệ mã sử dụng khóa 1 lần - OTP (One - Time Pad). Ưu điểm của giải pháp mới đề xuất là
các thuật toán được xây dựng có tính an toàn và hiệu quả thực hiện cao hơn của mã OTP,
nhưng việc thiết lập, quản lý - phân phối khóa hoàn toàn giống như các hệ mã khóa đối xứng
được sử dụng trong thực tế (DES, AES. . . ).
47