Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm looking for references, papers or guidance on a class of system which I have not seen widely discussed.

Consider powerful electronic machinery which remains in the custody of communicating parties, is reasonably insulated from tempest-style attacks, and which is not networked. Between tasks its state is completely reset, and includes no secret material such that the hardware may be considered entirely open.

The machinery is used to convert telegraphically-short plaintext to ciphertext (or back again) by means of a large, symmetric randomly-generated key, and the ciphertext is communicated to the recipient non-electronically and without the aid of electronic communications technology, presumably by laborious means (eg writing, semaphore, Aldis lamp). Similarly, keys are not stored electronically, but by some other painstaking means, so must also be as short as humanly possible (eg memory). Identity is not securely established or managed by the system.

If the act of communication were electronic, a default implementation might be to generate a random IV, encrypt the message with a respected symmetric block-cipher in CBC mode, and append an HMAC generated with a well-respected hash function.

However, for such communication to be successful when transmitted more laboriously, size is of the essence, particularly when also padded with ECCs, and with symbols drawn from a small alphabet. Questions I'd like to be more confident on include: what guidance is there for the length of IVs? What threats would be opened up by failing to include an HMAC? Given the vulnerability to errors, what are good approaches (if any) to resynchronization after corruption? What are the principal vulnerabilities and attack vectors of such a system, to the extent that it has been specified (beyond learning the key)?

Systems such as these must have been considered in the literature, but I can find little written about such a set up? Perhaps I am lacking some vital terminology which is thwarting searches? Is the system so simple that there's nothing to discuss?

share|improve this question

closed as too broad by Ilmari Karonen, e-sushi, rath, mikeazo Sep 3 '13 at 14:46

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

How is sending the message via semaphore different from sending it through a modem? Can an adversary observe the message in transit, or tamper with it? – Nick ODell Aug 23 '13 at 0:15
In two ways, Nick. First it is endlessly more painful to do in terms of effort for the communicators, which places restrictions on the specification of the cipher (eg key/nonce lengths, numbers of round-trips). Second, interception (eg in bulk by a foreign power) is also much more effort for an adversary when compared to a method where communication is circuit in a single system. Yes, I believe it's worth considering their ability to observe and tamper. – Dan Sheppard Aug 23 '13 at 1:35
These questions all seem pretty standard, for applied cryptography. Have you read Cryptography Engineering, by Ferguson, Schneier, and Kohno? Or other good textbooks on applied cryptography? They'll tell you about things like how long your IV should be, why you need a message authentication code, how to resynchronize after corruption, etc. You should start by studying what is already known about computer-based systems, then analyze for yourself how they apply to your situation, and come back if there's anything that you can't work out from the standard references. – D.W. Aug 23 '13 at 1:36
I'm really after the neat tricks and dangers that are applicable in a situation like this which I might not get from reading a standard text like Applied Cryptography (which I've read a few times). The very intense pressure on the length of streams, but the very restricted ability for an adversary to inject ciphertexts at a great rate, for example, might admit tricks which are rarely useful in other situations. An example of what I mean (which I do know about) is ciphertext stealing to remove padding from partial blocks. In most situations that would rarely be valuable, but be would here. – Dan Sheppard Aug 23 '13 at 1:56
I've voted this down because I don't think the question/questions have been distilled out of the domain in any meaningful way - hence it is impossible to answer this within known constraints. – Maarten Bodewes Aug 23 '13 at 12:02
up vote 1 down vote accepted

The "tricks" are

Build "arbitrary-size FPE with associated data" by using
S2V$\:\:$($\:\:$master_key$\:\:$,$\:\:$associated_data || plaintext_length$\:\:$)
as the key for format-preserving encryptions with a disjoint domain for each possible $\:$ plaintext_length .


Map pairs $\:\langle$nonce,plaintext$\rangle\:$ into the domain determined
by the plaintext's length via an efficiently invertible injection.


If the FPE decryption gives something that is not in the
range of that injection then the ciphertext is not valid.


Try to keep the nonces secret.
(Encrypting the same plaintext with the same nonce associated data will obviously produce the same ciphertext. $\:$ Thus, if an adversary knows that the same nonce was used and sees the same associated data but different ciphertexts, then the adversary can deduce that the plaintexts were different.
However, if an adversary doesn't know the nonces, then it can't distinguish between that case and the case in which the same plaintext was encrypted with the same associated data but different nonces.)


For any domain $\mathcal{C}_{\hspace{.02 in}n}$ of ciphertexts, with $\mathcal{M}$ the space of plaintexts of the corresponding length
and $\mathcal{N}\hspace{.03 in}$ the corresponding set of nonces, the probability of a single attempted forgery
$\langle$ associated_data , $c\hspace{.04 in}\rangle\;\;$ for $\;\;c\in \mathcal{C}_{\hspace{.02 in}n}\;\;$ being accepted will be $\;\;\; \frac{\left|\hspace{.01 in}\mathcal{N}\hspace{.03 in}\right| \hspace{.03 in} \cdot \hspace{.03 in} |\hspace{.02 in}\mathcal{M}\hspace{.01 in}|}{\left|\hspace{.02 in}\mathcal{C}_{\hspace{.03 in}n}\hspace{.02 in}\right|}+\epsilon \;\;\;\;$.

(Obviously, if there are multiple attempted forgeries, then there will
be a greater probability of at least one of them being accepted.)

Furthermore, even if that probability is large, decryption results will indistinguishable
from being "as close as possible" to independent samples from the distribution
with probability $\:\frac{\left|\hspace{.01 in}\mathcal{N}\hspace{.03 in}\right| \hspace{.03 in} \cdot \hspace{.03 in} |\hspace{.02 in}\mathcal{M}\hspace{.01 in}|}{\left|\hspace{.02 in}\mathcal{C}_{\hspace{.03 in}n}\hspace{.02 in}\right|}\:$ of being a random plaintext of the corresponding
length and with probability one minus that fraction of being rejections.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.