Analysis of Vulnerabilities That Can Occur When Generating One-Time Password

Featured Application

Cryptography; Random Number analysis.

Abstract

A one-time password (OTP) is a password that is valid for only one login session or transaction, in IT systems or digital devices. This is one of the human-centered security services and is commonly used for multi-factor authentication. This is very similar to generating pseudo-random bit streams in cryptography. However, it is only part of what is used as OTP in the bit stream. Therefore, the OTP mechanism requires an algorithm to extract portions. It is also necessary to convert hexadecimal to decimal so that the values of the bit strings are familiar to human. In this paper, we classify three algorithms for extracting the final data from the pseudo random bit sequence. We also analyze the fact that a vulnerability occurs during the extraction process, resulting in a high frequency of certain numbers; even if cryptographically secure generation algorithms are used.

1. Introduction

In general, fixed passwords are vulnerable to re-use attacks due to malicious attacker’s password collection. One-Time Password (OTP), on the other hand, is a password that is used differently each time for a login session or transaction [1]. Thus, this makes it impossible to reuse previously collected things. It also has the property of randomness, which makes it mathematically impossible to infer the next password from the current one. It is known to be highly secure because of these features, and it can be used as an authentication service in Information & Communication Technology (ICT) [2] fields such as mobile-payment [3,4] and mobile-cloud computing [5,6].

OTP mechanism generates passwords using secrets shared in advance between the certification authority and the user, and time or event occurrence information. So the attacker can not infer this by himself. Currently, it is provided as a token, card type device (Hardware), and mobile phone application type (Software) [7,8]. Hardware type is frequently used in the financial sector, and the number of issuances and transactions of this is continuously increasing. Software in mobile phones is widely used in online games and IT industries, but financial institutions are developing mobile OTP based on USIM.

2. Background

2.1. Random Number

2.1.1. Randomness

The random number sequence is the same as the result of a series of unbiased “fair” coins. Each side of the coin is 0 or 1, the value of the bit [9]. If it is thrown in succession, 0 and 1 are identically distributed and each trial runs independently. Thus it is equivalent to the result of a perfect random number generator. All parts of the random sequence are independent of each other, so the parts that have already been generated can not affect the next time and can not be predicted [10].

2.1.2. Unpredictability

The (pseudo) random numbers used in cryptography should be unpredictable. In the case of Cryptographically secure Pseudo-Random Number Generators (CPRNG), if the attacker does not know the seed, the output must be unpredictable, and he must not know the input value only by looking at the generated random number sequence (providing forward/backward unpredictability) [9,10]. In general, algorithms for random number generators are public, so the seed must be kept secret to provide unpredictability of the output random number.

2.1.3. Pseudo Random Number Generator (PRNG)

PRNG generates a large number of pseudo random sequences through one or more inputs. Its input value is called seed, and it is generated through a true random number generator (TRNG) because it must provide unpredictability and randomness. Therefore, PRNG is usually used together with TRNG because it uses the output of TRNG as seed [11,12].

Since the PRNG mitigates the bias, statistical characteristics, and correlations of the seeds, the pseudo random number sequence is more random than the true random number sequence. This generally uses cryptographic algorithms and is deterministic.

2.2. One-Time Password (OTP)

2.2.1. OTP Authentication Type

Synchronization type: This is an authentication technique in which the input value of the algorithm is kept the same by the user token and the authentication server [13]. This can be classified into time synchronization [14], event synchronization, time and event combination synchronization, and so on [15].

Non-synchronization method: In this method, the authentication process proceeds without any synchronization information established between the user token and the authentication server. A representative example is the challenge-response method.

2.2.2. OTP Token

This means a dedicated hardware or a software module installed in a mobile phone or the like for OTP. Dedicated hardware tokens have a built-in display for viewing disposable values, and a built-in numeric keypad for PIN entry (optional) [16].

3. Related Works

3.1. Vulnerabilities of OTP on PC

The OTP implemented as S/W on the PC can grasp the actual operation process through reverse engineering. By analyzing this, it is possible to obtain the master key and time information in the OTP, and it is possible to forge/modify the PIN, master key, and time information. If an attacker exploits this, it is possible to generate a valid OTP and even obtain the OTP value in the future. In order to eliminate such functional and logical vulnerabilities, it is required to apply various security reviews when implementing the OTP generation program mounted on the PC. In particular, anti-reversing technology must be applied so that the attacker(s) can not reverse the OTP program to easily perform security function bypass attacks [17].

3.2. Vulnerabilities of OTP in Internet Banking

Although OTP is one of the strongest authentication method to protect against account theft, there is always a possibility of account theft due to the evolution of hacking methods. The MITM (Man-in-the-Middle) attack accesses data transaction paths, and snatches information in the middle of data transactions. The MITB (Man-in-the-Browser) attack refers hacking methods which use malignant programs in the web browser. The MITPC (Man-in-the-PC) attack abuses the vulnerability of hardware environment or the operating system. It controls and attacks every data access path in the OS including the key input, mouse movement, screen, and even memories [18].

3.3. NIST Standards for Cryptographic Random Numbers

SP800-90 (A, B, C)

SP800-90A describes a PRNG that uses approved cryptographic algorithm. This makes it impossible to distinguish between an ideal random sequence and a pseudo random sequence without infinite computational power. It is designed with a fixed finite security strength to measure the workload required to attack PRNG. Ref. [19] SP800-90B describes mechanisms and entropy sources for obtaining unpredictable bits through non-deterministic processes. The entropy value of this source is equal to the Security Strength. Ref. [20] SP800-90C describes the overall RNG structure combining 90A and 90B, as shown in Figure 1 [12].

4. Materials and Methods

4.1. OTP Mechanism

OTP is generated following the procedure in Figure 1.

The OTP generation process can be roughly classified into three steps [21]: ‘Association information generation’, ‘generation algorithm’, and ‘extraction algorithm’. This is very similar to the process of generating pseudo random numbers used in cryptography [22]. Figure 1 shows similar parts of the two processes in the same color.

4.1.1. Association Information Generation

Association information means to a random value that can be collected from time, event information, and the like. This may be a raw value, depending on the collection method, or it may be a random number converted through additional processes such as hashing and encryption. Association information is similar to the noise source (or entropy source) needed to generate cryptographic pseudo random numbers and is necessary for the unpredictability of OTP. This process corresponds to the red part of Figure 1.

4.1.2. Generation Algorithm

This is a cryptographic algorithm used to generate OTP. This encrypts the association information to produce a 20-byte bit string [23]. The Korean OTP standard [24] introduces the cryptographic algorithm used in this step. Since the generation algorithm is deterministic, it generates the same ciphertext from the same association information. The cryptographic algorithms used should provide a security strength of at least 112 bits [21,23,25]. Different OTP values may be generated according to extraction algorithms in one same bit string. This process corresponds to the blue part of Figure 1.

4.1.3. Extraction Algorithm

This is an algorithm for extracting 3-byte data from the cipher string for use as OTP. This can be divided into static and dynamic algorithms (RFC4226 [23], an OTP-related standard, specifies only dynamic algorithms, and the Telecommunication Technology Association (TTA)’s standard [21] specifies static, dynamic, and improved dynamic algorithms.). This algorithm uses ‘extraction information’ to specify the location to extract. It also uses the value as the ‘extraction data’ at the location specified by the extraction information. The extraction information may use a value of a specific area of the cipher text or a predefined value. Then, the extracted 3-byte hexadecimal value is encoded in decimal so that humans can recognize it. At this time, the extracted 3-byte range is [0, 16777215] (i.e., [0, $2^{24}$− 1]), but the top two digits have little change. Therefore, the two digits are discarded and only the lower six digits are used (Only 0 ∼ 1 for ${10}^7$, only 0 ∼ 6 for ${10}^6$); so the final range is [0, 999999]. This process corresponds to the yellow part of Figure 1.

The static algorithm extracts data by specifying in advance the extraction information (the offset of the cipher text) to be used [21].

An example is shown in Figure 2: Data is extracted by specifying the extraction information as the first starting point of the cipher text. It extracts 3-byte contiguous data from the extraction information. If the result of the extracted data is 0x1A2B3C, the number is 1,715,004 when expressed as a decimal number, and the final output OTP is derived as 715,004 corresponding to the lower 6 digits of the decimal number.

The dynamic algorithm extracts data by obtaining extraction information from the cipher text [21,23].

About this example is shown in Figure 3: The value of the lower 4-bit of the lowest byte (i.e., 19th) in the cipher text is used as extraction information. The extracted data is contiguous 3-byte with an index of the extraction information as a starting point. If the result of the extracted data is 0xE7F809, that’s decimal is 15,202,313, the final output OTP is derived as 202,313 corresponding to the lower 6 digits.

The improved dynamic algorithm is used when generating OTP using a chip used as a smart card or USIM [21]. Figure 4 shows an improved dynamic algorithm; it extracts three bytes from two or more pieces of extraction information in the cipher text.

Extraction information of this algorithm is used to designate specific area of cipher text. If the value of the lower 4-bit of the lowest byte is used as the first extraction information (namely, LSB 4-bit 0x0D, the lowest byte 0x4D of the cipher text), then the data 0xE7 at that location (0x0D) is used as the first extraction data. And the second extraction information is 0x07, the value of the lower 4-bit of the first extraction data. The same method is repeated to select 3-byte extracted data. Final OTP is 171,883 which is the lower 6 digits of 15,171,883 that converts the extracted data 0xE7812B to decimal.

5. Analysis of OTP Vulnerabilities

5.1. Vulnerability in OTP Generation Algorithm

The pseudo random number generation algorithm specified in the TTA’s standard “One-time password (OTP) encryption key management security requirements” [24] is shown in

Table 1. Standard generation algorithms for OTP in Korea.

Classification	Standard Algorithms That Specified
Hash based	DSA-PRNG-SHA1	Hash-DRBG-SHA1
	ECDSA-PRNG-SHA11	KCDSA-PRNG-HAS1160
	HMAC-DRBG-SHA-256
Block cipher based	ANSI X9.31 triple DES	DSA-PRNG-ARIA
	ANSI X9.31 AES	DSA-PRNG-SEED
	ANSI X9.17 PRNG-triple DES	ECDSA-PRNG-ARIA
	CTR-DRBG-tiple-DES	ECDSA-PRNG-SEED
	CTR-DRBG-tiple-AES-128,192,256
etc.	Micali Schnorr-DRBG

.

Table 2. Hash functions that can be used to provide the targeted security strengths.

Security Strength	Digital Signatures and Hash-Only Applications	HMAC, Key-Derivation Functions, Random Number Generation
≤80	SHA-1
112	SHA-224, SHA-512/224, SHA3-224
128	SHA-256, SHA-512/256, SHA3-356	SHA-1
192	SHA-384, SHA3-384	SHA-224, SHA-512/224
≥256	SHA-512, SHA3-512	SHA-256, SHA-512/256, SHA-384,
		SHA-512, SHA3-512

shows the security strength defined by the NIST [25]. Currently, Korea’s OTP standard recommends to provide more than 112-bit security strength as a cryptographic algorithm that can be used to generate OTP. As shown in Table 2, SHA1 has a security strength of 80-bit or less, so NIST prohibits its use for key derivation and random number generation. However, the TTA standard still includes SHA1, which is unsuitable for using OTP; since HAS-160 is also a hash function built on SHA1, its security level is similar to SHA1. Therefore it should not be used anymore. In addition, SHA1 and HAS-160 are currently excluded from the National Intelligence Service (NIS)’s approved algorithm list, as are AES and Triple-DES. In order to proceed with the procedure of generating and communicating random numbers between entities for the purpose of authentication, the NIS’s Approved algorithm should be used, but this is not currently observed in the OTP standard.

5.2. Vulnerabilities in OTP Extraction

The improved dynamic extraction algorithms can be vulnerable to OTP generation. Figure 5 illustrates a situation where a vulnerability can occur in that case.

The improved dynamic algorithm derives new extraction information from the location indicated by the value based on the predetermined extraction information. However, in this process, if the first extraction information and the next one are the same, all three bytes of the extraction data are duplicated. For example, when the least significant byte $arr\left[19\right]$ of the cipher text is 0x42, the extraction information is 0x02, which is LSB 4-bit, and the first extraction data is $arr\left[2\right]$. Then, LSB 4-bit of $arr\left[2\right]$ is the second extraction information. At this time, if the LSB 4-bit of $arr\left[2\right]$ is also 0x02, the second extracted data is $arr\left[2\right]$ again. The third and last process is the same. As a result, a total of three bytes are duplicated. Example output is $arr\left[2\right]$$\left|\right|$$arr\left[2\right]$$\left|\right|$$arr\left[2\right]$. If all the extracted data values are duplicated in the above situation, OTP range is a set of elements that is $arr\left[i\right]$$\left|\right|$$arr\left[i\right]$$\left|\right|$$arr\left[i\right]$ (0x00 ≤ $arr\left[i\right]$ ≤ 0xFF, [0, 255]) form. If this reduced set is called R, then |R| Becomes 256, so |R| is reduced by approximately 99% compared to [0, 999999] (i.e., $[0,{10}^6-1]$), making it easier to predict the random numbers that can be output.

The following assumptions are made to analyze the probability that this situation can occur.

• Store the cipher text 160-bit in the array $arr\left[\right]$, which is 8-bit in size.
• For the integer $t\in [0,19]$, the lower 4-bits of $arr\left[t\right]$ are expressed as ${\left[arr\left[t\right]\right]}_4$.
• If ${\left[arr\left[19\right]\right]}_4=i$, then $arr\left[i\right]$ is used as the first extraction data.
• If ${\left[arr\left[i\right]\right]}_4=j$, then $arr\left[j\right]$ is used as the second extraction data.
• If ${\left[arr\left[j\right]\right]}_4=k$, then $arr\left[k\right]$ is used as the third extraction data.

In this case, the probability that a duplicate situation occurs in the extraction algorithm can be obtained as follows. Since the bit string is the output of the encryption algorithm, i.i.d is satisfied between all bits. That is, each bit is independent and the probability of getting 0 or 1 is $\frac{1}{2}$. $Pr$[All extraction information is duplicated] is

$$\begin{array}{cc}\hfill & Pr[\mathrm{output}\mathrm{of}\mathrm{extraction}=(arr\left[i\right]\left|\right|arr\left[i\right]\left|\right|arr\left[i\right]\left)\right]\hfill \\ \hfill & =\sum _{i=0}^{15}Pr[{\left[arr\left[19\right]\right]}_4=i,{\left[arr\left[i\right]\right]}_4=i,,{\left[arr\left[j\right]\right]}_4=i]\hfill \\ \hfill & =\sum _{i=0}^{15}Pr[{\left[arr\left[19\right]\right]}_4=i,{\left[arr\left[i\right]\right]}_4=i]\hfill \\ \hfill & =\sum _{i=0}^{15}Pr[({\left[arr\left[19\right]\right]}_4=i)\times ({\left[arr\left[i\right]\right]}_4=i)],(\because i.i.d)\hfill \\ \hfill & =\sum _{i=0}^{15}\frac{1}{16}\times \frac{1}{16}\hfill \\ \hfill & =16\times \frac{1}{16}\times \frac{1}{16}=\frac{1}{16}\hfill \end{array}$$

(1)

In addition, the probability through the total number of cases can be obtained.

$$\begin{array}{cc}\hfill & Pr\left[\mathrm{All}\mathrm{extraction}\mathrm{information}\mathrm{is}\mathrm{duplicated}\right]\hfill \\ \hfill & =\frac{\mathrm{the}\mathrm{number}\mathrm{of}\mathrm{cases}\mathrm{where}\mathrm{the}\mathrm{lower}4\text{-}\mathrm{bits}\mathrm{of}\mathrm{the}\mathrm{two}\mathrm{positions}\mathrm{are}\mathrm{the}\mathrm{same}}{\mathrm{the}\mathrm{number}\mathrm{of}\mathrm{total}\mathrm{cases}\mathrm{of}160\text{-}\mathrm{bit}\mathrm{string}}\hfill \\ \hfill & =\frac{2^{152}\times 2^4\times 1}{2^{160}}=\frac{1}{16}\hfill \end{array}$$

(2)

This means that whenever a random cipher text 20-byte (160-bit) is generated, there is a $\frac{1}{16}$ probability that the above duplication occurs, resulting in a vulnerability that reduces the size of the range (That is, the probability that the extracted information is duplicated is equal to the probability that the range is reduced.). Similarly, even if the data is duplicated only 2 times instead of 3 times, this process reduces the range and increases the predicted probability.

Moreover, when converting from extracted 3-bytes (24-bits) to 6-digit decimal number, the ideal probability that each appears as output in the range is as follows. Let $N\ge m\ge 1$ be integers, and let $(q,r)=IntDiv(N,m)$ (or $N=mq+r$). And let the random variable X be uniformly distributed over $Z_N$. For z in $Z_m$, let: $P_{\left\{N,m\right\}}\left(z\right)=$$Pr$[X mod $m=z$: X randomly picked in $Z_N$] [23].

Then for any z in $Z_m$,

$$\begin{array}{c}\hfill P_{\left\{N,m\right\}}\left(z\right)=\left\{\begin{array}{cc}\frac{q+1}{N},\hfill & \mathrm{if} 0\le z<r\hfill \\ \frac{q}{N},\hfill & \mathrm{if} r\le z<m\hfill \end{array}\right.\end{array}$$

(3)

Similarly, $Pr[X$ mod ${10}^6$ = z: X randomly picked in $Z_{2^{24}}$] is

$$\begin{array}{c}\hfill P_{\left\{2^{24},{10}^6\right\}}\left(z\right)=\left\{\begin{array}{cc}\frac{16+1}{2^{24}},\hfill & \mathrm{if} 0\le z<777216\hfill \\ \frac{16}{2^{24}},\hfill & \mathrm{if} 777216\le z<999999\hfill \end{array}\right.\end{array}$$

(4)

In other words, the ideal probability is approximately $1/2^{20}$. On the other hand, if the above-mentioned vulnerability occurs, the probability of each element in the set R is converted is as follows. $Pr$[X mod $2^8=z$: X randomly picked in $Z_{2^{24}}$] is

$$\begin{array}{c}\hfill P_{\left\{2^{24},2^8\right\}}\left(z\right)=\left\{\begin{array}{cc}\frac{2^{16}+1}{2^{24}},\hfill & \mathrm{if} 0\le z<0\hfill \\ \frac{2^{16}}{2^{24}},\hfill & \mathrm{if} 0\le z<256\hfill \end{array}\right.\approx \frac{1}{2^8}\end{array}$$

(5)

Since there is no situation where the integer r satisfies $0\le r<0$, it is only in the range $0\le z<256$. In other words, the ideal probability is $\frac{1}{2^8}$. Therefore, if the above mentioned vulnerability occurs, then the probability of each number appears is about 4000 times higher than that of an ideal situation, which occurs in 1 out of 16 cases. As mentioned in the first part of this paper, OTP is used for authentication purposes in various ways, and is particularly widely used in online banking. If an attacker attempts to attack an online banking system that follows this vulnerability, the attacker can significantly reduce the number and time of OTP predictions. In general, an authentication system that performs user authentication through OTP defines Time-To-Live (TTL); this limits the OTP value to be valid only for a specific time. Therefore, in order to succeed in the attack, he must find a valid value within the timeframe. According to the above analysis, the probability of an attacker succeeding in prediction increases significantly from $\frac{1}{2^{20}}$ to $\frac{1}{2^8}$.

This extraction method is vulnerable in terms of unpredictability, although specified in the standard. The standard for OTP-related TTA [21] was issued in 2012, and even RFC 2289 [22], 4226 [23], and 1760 [1] were published between 1995 and 2005 and have not been updated to date. Standards for generating and applying cryptographic random numbers, such as NIST’s SP800-90 series [12,19,20], have only been steadily revised in recent years. In 2015 and 2018, 90A and 90B were released as final versions, and 90C is still in draft. Thus, in the field, the period focused on various properties of cryptographic random numbers (predictability and bias, independence, entropy, etc.) is not long. And only recently has the trend to deal with the security of random numbers in depth. Therefore, looking at the OTP standards of RFCs and TTAs from a modern point of view can reveal vulnerabilities that have not been identified in the past.

To solve this problem, we suggest the following solutions.

• Use of static or dynamic algorithm: Rather than using an improved algorithm that can cause vulnerabilities, using a static or dynamic algorithm is suitable for information security by supplementing the randomness and unpredictability of OTP.
• Increases the number of LSB digits used as extraction information, and increases the length of the output bit string accordingly: Since 16 offsets can be selected using LSB 4-bit extraction information, the length of the output bit stream is used as 20-bytes $(=16+4)$. If this is used as LSB 5-bit or 6-bit, the offset that can be selected increases to 32 or 64, so the length of the output bit string is 36-bytes $(=32+4)$ and 68-bytes $(=64+4)$. In this case, the probability of offset overlapping decreases by $\frac{1}{2}$ each time the bit is increased by one. (For example, $Pr$[All extraction information is duplicated] for 5-bit = $\frac{1}{32}$, $Pr$ for 6-bit = $\frac{1}{64}$)
• Increase the amount of extraction to 4-byte: When the amount of extraction is increased from 3-byte to 4-byte, the range is [0, 16777215] (i.e., $[0,2^{24}-1]$) to [0, 4294967295] (i.e., $[0,2^{32}-1]$, About 4 billion cases). Therefore, OTP can be used up to 7 and 8 digits instead of 6 digits. In this case, since $[0,{10}^7-1]$ and $[0,{10}^8-1]$ can be used, the predictable probability decreases by 1/10 each time by one digit increment.

6. Results and Discussion

6.1. Experiments

6.1.1. Experiment 1: Does This Extraction Vulnerability Really Happen?

To verify that this vulnerability actually occurs depending on the extraction algorithm, the following two experiments were conducted.

Figure 6 shows an experiment to check if duplicate 3-bytes actually occur frequently when different extraction algorithms are applied to the same bit string by encryption algorithm. The experiment proceeds as follows. In order to continuously obtain 3-bytes of different OTP data, an arbitrary bit sequence ($2^{25}$-bit, or $2^{22}$-byte) is input to the block cipher AES [26], and a continuous cipher sequence is generated accordingly. Data that does not apply any extraction method to this string is called a pure cipher text sequence. In this bit string, each static/dynamic/improved algorithm is applied every 20-byte to extract 3-byte. It repeats this to accumulate 1,000,000-byte per algorithm.

And this was done by applying NIST’s statistical randomness test [27] for each data set. The experimental group is the Improved algorithm sequence, and the control groups are the pure cipher text sequence before OTP data extraction, the static algorithm sequence, and the dynamic algorithm sequence.

The result is shown in Figure 7. All of the control group passed every statistical random number test, but the experimental group did not. Although this statistical test cannnot entirely a substitute for cryptographic analysis, it can be useful at least as a first step in determining whether a pseudo random number generator is appropriate for a particular cryptographic application. The experimental group did not pass a number of tests such as BlockFrequency, Longest Run, Fourier Transform Test, etc., and did not cross the minimum margin line to determine whether it could be used as a cryptographic pseudo random number. Therefore, it can be judged that this data set is very weak to use as a cryptographic pseudo random number.

Figure 8 also shows the results of analyzing this data set with the hex viewer. As shown in Figure 8, it can be seen that 256 cases of 3-byte overlap frequently occur from 0x00 to 0xFF.

Figure 9 shows the result of 2-byte duplication due to the improved algorithm. Even if the first extraction information and the second one are different, if the second and third ones are the same, the remaining 2-bytes are duplicated. When the LSB 4-bit of the first extraction data satisfies a specific condition (if the extraction informations are the same) as the blue part, the rest appears as the red part.

6.1.2. Experiment 2: How Frequent Is This Extraction Vulnerability?

Experiment 2 follows Figure 10. This checks how often the phenomenon shown in Experiment 1 occurs. It extracts 3-bytes from contiguous cipher text with static, dynamic, and improved algorithms, and converts them to decimal. The samples in the experiment are the result of calculating the bit stream that generated by each algorithm from mod ${10}^2$ to mod ${10}^6$ (the range size is increased by 10 times). At this time, and $2^{20}$ samples were examined for each algorithm. For example, converting 3-byte data 0xE7812B of OTP to decimal is 15,171,883, then mod ${10}^2$ result is 83, and possible range is $[0,{10}^2-1]$. Or mod ${10}^4$ result is 1883; the possible range is $[0,{10}^4-1]$. Similar to before, the experimental group is an improved algorithm data set, and the controls are static/dynamic algorithm data sets. Since this experiment is a process of checking the frequency of a specific decimal number after extraction, a pure cipher text sequence is not included in the control group. The results of truncation of the values obtained by each algorithm for digits are summarized in the following

Table 3. Results of Experiment 2: This table shows numerically how often certain numbers occur when the improved algorithm is used.

• Element: A decimal number obtained with each extraction algorithm(static, dynamic, improved)
• Experimental group: Improved algorithm data set
• Control groups: Static/dynamic algorithm data sets
• Sample: $2^{20}$ elements (1,048,576)
• Random variable X: Number of occurrences of each “element” in the range (frequency)
•$E\left(X\right)$: Expected value of X when each “element” in the range is uniformly occur. ($\frac{\sum X_i}{\left|Range\right|}$)
•$MAX\left(X\right)$: The number of ‘most frequent’ element(s) in the range
• Threshold H: Heuristic value that distinguishes each extraction method
• #$(X>H)$: The number of elements whose random variable X exceeds the threshold
• Eccentricity e: Relative measure of how far from normal. ($\frac{MAX\left(X\right)}{H}$)
Range	$\mathit{E}\left[\mathit{X}\right]$	$\mathit{MAX}\left(\mathit{X}\right)$		$\mathit{H}$	#$(\mathit{X}>\mathit{H})$		#($\mathit{X}\le \mathit{H}$)		$\mathit{e}$
$[0,{10}^1-1]$	≈${10}^5$	-		-	-		-		-
		static	10,714		static	2	static	98	1.001
$[0,{10}^2-1]$	≈${10}^4$	dynamic	10,679	10,700	dynamic	0	dynamic	100	0.998
		improved	10,821		improved	10	improved	90	1.011
		static	1151		static	61	static	939	1.046
$[0,{10}^3-1]$	≈${10}^3$	dynamic	1154	1100	dynamic	59	dynamic	941	1.050
		$improved$	$\mathbf{1358}$		$improved$	$\mathbf{256}$	improved	744	$\mathbf{1.235}$
		static	148		static	0	static	10000	0.740
$[0,{10}^4-1]$	≈${10}^2$	dynamic	151	200	dynamic	0	dynamic	10000	0.755
		$improved$	$\mathbf{413}$		$improved$	$\mathbf{256}$	improved	9744	$\mathbf{2.065}$
		static	33		static	0	static	100,000	0.33
$[0,{10}^5-1]$	≈${10}^1$	dynamic	29	100	dynamic	0	dynamic	100,000	0.29
		$improved$	$\mathbf{333}$		$improved$	$\mathbf{256}$	improved	99744	$\mathbf{3.33}$
		static	9		static	0	static	1,000,000	0.257
$[0,{10}^6-1]$	≈${10}^0$	dynamic	8	35	dynamic	0	dynamic	1,000,000	0.229
		$improved$	$\mathbf{320}$		$improved$	$\mathbf{256}$	improved	999744	$\mathbf{9.143}$

.

6.2. Results

The random variable X represents the frequency of occurrence of each “element” of range. Here, element means a decimal number obtained through each extraction algorithm. For this experiment, we collect a total of $2^{20}$ elements and check the frequency of each decimal number. $E\left(X\right)$ is the expected value. If the probability of occurrence of all elements is uniform, the frequency of each element in the range should be distributed equally by $E\left(X\right)$. In addition, if the probability is uniform, the maximum number of element(s) in the range that occur most in the sample, $MAX\left(X\right)$, should not be much different from $E\left(X\right)$. In all ranges, the control group’s $MAX\left(X\right)$ is close to $E\left(X\right)$ and the difference between each control group (static, dynamic) is 5 or less. The experimental group also shows a similar tendency to the control group when the range was less than or equal to [$0,{10}^2-1$]. However, the gap between the experimental group and the control group becomes wider when the range is greater than or equal to [$0,{10}^3-1$]. The $MAX\left(X\right)$ of the experimental group differs from its $E\left(X\right)$ by more than 200 ∼ 300. Similarly, the difference in $MAX\left(X\right)$ between the control group and the experimental group can be seen that the difference is about 300.

Based on the above analysis, we present Threshold H, an experimentally obtained value that can clearly classify experimental and control groups. The samples in the control group appear to be close to the expected values, while the samples in the experimental group differ significantly from $E\left(X\right)$. Therefore, the improved algorithm could be identified from the three algorithms using the threshold values for each range. If the improved algorithm is used, OTP is selected from the reduced set R (|R|$=256$) with a probability of $1/16$, which maps many times to 256 elements. Evidence for this is that the number of elements larger than the threshold (#$(X>H)$) is 256 (in bold), and even one element in the rest of the controls does not exceed the threshold.

6.3. Discussion

Based on this, we define the eccentricity, e, as a relative measure of how far it is from normal, as $\frac{MAX\left(X\right)}{H}$, which gives us the last column in Table 3. The larger the range, the closer e becomes to 0 in the control group, but it becomes larger than 2 in the experimental group. This means that the closer you get to the OTP that people use in real life, the less random the data in the Improved algorithm is. In other words, OTP can provide sufficient randomness because the greater the range, the smaller the uniform probability of the elements that can be mapped. However, when using this (improved) algorithm, the range is frequently reduced, leading to a sharp increase in the probability that certain 256 elements will appear.

Combining Experiments 1 and 2, if an attacker wants to predict the value of OTP using the improved algorithm, the value of OTP can be predicted with probability $\frac{1}{2^8}$, which is much higher than $\frac{1}{2^{20}}$. From the point of view of "Generating secure OTP values", in order to alleviate the problems presented in Vulnerabilities 1 and 2 and Experiments 1 and 2 against them, we recap the solution we proposed.

• Enhance the generation algorithm: When generating an OTP, a cryptographic algorithm that provides security strength suitable for the current era should be used. As shown in Table 2 above, there are methods to use hash functions such as SHA2 and SHA3 that provide 112-bit or higher security strength, or block ciphers such as AES-128,192,256. It is also okay to use standard cryptographic algorithms defined by the country that implements the OTP service;in Korea, LEA-128,192,256, ARIA-128, 192, 256, etc. can be used.
• Use of static or dynamic algorithm: We should not use the improved algorithm. Using this algorithm increases the probability of predicting the value of OTP. In cryptosystems, OTP is widely used because of its advantages; the value is valid only once, has randomness, and can not predict the next value. However, if the values can be easily predicted as in the results of Experiments 1 and 2, the meaning of using this will fade. Therefore, static and dynamic algorithms should be used instead of improved algorithms that eliminate these advantages.
• Increase the amount of extraction to 4-byte: Increase the OTP extraction range. This way, we can also use digits where the number change is not large, so that we can reduce the probability of prediction each time we increase one digit. When the amount of extraction is increased from 3-byte to 4-byte, the range is [0, 16777215] (i.e., $[0,2^{24}-1]$) to [0, 4294967295] (i.e., $[0,2^{32}-1]$, About 4 billion cases). Therefore, OTP can be used up to 7 and 8 digits instead of 6 digits. In this case, since $[0,{10}^7-1]$ and $[0,{10}^8-1]$ can be used, the predictable probability decreases by 1/10 each time by one digit increment.
• Increases the number of LSB digits used as extraction information, and increases the length of the output bit string accordingly: Since 16 offsets can be selected using LSB 4-bit ($2^4$) extraction information, the length of the output bit stream is used as 20-bytes (=16 + 4). Here, adding 4 to the length to be extracted has this meaning. Suppose that when the dynamic algorithm is used, the maximum value that can be expressed in 4 bits is 15.At this time, if 3-byte data is extracted, it becomes $arr\left[15\right]$$\left|\right|$$arr\left[16\right]$$\left|\right|$$arr\left[17\right]$, and if 4-byte is extracted, it becomes $arr\left[15\right]$$\left|\right|$$arr\left[16\right]$$\left|\right|$$arr\left[17\right]$$\left|\right|$$arr\left[18\right]$. If 4 is not added to the length, there is insufficient extraction data and a memory overflow occurs, or the data at the last offset used for extraction information is accessed again. That way, the data is not independent. When LSB is used as 5-bit or 6-bit, it is also appropriate to generate at least 4-byte additionally. In this case, the probability of offset overlapping decreases by $\frac{1}{2}$ each time the bit is increased by one.

7. Conclusions

OTP is used for various purposes such as multi-factor authentication [28]. Although 5G and next-generation cryptography are being studied, it is still a reality to trust and use legacy cryptosystems. However, OTP standards in Korea have not been updated since enactment in early 2010, and even when cryptographically secure algorithms (satisfying security strength) are used in the OTP generation process, the vulnerability can occur as the result of this paper during the extraction process. We presented and analyzed the weaknesses of the OTP system, which is still widely used by many people in daily life. Both the process of extracting a small bit and the process of converting it to a decimal are computing processes included for human convenience. We insist that the processes applied for Human-Centered computing can cause critical defects. We also contributed to reflect on the security perspectives that current OTP systems should consider by providing solutions to address the vulnerabilities we claim. In fact, neither the system was critically attacked by the vulnerability mentioned in this paper, nor did the problem occur. Even so, you should be aware that problems can arise, and you should consider these problems in authentication systems, which are currently vulnerable situations. It is also necessary to revise the standard, and ongoing research is needed to ensure that existing authentication methods such as OTP can be trusted and used; until one of the multi-factor authentication technologies has been replaced.