This document is a technical descriptor, providing details relevant to the construction of algorithms within CryptX that were built from the ground up, as well as providing details of hardening measures taken to ensure the library is as secure as possible. This document is provided such that platform-specific components of the library are able to be analyzed and peer-reviewed.

Authors
Secure RNG Construction & Analysis
Rationale & Difficulties

The first question to answer in the quest to devise a secure RNG was does the TI-84+ CE produce randomness, and if so, (1) what is the nature of this randomness and (2) how does this differ by hardware revision. The calculator is unlike a computer in that it lacks many of the dynamic sources of entropy that go into generating randomness for those platforms. I intially intended to use the r register or CPU clock cycle counter, but this was rapidly discarded after I was informed that both of those are predictable. At a loss, and with insufficient knowledge of the device hardware mechanics, I posted on Cemetech seeking information about possible sources of randomness on the TI-84+ CE. Cemetech user Zeroko came to the rescue with data on hardware bus noise.

SRAM has a pair of bitlines for each bit of each column address, which are connected to a circuit that tries to make them both be charged to an equal, high level before reading from a memory cell (which partially discharges one of the two) and to a sense amplifier (basically a comparator) to read the resulting state afterward. (There may also be another level of gating between the bitlines and the comparators, but that does not strongly affect the dynamics.) In the unmapped space, there are no memory cells, so the controller equalizes the bitlines however well it does, then does nothing (there being no memory cell to discharge them), then senses which bitline is at a higher level. For some column addresses, this will be heavily biased one way or the other because the pre-charge transistors on the bitlines are too different, while for others, it will be less biased because they are more similar.
Cemetech user Zeroko, Producing Crypto-Safe Randomness on the TI-84+ CE, May 2021
Source-Selection Algorithm

Based on analysis of the unmapped space, I noticed that there was a very large subset of possible source bytes that appeared entropic and that these subsets differed by hardware revision. After some discussion I decided to construct an algorithm (with optimization support from Adam Beckingham) that would poll each byte in the unmapped space 1024 times and then count the deviation.

As the algorithm proceeds through the unmapped space, it maintains an internal pointer to the most entropic source it has encountered as well as a "value to beat" on the degree of deviation. If the algorithm encounters a better source, it updates the internal pointer and the value to beat. By the time the algorithm finishes polling the unmapped space, it will have selected the best possible source of entropy. That source address is retained by the library for use gathering entropy and cannot be modified by the user.

Should the algorithm fail to find a suitable source (the maximum allowable bias is 75%/25% in either direction), the initialization function will return FALSE.

Entropy-Gathering Algorithm

The RNG internally reserves an entropy pool 119 bytes large in the device’s accelerated RAM. 119 bytes was chosen because it fits nicely within two (2) SHA256 blocks. To generate a random number, each byte in the entropy pool is updated by reading from the selected source byte. The entire pool is then passed through the SHA-256 cryptographic hash, generating a 32-byte digest. That hash is broken into 8-byte blocks, each byte of which is xored together to produce a single byte. The result is a 4-byte compression of the 119 byte entropy pool.

The next thing to prove was whether or not that size of an entropy pool has enough entropy to generate a 32 bit integer. To answer this question we turn to the Shannon entropy formula, which takes as inputs the set of all possible probabilities for an event and outputs the entropy of the event. In this case the "event" is the generation of a single bit from the source. The provided probabilities are the worst-case allowable: 75%/25% in either direction.

Proof of Entropy, Worst-Case

The byte selected for use by the CSRNG will have at least one bit with a maximum bias of 75% (± 25% deviation from 50/50), with the rest of the byte likely having a much higher bias. Therefore I will make the following assumptions:

  1. A single bit in the source has probabilities .75 and .25 for the set of two possible outputs (0 or 1).
  2. The rest of the byte has zero entropy.

$$ H(bit)=\sum_{i=1}^nP(i)\log_2\frac{1}{P(i)} $$

In the formula above, n is the length of the set of probabilities, i is an iterator, and P(i) is the probability of the i-th element in the set.

$$ H(bit)_{min}=0.750\log_2\frac{1}{0.750}+0.250\log_2\frac{1}{0.250}=0.811 $$

This is the entropy of a single bit, but because we are also assuming no entropy in the rest of the byte, we can use the same value for bytewise entropy.

The final step is to multiply that value by the number of bytes in the entropy pool.

$$ H(pool)_{min}(119)=0.811\times119.0=96.51 $$

This means that the entropy pool yields 96.51 bits of entropy per 32-bit number generated, which is more than enough.

Mitigating Correlation in the Source

Due to the nature of the CE hardware, there is a measurable correlation in the values of floating bits within unmapped memory. This correlation varies depending on the sample size, but would measurably reduce the entropy of the system. While specific numbers on the degree of correlation are, as of yet, unavailable, we do know that there are higher amounts of correlation in the initial reads which decreases after a certain number of reads. Zeroko provided a more technical explanation of this as well.

Another source of non-randomness distinct from the bias is that the bitlines act like capacitors, so precharging only moves their voltage toward the desired level rather than reaching it. This results in a correlation between reads, with the correlation getting weaker with a longer time interval between them and with more intervening reads performed. This is why we cannot just use a von Neumann extractor (which only de-biases) and instead have to do something like XORing many consecutive bits together (which does not fully remove the bias and correlation but can lower it to an undetectable level).
Cemetech user Zeroko, Producing Crypto-Safe Randomness on the TI-84+ CE, May 2021

To solve this problem, Zeroko performed some analysis on the unmapped memory and revealed that XOR'ing seven (7) reads together per byte would be sufficient to trend the actual entropy closer to what is calculated above.

Note that these security proofs only apply to physical hardware (an actual TI-84+ CE), not to emulators. Emulators tend to use a deterministic RNG to reproduce the behavior of unmapped memory for the sake of speed and therefore sacrifice unpredictability.

Side-Channel Analysis

Side-Channel Analysis is defined as an attack vector that can defeat cryptography by utilizing weaknesses in the hardware that, in conjunction with how the algorithm is written, can leak information about the secrets or data. Timing information, power use, electromagnetic leaks, and sound are examples of information leaked by a device that can help a knowledgeable attacker break cryptography. Citation: https://en.wikipedia.org/wiki/Side-channel_attack

Timing Analysis Protection

One of the first considerations in this library was resistance to timing analysis. While the complete library group has not been thoroughly reviewed for timing analysis, here is what we do know:

As the library is under constant review with the aim of enhancing security, over time its resistance to timing analysis may improve and more data will be published here.

Buffer Leak Protection

Another consideration taken was to avoid leaving residual computational data in the stack frame after a function that performs data transformations completes. For this reason, some code was written that purges the stack frame and we call that code in most of the user-facing encryptor functions before returning control to the caller. For reference, the code used to accomplish this is:

Stack purging code. by Zeroko 

?stackBot := 0D1987Eh
stack_clear:
; backup hl, a, and e
	ld (.smc_a), a
	ld (.smc_hl), hl
	ld a, e
	ld (.smc_e), a
; set from stackBot + 4 to ix - 1 to 0
; ix points to the current top of stack frame
	lea de, ix - 2
	ld hl, -(stackBot + 3)
	add hl , de
	push hl
	pop bc
	lea hl, ix - 1
	ld (hl), 0
	lddr
; restore a, hl, e
	ld e, 0
.smc_e:=$-1
	ld a, 0
.smc_a:=$-1
	ld hl, 0
.smc_hl:=$-3
	ld sp, ix
	pop ix
	ret
Memory Mapping Protection

After resolving buffer leaks, our attention turned to thwarting attempts to map the device’s memory while CryptX is running to gain information about the encryption or decryption. While there is sufficient difficulty in achieving this on a device designed to be used in that manner in other contexts, I believe the solution arrived at is sufficient.

It is the system interrupt that makes it possible for the operating system to handle activity on the USB port, and disabling said interrupts would severely hamper attempts to read CryptX’s state by preventing the system from responding to USB transfers. For this reason, some code was written that disables interrupts in all functions where data is being encrypted or decrypted, saving their state to SMC, and restoring that state afterwards. While there are many variations of this code that operate in slightly different ways depending on when they are called, here is the basic version of it, for reference:

Save/disable interrupts, restore interrupt status. by Adam Beckingham 

; helper macro for saving the interrupt state, then disabling interrupts
macro save_interrupts?
	ld a,i
	push af
	pop bc
	ld (.__interrupt_state),bc
	di
end macro

; helper macro for restoring the interrupt state
macro restore_interrupts? parent
	ld bc,0
parent.__interrupt_state = $-3
	push bc
	pop af
	ret po
	ei
end macro
Algorithmic Security
CPA Resistance

CPA is an acronym for chosen plaintext attack, a type of attack against an encryption algorithm that involves an attacker gaining information about the secrets (keys) used for encryption by requesting encryptions of arbitrary plaintexts. The simplest way to explain this is to liken it to a system of multi-variable algebraic equations. With only one equation in the system it is unsolvable but if you begin to add more equations, suddenly it becomes possible to solve for and even eliminate variables. In a similar manner an encryption system with perfect secrecy can still be completely broken by a chosen plaintext attack, although the methods of doing so are vastly more complicated than merely "solving a system of equations".

All of the encryption functions in CryptX facilitate CPA security by allowing for the inclusion of a random oracle in the encryption. A random oracle simply means a string of unpredictable random bytes. In other places you may also hear or read the terms salt or nonce. These mean the same thing. In AES the randomness is included through the use of an initialization vector, a buffer equal in size to the AES block size, filled with random data. In RSA, the randomness is added via the optimal asymmetric encryption padding scheme (OAEP) which xors the entire message with a salt using a Feistel network.

CCA Resistance

CCA is an acronym for chosen ciphertext attack, a type of attack against an encryption algorithm that involves an attacker gaining information about the secrets (keys) used for encryption by requesting decryptions of arbitrary ciphertexts. The objective of the attacker is the same, to ”solve” for the encryption secret by requesting decryptions of chosen ciphertexts until characters of the key are revealed. However, because CCA works backwards to CPA, the random oracle that provides CPA security does not help us here. CCA security requires some form of authentication integrated with the encryption.

Typically authenticated encryption is accomplished in one of two ways: (1) using a specialized encryption cipher mode that produces an authentication tag in parallel with the encryption and a specialized decryption cipher mode that can validate this authentication tag while decrypting, or (2) appending a hash or keyed hash to the message that is validated BEFORE decryping the message. The former method is generally considered to be more secure but is also more computationally intensive. For this reason, CryptX provides an API for the latter. A series of rules for properly constructing an authenticated encryption scheme using the included hash and hmac implementations can be found in the documentation section for ENCRYPT. It will be on the user to follow the rules properly, or their implementation may be insecure.

Concluding Notes

In summation, CryptX is a work-in-progress and sees regular updates that add resistance to various forms of attack. While its algorithmic security is solid if implemented properly, hardware-based attack is harder to defend against due to the nature of the hardware. Thus far, some significant actions have been taken to secure the library against hardware-based attack and the source code is publicly available on forums frequented by others familiar with the CE’s hardware and is under continuous peer-review with the aim of continually improving the library’s security profile.

If you have any questions about the proper usage of CryptX in your programs, any of its functionality, algorithms, etc, please do not hesitate to contact me on Discord at acagliano#3685. I would rather you ask questions than implement security improperly and risk compromising your implementation.

Please update to new stable releases of CryptX as soon as they become available and update any software you are developing to use the latest versions as soon as you are able. At this stage in CryptX’s development, updates are security enhancements, not major feature additions.

References
  1. https://github.com/B-Con/crypto-algorithms/
    Reference for AES and SHA-256 algorithms initially ported to platform.

  2. https://www.cemetech.net/forum/viewtopic.php?p=293090#293090
    Source of information on randomness on the TI-84+ CE.

  3. https://en.wikipedia.org/wiki/Cryptographically-secure_pseudorandom_number_generator
    Information on constructing a secure PRNG.

  4. https://datatracker.ietf.org/doc/html/rfc8017
    Guidance on implementing RSA-OAEP and RSA-PSS padding schemes.

  5. https://datatracker.ietf.org/doc/html/rfc4868
    Guidance on implementing SHA-256 HMAC.

  6. https://github.com/kokke/tiny-ECDH-c
    Reference implementation for Elliptic Curve Diffie-Hellman.

  7. Modern Cryptography and Elliptic Curves, A Beginner's Guide. Thomas R. Shemanske.
    Reference for learning elliptic curves.