OpenSSL supports AES, Camellia, ChaCha. How about Twofish, Threefish, Serpent? If I understood correctly, some symmetric ciphers such as AES, Camellia, ChaCha are implemented in OpenSSL (along with several older ones) but some other commonly used and proven ciphers such as Serpent, Twofish and Threefish are not.
Any way or chance of these being supported by OpenSSL as well?
Or is there another de facto encryption tooling (with comparable solid reputation as OpenSSL) that implements these ciphers?

AES is the main block cipher in use today, standardized by NIST. Camellia is a Japanese standardized cipher. ChaCha is a fast stream cipher specified by Bernstein and incorporated into TLS with support from Google.
Serpent and Twofish were AES last round candidates that didn't make it. Serpent is not that fast, and Twofish is relatively fast but not compared to AES when hardware acceleration is used. Both are block ciphers that are really not needed as long as we deem AES to be secure.
Threefish was mainly designed for the Skein hash function. This tweakable block cipher is not used much. It Skein had been chosen as SHA-3 then it would have stood a better chance. For now an authenticated form of Keccak would make more sense.
So yeah, two standardized ciphers and a fast stream ciphers are supported, none of which are broken. There is no reason to include the also-ran's and a cipher made specifically for a hash function which was also not standardized.


Can we trust digital signatures? Consider that Alice wants to send a digitally signed message to Bob.
Mallory might be able to publish his public key under Alice's name and then impersonate Alice to send a message with an apparently valid signature.

But let's assume that Bob already has received Alice's correct public key.
Can Mallory still send a fake message with a valid signature using more advanced methods?

Consider the following situation:
Bob knows Alice's public key.
Alice private key is secret and only known to Alice.

Mallory doesn't have Alice's private key, but he knows her public key.

Alice now sends the signed message "today is my birthday".
Mallory wants to change that message to say "tomorrow is my birthday".
Mallory and Alice know What is message: "today is my birthday".

Can Mallory find a way to send his fake message without Bob noticing, i.e. with a valid signature.

Could Mallory somehow compare the hash value of "today is my birthday" and the signature generated by Alice and learn from that how to generate a valid signature of "tomorrow is my birthday" under Alice's public key?

For the first part of your question: Yes, if Mallory manages to publish his own public key under Alice's name, then there is really nothing to stop him.
This problem is addressed with public key infrastuctures and public key certificates.

That is, for Bob to believe that the public key is Alice's key, Mallory would need to have a trusted third party attest, that that's the case. As the third party is assumed to be trusted, she obviously wont attest to that false statement.

Once we've got that problem out of the way, then no, as long as you use a secure signature scheme, it is not possible for Mallory to forge a signature on any message not already signed by Alice herself.

The usual security requirement for a signature scheme is existential unforgeability under chosen message attacks.
That means, Mallory can ask Alice to sign any number of messages of his choosing and he still wont be able to produce a single message signature pair, where the message has not already been signed by Alice herself.

What Mallory would need is an even stronger forgery, namely a selective forgery, because he chose the message to forge a signature for, before he even started the attack.


Testing implementation of cryptography algorithms: Brainstorm I wonder what kind of techniques can be used to validate implementation of cryptography algorithms?

The obvious one is to run specific algorithms against publically known test vectors (i.e. from NIST). Other idea would be to run it against some tool for fuzzing like AFL.

Would you have any other ideas, tools? How would you test against side channel?

My own algorithm validation for block ciphers consists of the combination of the AESAVS KAT and MCT tests from the NIST CAVP, plus the NESSIE test vector sets, plus an additional MCT of 400 key changes and 10000 inner loops (like the TDES tests). The probability of a block cipher passing all these tests but failing in production is astronomically low.

Once I have generated an entire set of test results, the file is hashed and compared to a known good hash. Each test set is hashed individually. That way I do not need to compare each of the 1000s of results individually. For a complete validation, each result MUST be compared individually.

Stream ciphers are tested similarly, a variety of keys/nonces are used, outputs are generated, and sections of the output are compared against the known answer. Additionally, the entire output can be hashed and compared, although this is slower.

There are also implementation tests, where data is passed to the algorithm that should not be passed, such as invalid key and block sizes. These are necessary to test against fault and overflow attacks, but do not test the algorithm itself.

For hash functions there are similar NIST validation systems in place, one for the SHA1/2 families, which can be applied similarly to other MD type functions like Blake and MD5. This is in addition to the "health test" checks which process about a dozen values of known size and compare the outputs.

SHA3 has a similar validation system, which can be applied to Keccak and other sponge based hash functions.

ECCDH validation is routinely done by KAT and MCT testing, the NIST test only uses 24 KATs. X25519 sometimes (depends on implementation) uses a MCT with 10000 operations, and a short list of KATs.

Other algorithms use similar tests. HMAC testing for example assumes the hash function being used already passed its component test, so the HMAC test is really only testing the HMAC implementation and not the hash function.

Of course, none of these are testing for side channels. Some algorithms have been designed to be free of cache timing and power analysis side channels, but only if they are implemented precisely as designed. A 32-bit integer implementation of X25519 will not be free of side channels. Side channel testing is usually targeted at specific algorithms and implementations, and there is not a one-size-fits all method.


Number of states in a LFSR Do all $2^{\ell}$ (where $\ell$ is the bit length of the shift register) states always occur in a LFSR or can I choose my taps badly so some states are skipped and the period is shortened?

If so is there a way to prove the number of states that can occur in a LFSR?

As fgrieu points out, the number of states reached is at most $2^\ell-1$ and that is achieved only if the feedback polynomial is a primitive polynomial (and the initial state is not all
zero). If the feedback polynomial is irreducible but not primitive, then with
nonzero initial loading, the LFSR state will cycle through $N$ states, where $N$ is a
divisor of $2^\ell-1$ but not a divisor of $2^m-1$ for any $m$ that is itself a proper divisor
of $\ell$. For example, if the feedback polynomial is an irreducible but nonprimitive polynomial of degree $6$, then, depending on which polynomial is being considered, the
LFSR will cycle through $21$ states, or through $9$ states. The $63$ nonzero states
form $3$ cycles of $21$ states each, or $7$ cycles of $9$ states each. Depending on
the initial loading, the LFSR will cycle through one of these cycles (and the other
cycles will never occur).

For an arbitrary feedback polynomial, which could be reducible, that is,
factorable into a product of (not necessarily distinct) irreducible polynomials
(meaning something like $[f(x)]^2g(x)$ might be the factorization),
the answer is much messier and complicated to describe. Search for the
term period of a polynomial and read Lidl and Neiderriter's Finite
Fields or Chapter 6 of Berlekamp's Algebraic Coding Theory for some
of the details.


Calculating the point on the curve during ECDSA signature verification I'm confused as to how he got (62, 44) as an answer within this article: https://www.coindesk.com/math-behind-bitcoin

To obtain (62, 4) you just add points $\textbf{but on elliptic curves}$.
This is different from a "regular" addition, since the result must be a point of the curve (or a point said to be at infinity, I'm not explaining I try to keep things simple) .
Addition is defined and to do so either you use the heavy addition formulas (If you have seen groups theory), either you do as explain in the coindesk article :
let $P$ and $Q$ be two points on the curve
to do  $(P) + (Q)$ you trace the line passing by both $(P)$ and $(Q)$.
This line will intersect the curve on a third point, call it $(R')$, then $(P) + (Q) = (-R')$  and you have your result,
i.e. if $(R') = (x, y)$ then $(-R') = (x, -y)$. (In the coindesk article $(-R') = (R)$)
This is an $\textbf{incomplete}$ explanation but you should catch the thing, I didn't discuss the special points (when the last coordinate's member is $0$), inflexion points (when $P = Q = R$), or why there is another point on both the line and the curve.
If you want to double a point $(P)$ you trace the tangent passing by $(P)$, and this tangent will pass by a second point on the curve and you take the opposite point.
Personally I never use the explicite formulas (I didn't write them here) , which are too heavy in my opinion, I just do it with the last method.
For the first part you just break $76G$ in additions and doubles of $G$. Then you replace $G$ by its coordinates $(2, 22)$ and you just double or add.
For example: $2.(2, 22) = (2, 22) + (2, 22) = (52, 7)$ using your curve.
To check your results, or to get it easily, you can use : http://christelbach.com/ECCalculator.aspx an online calculator for elliptical curves.
You just have to set the parameters of your curve ($mod p = 67$, $A = 0$, $B = 7$) and you will get the correct answer (I checked).


Is pseudorandom function also a one-way function? Can I assume this? Specifically, I want to know if the following two cases are valid. Suppose $prf_k(m)=c$

One-wayness: Only given $c$, we cannot reveal $m$.
Without key $k$, even given $m$, cannot get $c$.

They seem intuitive, but I want to be assured of their validity when I say that. Is a pseudorandom function also a one-way function?

(Note the OP's clarification that even for 1, the adversary does not have the key k.)

Yes. $\:$ The way to show anything like those, is to use the fact that oracle access to prfk

is sufficient to efficiently determine the extent to which an adversary is violating those.

def straight-line_reduction_1_():
 m = random_element_of_(domain(F))
 query F on m
 let c be the output of F on m
 send c to inner_adversary_1
 forward any queries and responses between inner_adversary_1 and the F oracle
 let guess be the output of inner_adversary_1 on c
 if guess == m:
  return True
 else:
  return False

straight-line_reduction_1_ uses only a small amount of space and makes only one more oracle query than inner_adversary_1, and straight-line_reduction_1_'s runtime is dominated by forwarding queries/responses from/to inner_adversary_1.  (So, straight-line_reduction_1_

is efficient.)  For all F, the probability of straight-line_reduction_1_ outputting True is equal

to the probability of inner_adversary_1 correctly guessing m given c.  However, if F is a

truly random function and inner_adversary_1 makes at most q queries, then the probability

of inner_adversary_1 correctly guessing m given c is at most (q+1)/(cardinality(domain(F))).

(That should be proven, but I'll only bother doing so if you ask.)

Given that result (which I didn't provide a proof of), it then follows that the probability of inner_adversary_1 correctly guessing m given c by making at most q queries is at most (q+1)/(cardinality(domain(F))) plus the extent to which the combination of inner_adversary_1

with straight-line_reduction_1_ distinguishes the function family from random.

In particular, if the function family is pseudorandom then 1 holds.

One can proceed analogously to show that

if the function family is pseudorandom then 2 also holds.


Using e-ID Number for Encryption and Digital Signing I want to use e-ID number for performing Encryption/Decryption and Digital Signing - and in order to do so, I've opted a PGP-oriented approach which goes a bit like this.

Generating PGP key-pair using e-ID Number (pass-phrase protected)
Digital Signing using e-ID Number (private-key) - and verifying the signature legitimacy by matching the sender's e-ID public-key fingerprint/key-id which has been pre-shared (via telephone/meeting) with the recipient.
Encrypting using e-ID Number (pre-shared) public-key of the recipient - and will then be Decrypted by using his/her private-key.

There will be a use of 'Random Session Key' for each session - as per the PGP concept and the implementation of classical (RSA, Elgamal) for Encryption/Decryption and (RSA or DSA) for Digital Signatures will be realized.

This is still a quite rogue approach - and therefore I would like you to share your view-point concerning the feasibility and the possible weaknesses of such a mechanism.

I will also appreciate other possible (effective) ways to use the e-ID card features for performing the Encryption/Decryption and Digital Signing - excluding the fact that card's electronic chip itself is equipped with a key-pair (by the reason of not being supported/compatible/encouraged for encryption and just for digital signing).

The number of your ID card is not really a secret, and probably shouldn't even considered one. You could use it as a key for symmetric encryption (but for this purpose you'd have to share it with your communication partners, and everybody knowing the ID could read the communication), but not for public/private key cryptography.

This is the reason why the cards often are (or can be) equipped with public/private key pairs, at least when they provide any cryptographic features.

An interesting way to work around the fact the basic key pair stored on the card is not really released to general usage is available for the German "Neuer Personalausweis" (the digital ID card issued for some years now): you can use the card to prove your identity to an OpenPGP key signing service (German website), which again will sign your key as certificate authority.

  Generating PGP key-pair using e-ID Number (pass-phrase protected)

Specifically discussing this point: If you want to use the card's identifier for generating the key, be aware that likely the key space is much smaller than necessary, which will heavily reduce the key's security. Brute-forcing the key might boil down to simply enumerating all possible IDs (which might be made harder using repeated hashing like often done for passwords). Also, everybody getting hold of the ID will be able to calculate the key without problems: the government, possibly also private entities getting hold of your ID card for verification purposes (hotels, airlines, ...).


Are there any additively homomorphic encryption schemes over $\Bbb Z_2$ besides Goldwasser-Micali? I am aware of Goldwasser-Micali cryptosystem, which is additively homomorphic over $\Bbb Z_2$.
Are there other schemes that satisfy this property?

Note: If one is willing to involve advanced tools like lattices one could get something stronger like FHE. I am looking for a simple cryptosystem not involving lattices or similar tools.

Any additively homomorphic encryption scheme (with a large enough message space), e.g. Paillier. To do so, let the message space of the homomorphic encryption scheme be $\mathcal{M}$, you encode your message space $Z_2$ as follows:

choose an even number from $\mathcal{M}$ to represent 0, and an odd number to represent 1. One obvious choice would be simply 0 and 1. Let's call the two $m_0$ $m_1$ respectively

To encrypt, you encrypt $m_0$ or $m_1$ (all other messages are not allowed) using the homomorphic encryption scheme as usual.

To do homomorphic operations, you do the homomorphic operations as usual.

To decrypt, you decrypt as usual, then take mod 2 on the result to get your final result.

Here the parity of the values encodes messages in $Z_2$: even corresponding to 0, and odd corresponding to 1. We know

odd+odd $\rightarrow$ even (1+1=0 mod 2)
odd+even $\rightarrow$ odd (1+0=1 mod 2)
even+even $\rightarrow$ even (0+0=0 mod 2)
even+odd $\rightarrow$ odd (0+1=1 mod 2)

Thus it is correct.

The message space needs to be large enough so you can do enough number of addition operations without overflow (0 and 1 is actually the best choice to maximize the number of operations you can do).


k(k-1)/2: Combinations and the Birthday bound Disclaimer: I'm new to cryptography.

Background: I'm reading Cryptography Engineering by Ferguson, Schneier, and Kohno, where, in Chapter 2, the authors write this:

Question: What is $k(k-1)/2$ called? It seems related to an arithmetic sequence $a_n = a_1 + (n-1)d$ and some kind of combination (my notes below), but I can't place it.

$k(k-1)/2$ is usually called a binomial coefficient and written $k \choose 2$. It corresponds to the number of unordered pairs of distinct elements out of $k$ elements. It does indeed correspond to the sum ${k \choose 2} = \sum_{i=1}^{k-1} i$. This is quite intuitive: fixing one element, you have $k-1$ pairs containing this element. Now remove it, consider a second element: you have $k-2$ pairs with this second element, and so on. At the end, you get $(k-1) + (k-2) + \cdots +2 + 1 = k(k-1)/2$ pairs.

your bottom right formula is the general formula for ${k \choose r}$.


How close is homomorphic encryption to handling regular expressions? Is there any reasonable homomorphic encryption protocol that supports some meaningful fragment of regular languages/expressions and/or edit distance bounds?

I'm suspicious that homomorphic encryption never handles this sort of "insert bounded amount of arbitrary garbage", but maybe a subset of regular expressions with various bounds, or perhaps up to some bonded edit distance.

This question came up in a discussion about CryptDB.

In general, it seems that right now, searching on encrypted data is still quite limited. Besides CryptDB, SADS is another that I have seen. Without knowing more about your security requirements, however, it will be hard to say exactly (e.g., is the regex kept private or is only the data that it is being matched against kept private? Is there a trusted third party? and so on).

Personally, I have never seen a system which allows full regex searching of a dataset where either query or data is kept private. The best I have seen is keyword matching with AND and OR boolean logic (see SADS). Phase II of the DARPA PROCEED program looks to some sort of regex searching capability. Depending on how successful that phase is, we might have something a year from now.

As a side note, from the little I actually understand about fully homomorphic encryption (FHE), it would seem that a fully homomorphic system could perform this type of search. FHE systems are currently not that mature, however, as researchers are still trying to figure out how to make them practical.


Cryptographically secure linear congruential generator - is it possible? Let's consider generator:
$x_{n+1} = (a \cdot x_{n} + c) \mod m$
And let's assume we will meet three requirements known as Hull–Dobell Theorem. Also consider only $m=2^{i}$ (then $c$ has to be odd).
Now let's consider $a$, $c$ and $x_{0}$ are 256-bit keys ($c \neq 0$). Could this generate secure pseudorandom numbers? Wikipedia says: if $m$ is a power of $2$, then $a−1$ should be divisible by $4$ but not divisible by $8$. Let's say we will meet also this requirement. By the way what will happen if we will not?
Are there any other problems which can make such a generator insecure? Is there also requirement that $a−1$ can't be divisible by $16$, $32$ and so on? Anywany it is not a big problem to choose $a$ this way.

Public m private a,c
If the attacker gets some $x_i$ in sequential
\begin{align}
x_{i+1} &= a \cdot x_{i} + c &\bmod m\\
x_{i+2} &= a \cdot x_{i+1} + c &\bmod m\\
\end{align}
Then subtracts the two
$$x_{i+1} - x_{i+2} = a ( x_{i} - x_{i+1})  \bmod m$$
this will lead to the exposition of the $a$, the rest is there.
In short the next-bit test is failed.

By the way what will happen if we will not?

No maximal period!
Private m,a,c
The attacker still can recover the $m$ then the rest as following D.W.'s steps;
Define a new sequence $t_n = x_{n+1} - x_{n}$ and with some operation;
$$t_{n+1} = x_{n+2} - x_{n+1} = a x_{n+1} + b - a x_{n} -b = a x_{n+1} - a x_{n} = a t_{n} \bmod m$$
So we have $t_{n+1} = a\cdot t_{n} \bmod n$, then we have $t_{n+2} = a^2\cdot t_{n} \bmod n$ and $t_{n+i} = a^{i}\cdot t_{n} \bmod n$. From this one can notice that $$t_{n+2}\cdot t_n - t_{n+1}^2 = 0 \bmod m,$$ i.e. $|t_{n+2}\cdot t_n - t_{n+1}^2|$ is a multiple of $m$
Now call $U_n = |t_{n+2}\cdot t_n - t_{n+1}^2|$ and consider $\gcd(U_i,U_j)$ where $i \neq j$
Now, we will use a fact that Dirichlet showed in 1849

The probability of two random numbers being relatively prime is $\frac{6}{\pi^2}$

Consider two multiples $k$ and $\ell$ of $m$, then there are $u$ and $v$ such that $k = u \cdot m$  and $\ell = v \cdot m$. This will turn the question of $\gcd(k,\ell) = m$ to $\gcd(u,v)=1$ and this is the Dirichlet's result. If you are lucky with 5 outputs from LCG to from two $U_i$ than with $\frac{6}{\pi^2} = 0.607927101854027$ you will find $m$. If you have more output, you can calculate $\gcd(U_i,U_j,...,U_r)$ to increase to finding probability close to 1.


Is it practical to use a stream cipher in a block cipher mode? My idea is to use a stream cipher encrypting 16 bytes at a time as a primative block cipher in a mode of operation such as CBC mode.  Is this practical or useful in any way?

The way you propose to use a stream cipher as a drop in replacement for a block cipher is flawed, as the other answer explains nicely.

There is a simple way to convert a stream cipher into a block cipher. In pact, it works for any PRF, regardless of if it is reversible or not.

This presentation perfectly covers how to use a PRG such as a stream cipher to construct a block cipher.

Basically, you use the stream cipher in the following manner:

Take your message m and break it down into an n-bit binary string.

Take your stream cipher $G(k)$ and use it to generate a a stream of length $2 · |k|$. So $G(K) \to K^2$ (output space = double that of keyspace).

Do $k \to G(k)[0]$ and $G(k)[1]$, pick $G(k)[x]$ depending on what the first bit of m is.

Then, compute $G( G(k)[x] )$. You have a message of length two blocks, pick the block corresponding to the second bit of m. Repeat n times.

This can be reversed (decrypted) in the same way Feistel networks are, via the Luby-Rackoff theorem.


Are there any well-known examples of SHA-256 collisions? The popularity of SHA-256 as a hashing algorithm, along with the fact that it has 2256 buckets to choose from leads me to believe that collisions do exist but are quite rare.

Are there any well-documented SHA-256 collisions? Or any well-known collisions at all? I am curious to know.

I find that showing collisions to people I'm explaining hashing to is a great way to show them what non-invertibility means when they have a hard time seeing how the modulo_x operation relates to the SHA-256 operation.

No, there is not any known SHA-256 collision. Publication of one, or of a remotely feasible method to obtain one, would be considered major.

It is next to impossible that two distinct strings with the same SHA-256 have been computed so far. The most visible such computation is in bitcoin mining. By summing this data giving history of SHA256d hash rate (that's two SHA-256), I get that by end of April 2018 that had made 289.7 SHA-256, with the exponent growing roughly by 2 per year for the last few years. My computations, and opinion that they represent the bulk of SHA-256 made, have not been challenged there. Extending to 291 to account for other cryptocurrencies and (perhaps coverts) password search activity, odds are about 1 against 2256+1-91-91 = 275 that a collision occurred (see Birthday problem for cryptographic hashing).

For the purpose of illustrating collisions, perhaps make an example with SHA-256 restricted to its first 64 bits (16 hexadecimal characters instead of 64), and explain that each 2 bits added doubles the expected number of hashes before a collision occurs.


ARC4random – ChaCha-based LibreSSL PRG Here is arc4random.c from the LibreSSL pseudorandom generator as used in OpenBSD.

It works as follows:

Take 40 "truly random" bytes from OS (PRG seed);
Use the seed as key and IV to generate 1024 bytes of ChaCha keystream;
Use the last 984 bytes of the keystream as a PRG output, and the first 40 bytes as the key and IV to generate the next 1024 of ChaCha keystream;
Repeat until the total number of keystream bytes exceed the limit; after that reseed (go to the step 1).

I don't quite understand the purpose of the step 3 (see the lines 135-138 of the linked code):

/* immediately reinit for backtracking resistance */
_rs_init(rsx->rs_buf, KEYSZ + IVSZ);
memset(rsx->rs_buf, 0, KEYSZ + IVSZ);
rs->rs_have = sizeof(rsx->rs_buf) - KEYSZ - IVSZ;

Why isn’t the whole keystream as a PRG output used? Why does the "rekeying" step make the PRG more secure?

This is to prevent two different types of attacks.

Bias attacks. It may in the future be that ChaCha20 is broken like RC4 is and that you can recover the secret key (or something equivalent) only given enough parts of the keystream. By re-keying often enough you can limit the length of the keystream for each given key, rendering those attacks impossible.
State recovery attacks. Assume an attacker learns the state of the PRNG at some point in time. Now while he can still predict future bits, he won't be able to predict past bits beyond the last re-key, because the key needed to do this is gone and you can't recover it from the current key (if you could you could passively recover the key from a short fragment of the keystream).


Replay attack resistant MAC? I came up with a threat model where:

Alice and Bob agree on a shared key $K$
Alice sends a plain text $M$ and its $\operatorname{MAC}$ tag, $T = \operatorname{MAC}(K,M)$ to Bob over an untrusted network
Eve collects pair of $M$ and $T$, thus mount a replay attack

First of all, I am curious whether my threat model is reasonable.

Is it possible for Eve to collect a pair of $M$ and $T$, thus mounting such an attack?

Given that, is there any replay-attack-resistant MAC scheme that is widely used?

A plain MAC algorithm acts as a deterministic function of the key, message, and (maybe) a nonce. Every time you evaluate the function you get the same results. Mathematical functions do not know whether or not they're being evaluated for the first time.

Replay attack protection has to be employed at the level of the protocol. Software, not math, is necessary for this task. The maintenance of state is a necessary and critical part of the problem. (Including issues like keeping state after losing power, as well as ensuring atomicity and consistency when you have multiple endpoints or system-level concurrency.)

The best method to prevent replay attacks is to include a sequence number in the messages you're trying to create a tag for. (You might not need to explicitly send this over the network, though. That might be redundant.)

Prepend a fixed-width counter to all messages. Maintain a value n shared between the client and server. Every time a message is received, check that the message's sequence number is the value (n) which you expected. Look for n == 0 on the first message, n == 1 on the second message, and so on. If you receive a message with the correct sequence number with a valid tag then increment n. If you receive a message with an invalid tag or with a sequence value that you've already seen, then reject that message.

This method additionally protects against a man-in-the-middle's attempts to reorder or block messages. You don't want for an attacker to be able to change a message sequence ["On", "Off", "On"] to ["On", "On", "Off"]. Or to just ["Off"].

To illustrate how a sequence number solves that problem, imagine that the sender instead transmits the sequence ["1:On", "2:Off", "3:On"]. It should be obvious how repeated or reordered messages could be detected with only O(1) memory. Attempts to selectively block messages can (partly) be detected by looking for skipped sequence numbers.

(Although some protocols replace server-side checks for seq == n with seq >= n. Car key fobs, for example, might do this, since the user might be out of signal range when they press a button. If this method is employed, then it is important that all commands sent in a protocol are idempotent and that the user can tell what state the system is in. You can have "Lock" and "Unlock" commands, but not a "Toggle lock" command. For car key fob systems, a car should beep or flash its lights when locked.)

Attempts to block the last message(s) sent in a session can't be detected by looking for skipped sequence numbers, obviously. It's necessary to add a "End transmission" message (or message flag), since you can't distinguish between an incomplete session and a maliciously cut-off transmission otherwise.

A worse method to prevent replay attacks is to require the client to attach a random nonce to every MACed message. But then the server has to make more effort to track which nonces have been used. If the server sees a nonce it has already seen before, then it rejects the (replayed) message.

This kind of system lets you add idempotency to a system which wouldn't otherwise have it. This same method is used in web applications to prevent accidental doubly-posted messages. If a user has network issues, accidentally hits the refresh button, or hits the back button and resubmits a form, then the server will notice the reused nonce and ignore the re-submission.

This method does not detect reordered or selectively blocked messages. This is okay for the other accidental-double-post-detection system because blocked messages are not considered a realistic threat. Out of order posts are accepted as a "feature": The user can open two tabs, compose two messages separately, and submit the posts in whatever order they complete them in.

You could use it in other scenarios with out-of-order protocols, but it's tricky to get right. So it's not worth the risk or the extra investment in developer time.

An additional problem is that the "spent nonce" database can grow indefinitely large. A modified system could incorporate a timestamp into the nonce, allowing old records to be purged if a timestamp check is added.

You basically ONLY would opt to use this method instead of using sequence numbers if you have a powerful stateful server and low-end stateless clients. (Clients without non-volatile memory.)

Those (stateless) clients need a TRNG, because long random numbers are used to avoid accidentally reusing nonces. (Leading to false positive replay detection.)


Why can't you divide by 0 in an Edwards Curve? The equation of an Edwards curve is $x^2 + y^2 = 1 + d x^2 y^2 \,$

The addition formula is $(x_1,y_1) + (x_2,y_2) = \left( \frac{x_1 y_2 + x_2 y_1}{1 + dx_1 x_2 y_1 y_2}, \frac{y_1 y_2 - x_1 x_2}{1 - dx_1 x_2 y_1 y_2} \right) \,$

Why can't you divide by zero when you have a non-square d?

What is the intuitive explanation that $dx_1 x_2 y_1 y_2$ can't be equal to ± 1 when d is a non-square? Because I don't see why you can't have $x_1 x_2 y_1 y_2 = ± \frac{1}{d}$

Claim:

Both denominators can never be zero if $d$ is not square in $K$.

Proof:

Let $(x_1, y_1)$ and $(x_2, y_2)$ be on the curve, i.e., $x_i^2+y_i^2=1+dx_i^2y_i^2$. Write $\epsilon=dx_1x_2y_1y_2 \neq 0$ and suppose $\epsilon \in \{-1,1\}$. Then $x_1, x_2, y_1, y_2 \neq 0$ and

\begin{equation}
\begin{split}
dx_1^2y_1^2(x_2^2+y_2^2) & = dx_1^2y_1^2(1+dx_2^2y_2^2) \\
 & = dx_1^2y_1^2 + d^2x_1^2y_1^2x_2^2y_2^2 \\
& = dx_1^2y_1^2 + \epsilon^2 \\
& = 1+dx_1^2y_1^2 \\
& = x_1^2 + y_1^2
\end{split}
\end{equation}

Now we need to show that $\epsilon = dx_1x_2y_1y_2 = \pm1$ implies $d$ is a square. For now we have $dx_1^2y_1^2(x_2^2+y_2^2)=x_1^2+y_1^2$. It follows that

\begin{equation}
\begin{split}
(x_1+\epsilon y_1)^2 &= x_1^2+y_1^2+2\epsilon x_1y_1 \\
& = dx_1^2y_1^2(x_2^2+y_2^2)+2x_1y_1dx_1x_2y_1y_2 \\
&= dx_1^2y_1^2(x_2^2+2x_2y_2+y_2^2) \\
&=dx_1^2y_1^2(x_2+y_2)^2
\end{split}
\end{equation}

$x_2+y_2 \neq 0 \rightarrow d=\left(\frac{(x_1+\epsilon y_1)}{x_1y_1(x_2+y_2)}\right)^2 $

$x_2-y_2 \neq 0 \rightarrow d=\left(\frac{(x_1-\epsilon y_1)}{x_1y_1(x_2-y_2)}\right)^2 $

Now if $x_2+y_2 = 0$ and $x_2-y_2=0$, then it follows that $x_2=y_2=0 \rightarrow$ contradiction to the statement we made above ($x_1,x_2,y_1,y_2 \neq 0)$.


Determine if encryption is safe against CPA The following encryption scheme encrypts each block of length $n$ of the plaintext separately:

$c_i = k_1 \oplus F(k_2 \oplus p_i)$

Where $F$ is a strong pseudo-random permutation (i.e. it is easy to calculate $F(.)$ and $F^{-1}(.)$), and $|k_1|=|k_2|=n$.

  $a.$ Is this encryption safe against a CPA attack with a single block? multiple blocks?

  $b.$ Show an efficient attack to discover the two keys.

So I thought of choosing $p=0$, and then we easily get $k_1 \oplus F(k_2)$, and we can do the same with $p=1$. But then we have two equations with our two variables being $k_1$ and $F(k_2)$, so we can get $k_1$, but how does that help with $k_2$ if we cannot calculate $F^{-1}$?

Am I in the right direction? Any help would be appreciated.

With multiple blocks the scheme is definitely not CPA as the same plaintext blocks encrypt to the same ciphertext. Using the security game given here as a framework for proving this, begin by letting $m_0 = 0^n0^n1^n$ and $m_1 = 0^n1^n0^n$. Given back a ciphertext $c = Enc_{k1, k2}(m_i)$ (where $i \in \{0, 1\}$) we can look at blocks two and three of $c$ to determine $i$. If the second block of $c$ is equal to the first block then $i = 0$. If the third block of $c$ is equal to the first block then $i = 1$. So the adversary can always correctly determine which plaintext was encrypted.

My thought on one block is that the scheme is CPA, though I don't quite know how to prove it. Assuming that $F$ is a strong PRP we can say that $F(.) \approx U_n$ ($U_n$ being uniform randomness). Given this, we can say that $c \approx k_1 \oplus U_n \approx U_n$. This intuitively indicates to me that encrypting only one block is CPA secure.

I'm not sure how to recover the keys efficiently, given that (if I remember correctly) by definition the probability of efficiently inverting a strong PRP is $< \epsilon(n)$ (aka negligible). That means getting anything back out of $F$ should not be feasible.


Number of operations for Elgamal cryptosystem In page 408 of Hoffstein, Piper, and Silverman's Introduction to Mathematical Cryptography, it says

  "Roughly speaking, in order to achieve $k$ bits of security,
  encryption and decryption for Elgamal, RSA, and ECC, requires
  $\mathcal{O}(k^3)$ operations, while encryption and decryption for
  lattice-based systems requires only $\mathcal{O}(k^2)$ operations".

Why does Elgamal encryption and decryption require $\mathcal{O}(k^3)$ operations?

Roughly speaking, in order to achieve $k$ bits of security, encryption and decryption for Elgamal, RSA, and ECC, require $\mathcal{O}(k^3)$ operations, while encryption and decryption for lattice-based systems require only $\mathcal{O}(k^2)$ operations.

That quote uses "$k$ bits of security" where there should be "a security parameters of $k$ bits" or "key size of $k$ bits". In particular, having RSA and ECC together can only mean that a confusion is made between security in bits (that I now note $b$) and key size $k$. As an aside, the quote uses $\mathcal{O}$ where formally there should be $\Theta$ or $\Omega$, see this for the difference. That's a common, I do it often!
Let's independently derive the cost counted as instructions on standard computers with fixed-width word (as customary), for $b$-bit security meaning $\Theta(2^b)$ work for an attacker to break the system,
Consider RSA with $k$-bit public modulus, and ElGamal as originally formulated, that is the group $\Bbb Z_p^*$ with $p$ a $k$-bit public prime and a generator for all or most of the group. The cost of the private-key operation is dominated by $\Theta(k)$ modular multiplications. Each of these has costs $\Theta(k^2)$ work using common algorithms, $\Theta(k^{\approx1.6})$ for large parameters with Karatsuba, $\Theta(k^{\approx1.5})$ for huge parameters with Toom-Cook, $\Theta(k\log k)$ in theory only. Ignoring anything better than Toom-Cook, we get $\Theta(k^3)$ to $\Theta(k^{2.5})$ work. For RSA, subtract $1$ from the exponent for public-key use (encryption, signature verification) and fixed public exponent.
The two algorithms considered are vulnerable to GNFS, with heuristic cost $L_{(2^k)}\left[1/3,\sqrt[3]{64/9}\,\right]$ in L-notation. Assuming this remains the best attack, and keeping only the first parameter in the interest of simplicity and a little safety margin (from the standpoint of the legitimate user), we have like $\Theta(k^{1/3})$-bit security.
At $b$-bit security, the work for ElGamal as originally formulated, and RSA signature/decryption, thus comes out roughly as $\Theta(b^9)$ to $\Theta(b^{7.5})$.


Traitor tracing - codeword properties Let $c ≥ 2$. A code $C ⊂ Q^n$
is a $c$-frameproof code if for any set
$X ⊂ C$ with $|X| ≤ c$ we have
desc$(X) ∩ C = X$.
Thus the only codewords that a coalition of up to $c$ pirates is capable of producing are those
that already belong to members of that coalition. To see a definition of desc$(X)$, see here.

What I want to know is, from the definition above can I say the following is not a 2-frameproof code?

$012,011,222,112$

As for example $012$ and $011$ agree in more than one position but I don't know if it must be the case that for any two of the codewords, they will have to agree in more than one position?? As $222$ and $112$ only agree in one position for example.

General method:

Let $X=\{222,112\}$ be a group of two traitors we focus on. Clearly (see my answer to your earlier question)
$$\mathrm{desc}(X)=\{1,2\}\times \{1,2\}\times \{2\}=\{222,122,212,112\}
$$
is the set of vectors these two users can create if they collude.
Since $\mathrm{desc}(X)\cap C=X$, this is not a contradiction to the code being $2-$frameproof.

Edit: Intuitively, two users can compare their symbols at each position and choose to use either symbol, if their symbols are distinct. If by doing this they can generate a third user's codeword, they can frame him/her by using his/her codeword. The code symbol alphabet will be very large and you can think of code symbols as cryptographic keys, and the whole codeword as a concatenated key. Thus it is infeasible to brute force the keys except by learning them with pairwise sharing between coalitions of users (called traitors).

You need to do this for all sets $X$ made up of 2 codewords and verify the e  equality holds. The overlap of codewords does not allow you a shortcut to decide if the code is $2-$frameproof.

For a small code:

Can we find two codewords that allow two traitors to build a third codeword thus frame a third user?

YES. Using $X=\{011,112\}$ we can build $012$ which is another codeword. So this code is not $2-$frameproof. Thus if Alice is the user who is assigned codeword $011$ and Bob is the user who is assigned the codeword $112$ they can generate the vectors in $desc(X)$ and in fact they can pretend to be Harry, the user who is assigned the codeword $012$, and frame him by, e.g. downloading a movie which will be charged to his account.


What are the major differences between theoretical cryptography and applied (practical) cryptography? There are a lot of theoreticians who don´t have a clue of the applied aspects involving cryptography.
Are the two disciplines mutually exclusive?
Can you learn one without the other?

I cannot tell any obvious feature to differentiate them, but I think you can distinguish theoretical cryptography and applied cryptography from the writing style of papers. In the paper about theoretical cryptography, they usually prove some cryptographic primitive(s) imply another one or construct some schemes or protocols that could be reduced to a standard assumption (e.g., identity-based encryption can be reduced to BDH assumption). Nevertheless, in the paper of applied cryptography, there are usually some implementation results which includes, for example, how to set exact security parameters or message length and so on. Furthermore, theoretical cryptography papers are usually published in conferences like CRYPTO, EUROCRYPT, and TCC, and applied cryptography papers are usually published in conferences like USENIX and ACM CCS.


Question about brute force running time Quite a simple question though I can't wrap my head around it:

The key size is: $n$

Because it's brute force it tries each possible key once from $0$ to $n$, but in my head that just makes the run time $O(n)$, though it's surely meant to be a polynomial or exponential. The decryption message is of size $x$ though I'm not sure it is relevant. Would it be because the key is of size $n$, but they must also try all keys from $0$ to $n$ make it $2^n$?

When we say key size is $n$, we consider $n$ in bits, n-bit key size. For example, AES has 128, 192 and 256-bit keys sizes. Therefore, we have $2^{128}$ key to search for AES-128 and that is exponential, $ \mathcal{O}(2^n)$

In cryptography, we use also a security parameter that measures the input size of the problem.  The security parameter is represented as unary representation ( $\lambda-\text{times }1)$ so that the complexity of the cryptographic algorithms will be polynomial time.

For RSA like systems, when we say the security parameter is $1^\lambda$, the $\lambda$ represents the number of bits of RSA modulus $n$. So the positive integer $n$ must be between $0,\ldots,2^{\lambda-1}$.

Note: We usually don't say AES (and other block ciphers) have security parameter 128, we just say 128-bit key.


Hill cipher -- obtain matrix key I have to solve Hill's cipher. I have only cipher text: CGQIYN and key: CFDG. I don't know how to decrypt it, because in all videos I've watched they knew the Matrix key from the beginning. I don't want you to solve it, but I am really hopeless and I absolutely don't know how to do it. If you can provide me some procedure, I will be grateful. Thank you.

The key is 4 characters long, therefore it must be in a 2 × 2 matrix. The numbers in this matrix must be the inverse of the encryption key matrix, and there are various methods to work this out (see this link). Once the matrix inversion has been calculated, you multiple it through each part of the cipher text in their respective 2 × 1 matrices


Stream cipher -- Are all random bit generators suitable for stream cipher? I learned the stream cipher using LFSR in the book. I wonder whether all random bit generators (i.e. BBS, Rabin generator) are suitable for stream cipher. I search using keywords "stream cipher" and "BBS", and there are few results.

The requirements for cryptographically secure pseudo random number generator and those for a stream cipher are essentially the same.
Obvious not all PRNG are secure, LFSR and mersenne-twister to name a few aren't suitable for any cryptographic task.

In some cases a PRNG will be not practical for use as a cipher. If you look at it in the pure form of a seed generating a stream of random bits than we are OK, random bits are random and knowing some won't help me know the others. But if you look at the full system, PRNGs require some entropy collection and this can make it unpractical when you want to make it a keyed cipher, some PRNGs may for instance have a huge seed which you will not want to use as a key.


Can we have single hash function both for data integrity and key derivation function? Can we have single hash function both for data integrity and key derivation function? Why and Why not?
Any link describing difference analytically will be appreciated.
Thanks.

I'll answer the question in the context of the most common application of KDFs - Password-Based Key Derivation Functions (ex PBKDF2) which take a relatively low-entropy string and derive a key from it. As opposed to Key-Based KDFs which take something that's already a strong key and change its length.

Hashes and PBKDFs are designed for different things. Yes, they are both hash functions with all the usual collision resistance, pre-image resistance, etc, but:

General-purpose hash functions want to be fast to have efficient implementations in software and hardware. This greatly reduces the runtime costs and latency of TLS servers, embedded devices doing TLS, hashing large files, etc.
PBKDFs want to be slow to make it as frustrating / expensive as possible to perform brute-force attacks on the password or master key.

SHA2 makes a terrible PBKDF because it's way too fast. PBKDF2 makes a terrible hash function because it's way too slow.

Many key derivation functions use regular hash functions internally.

For example, if you take a look at the PBKDF1/2 spec in RFC 2898, you'll notice:

  5.1 PBKDF1

  PBKDF1 applies a hash function, which shall be MD2 [6], MD5 [19] or
     SHA-1 [18], to derive keys.

and

  5.2 PBKDF2

  PBKDF2 applies a pseudorandom function (see Appendix B.1 for an
     example) to derive keys.

And the example referenced in Appendix B.1 is to use HMAC-SHA-1 as the underlying pseudorandom function.

Related question on security.SE:

What's the advantage of using PBKDF2 vs SHA256 to generate an AES encryption key from a passphrase?


Apple secure notes. How secure? In terms of cryptography, how secure is Apple Secure Notes? Can one store sensitive information there? The relevant section of the Apple white paper is quoted below:

The Notes app includes a Secure Notes feature that allows users to protect the contents of specific notes. Secure notes are encrypted using a user-provided passphrase that is required to view the notes on iOS, macOS, and the iCloud website.
When a user secures a note, a 16-byte key is derived from the user’s passphrase using PBKDF2 and SHA256. The note’s contents are encrypted using AES-GCM. New records are created in Core Data and CloudKit to store the encrypted note, tag, and initialization vector, and the original note records are deleted; the encrypted data isn’t written in place. Attachments are also encrypted in the same way.
When a user successfully enters the passphrase, whether to view or create a secure note, Notes opens a secure session. While open, the user isn’t required to enter the passphrase, or use Touch ID, to view or secure other notes. However, if some notes   have a different passphrase, the secure session applies only to notes protected with   the current passphrase. The secure session is closed when the user taps the Lock Now button in Notes, when Notes is switched to the background for more than 3 minutes, or when the device locks.

From a cryptographic standpoint (ignoring implementation issues and password sniffing), the security depends primarily on the entropy $s$ in the password, and the number $n$ of iterations in PBKDF2. Work to break is about $n\,2^{s-1}$ SHA-256 (for large $n$).

Per the obligatory XKCD, a good password has like 44 bits of entropy; a bad password (among the 1000 most common) like 10 bits.

According to that source, $n$ was $10^4$ in iOS 4.x; I'll use $n=2^{16}$ (6.5 times more).

Thus the effort to break the system is like $2^{25}$ to $2^{60}$ SHA-256.

$2^{25}$ SHA-256 is very easy. $2^{60}$ is considerable, but feasible for an entity like the NSA if it decides to invest in the necessary hardware (ASICs specialized in cracking PBKDF2). As a comparison, according to this source, bitcoin miners currently hash at a rate of $10^{19}$ SHA-256d per second, where one SHA-256d is two SHA-256; that is over $2^{70}$ SHA-256 per minute.

Nowadays, if something is protected only by a password, and can be accessed on a mobile device, and the key stretching step uses PBKDF2 without the hash in hardware, and the password is of average quality, likely it could be broken. For something safer, we want scrypt or Argon2, that leverage RAM to make the investment in a password cracker much higher; or an exceptionally good password.


(Lightweight) Multicast one-way Authentication Problem:
I'm thinking about a lightweight solution to provide source authentication (only one source) to multiple receivers (multicast message).

Context:
Taking the problem to ground, we can think of use cases like firmware update (one to many), or a command to turn on several lights 'on' (that command can be sent by one and only one source). In all cases I don't want to send many times the same message, but only once (multicast), and that the receivers can authenticate that comes from an authorised-trusted source (one-way authentication).

The scenario is similar to the one described on:
https://tools.ietf.org/html/draft-somaraju-ace-multicast-00
But there they have many senders, they use symmetric crypto, any member of the security group (same symmetric key) can send message to the other members of the group.

I know that with asymmetric cryptography the problem can be easily solved:  Digital Signatures.

But I was wondering:

Is there any established symmetric-cryptography-only solution to this problem?

To my (not extensive) knowledge I'm inclined to say No (due to the symmetric characteristics of.. symmetric crypto), but maybe there is a smart symmetric cryptosystem that can achieve source-authentication.

ps: this question is simmilar Digital Signature using symmetric key cryptography but not the same (and the answers do not provide a categoric answer)

Yes, the problem of multicast one-way authentication can be solved using symmetric cryptography only, assuming (at least) one of the following applies (there might be other ways):

we trust each receiving party to hold a common secret key secret, and not to use it nefariously;
we accept overhead in the broadcasted message growing linearly with the number $n$ of recipients, in the order of $n\cdot b$ bits for $2^{-b}$ odds of forgery;
the broadcaster and receivers share some time reference, and we can tolerate a delay (a small multiple of the time uncertainty) for the authentication of a message.

In all cases, the general idea is to include with the message a Message Authentication Code made with a key known to both the sender and receiver.

In 1 we assume a common secret key, and that's the most classic use of a MAC; but extracting the common secret key from any receiver breaks the whole security.

In 2, that problem is solved by using keys unique to each receiver, derived from a master key and a device identifier. That's a most common key management technique for Smart Cards. Something similar to the following illustrative example may have been used for software updates in the field of pay TV:

At manufacturing, each receiver device gets a public consecutive serial number $j$, starting from $j_0$, and a (so-called diversified) secret key $K_j=\operatorname{HMAC-SHA-256}(K,j)$ where $K$ is a master secret key.
Each message $M$ (firmware update) is hashed to $H=\operatorname{SHA-256}(M)$, and it is broadcast

the length of $M$
$M$ (perhaps with a version number at some fixed offset)
the concatenation of all the $\operatorname{HMAC-SHA-256}(K_j,H)$ truncated to $b$ bits, in increasing order of $j$ (which can be computed from $K$, $j$, and $H$).

Each receiver

gets the length of $M$, and checks it is within allowable bounds
gets $M$ (perhaps checking the version number is higher than the current version; this avoids replay)
computes $H=\operatorname{SHA-256}(M)$
skips $(j-j_0)\cdot b$ bits (where $j_0$ is the first serial number)
gets the next $b$ bits
checks that against $\operatorname{HMAC-SHA-256}(K_j,H)$ truncated to $b$ bits
only then proceeds to use $M$.

Security trivially follows from the PRF properties of HMAC-SHA-256, and collision resistance of SHA-256; but a practical issue is the bandwidth used.

In 3, both security and bandwidth issues are solved, based on a shared time reference. A chain of keys is set up at initialization time, that is revealed link per link by the broadcaster, and verifiable by the receivers. A message is broadcast authenticated by a MAC per one of these keys. Receivers ensure the message is received soon enough that the key can be known only by the broadcaster, and authenticate the message later when that key is revealed.

Assume broadcaster and receivers know the number $t$ of time units (say minutes) elapsed since a reference, as an integer, with a cumulated uncertainty significantly below $\pm1$ unit between broadcaster and any receiver, accounting for their cumulated uncertainty and propagation delay.

Setup (by the broadcaster)

choose the initial time $t_0$ for first use of the system;
choose a large parameter $n$; the system will be usable up to time $t_0+n-3$;
randomly choose the master 256-bit secret $K_n$;
compute $K_j=\operatorname{HMAC-SHA-256}(K_{j+1},0\|j)$ for $j$ going down from $n-1$ to $0$, and store some of the $K_j$ (say, for $j\equiv0\bmod2^{16}$, in order to be able to recompute any $K_j$ with less than $2^{16}$ HMAC);
when a device is manufactured, and that's at $t_1\ge t_0$, compute $g=t_1-t_0$ and setup the device with the trusted pair $(K_g,g)$;

Broadcast

in order to broadcast message $M$, compute and broadcast $\operatorname{HMAC-SHA-256}(K_j,1\|M)\|j$ with $j=3+t_2-t_0$, where $t_2$ is the time of that broadcast, with $t_2\ge t_1\ge t_0$;
broadcast the associated $M$ itself at any time, with something to link it to the $\operatorname{HMAC-SHA-256}(K_j,1\|M)\|j$ that has or will be broadcast;
broadcast $K_j\|j$ in clear not earlier than time $t_0+j$ (and soon after that), perhaps for all $j$, or when use has been made of $K_j$ to authenticate a message, or/and at least once in a while (say, when $8$ time periods have elapsed since the last broadcast of $K_j\|j$);

Reception

when a receiver gets an alleged $\operatorname{HMAC-SHA-256}(K_j,1\|M)\|j$, it checks that $j+t_0-3$ is at least the current time; only if that check succeeds does the receiver accept that alleged $\operatorname{HMAC-SHA-256}(K_j,1\|M)\|j$ (and buffers it until the corresponding $K_j$, and $M$, are known);
when a receiver gets an alleged $K_j\|j$, and $j>g$, the new alleged $K_j$ is checked against the trusted pair $(K_g,g)$ by way of $j-g$ iterations of the recurrence relation $K_i=\operatorname{HMAC-SHA-256}(K_{i+1},0\|i)$ with $i$ going down from $j-1$ to $g$; if and only if that checks succeeds, the trusted pair $(K_g,g)$ is atomically set to $(K_j,j)$;
a received message $M$ is accepted by a receiver when and if

an associated alleged $\operatorname{HMAC-SHA-256}(K_j,1\|M)\|j$ has been accepted;
and $K_j$ is available and trusted; that is, $j\le g$ and $K_j$ can be computed from $(K_g,g)$ by way of $g-j$ iterations of the recurrence relation $K_i=\operatorname{HMAC-SHA-256}(K_{i+1},0\|i)$ with $i$ going down from $g-1$ to $j$;
and the recomputed $\operatorname{HMAC-SHA-256}(K_j,1\|M)$ is as alleged.

Protection against replay, or playing messages out of order, can be easily added. That's very similar to: Perrig, Canetti, Briscoe, Tygar, Song, TESLA: Multicast Source Authentication Transform (Internet Draft, 2000), and perhaps earlier work that I failed to locate.

Drawbacks include:

receivers must be able to maintain or obtain a trusted time reference, which is hard in practice;
there's a latency a few time the uncertainty the receivers have on time, and that will increase over time if the trusted time is maintained my a local oscillator;
a receiver will have to perform several HMAC computations before being able to authenticate messages after the the link (or its computation capacity) was interrupted, in proportion of the duration of the interruption.

All the aforementioned drawbacks are good reasons to use a signature scheme instead of symmetric cryptography:

Virtually any 32-bit CPU for sale now, and many 8-bit CPUs, have enough resources to check an RSA or Rabin signature in time negligible compared to the duration of a software upgrade.
Signature is intrinsically immune to side channel attacks on the receivers, which has the potential to leak any secret material like $K_j$.
The size overhead is constant, and modest (crosspoint is just above 2 devices if we use signature with message recovery, like 24 if we do not).


Remotely Verify File Timestamp I'm working for a professor to build a platform for students to take midterms and finals online. The student downloads the test during class (when the professor makes the test available on the server or passes out the paper copy). However,  because of unreliable internet service, we'd like for students to be able to submit their finals later, when they can find a reliable connection. What I need is a way for a server to check that the student has not modified their answers to the exam in the intermittent period.  How can I do this?

This is exactly the scenario that the Timestamp Protocol has been created for.

You need to provide your students with access to a trusted timestamping authority (TSA). This could be you yourself or someone else (like a CA offering that service). The TSA signes the hash of the document (the test with all answers) alongside the current date and if your student passes that timestamp along to you, you have the guarantee, that the answers were not created later than the signed timestamp says.

Pleas note that while this solution does not require your students to be able to connect to your servers, it does require a short online communication to the TSA server. This requirements holds true for any other alternatives that I am aware of (like tweeting the test's hash or storing the hash in a public blockchain), I do not believe that a completely offline solution exists for your problem.


What does "simulatable" mean in security proofs? I am reading a security proof in a paper as follows.

Regarding the data confidentiality of users, all related public transcripts are simply the ciphertexts $\mathcal{C}_1,\ldots,\mathcal{C}_n$. The ciphertexts are easily simulatable according to the semantic security of the public key encryption.  How can I interpret this proof? In other words, what is meant by simulatable?

That means you can produce a transcript by yourself (with only public knowledge), which has a sequence of values $C_1',\ldots,C_n'$ such that the distribution of $C_1',\ldots,C_n'$ and that of $C_1,\ldots,C_n$ are computationally (since public key encryption) indistinguishable.


Encrypt-then-HMAC implementation - am I doing it right? I want to implement authenticated encryption using C#.  There is a dot net class called encryptAndAuthenticate, but it is only supported on windows 8 or later, and I need the code to also work on windows 7.  In other words, there is no built-in dot net library to do AES in GMC mode that works on windows 7 or earlier. So it looks like I have to use separate calls to the C# aes and hmac routines.  Here is the pseudocode in my head.  Am I planning this correctly?

Encryption:

User supplies plaintext.
User supplies password.
CSPRNG generates 256-bit salt.
Slow key derivation function on password and salt produces 640-bit output.
First 256 bits of output becomes AES key.
Next 128 bits of output becomes AES IV.
Last 256 bits of output becomes HMAC-256 key.
AES encrypt CBC mode using (plaintext, AES key, AES IV) to produce ciphertext.
HMAC-SHA256 on IV||ciphertext (using HMAC-256 key) to produce MAC.
Publicly store salt, ciphertext, and MAC.

Decryption:

User retrieves salt, ciphertext, and MAC.
Step 2 from above.
Steps 4-7 from above.
Step 9 from above.
Compare calculated MAC to retrieved MAC.
If different, abort and tell user decryption failed.
If valid, AES decrypt CBC mode using (ciphertext, AES key, AES IV) to produce plaintext.
Display plaintext to user.

PBKDF2 alone would be bad for step 4, since the blocks of its output can

trivially be computed independently.  If the PBKDF you use can't directly

produce enough output, then you should compose with a fast key-based KDF.

Make sure that

the IV is part of step 9's ciphertext
and
step 5 of decryption is constant-time

.


RSA Decryption: Doubts: knowing p or $\phi(n)$ can lead to find private exponent? I have some doubts about RSA (the public key $n$ and $e$ is public):

Note $n = pq$ and $\phi (n) = (p-1)(q-1)$

1) Say if some hacker knew $p$, why would it be easy for them to find $q, \phi (n), d$?

$d$ is a prime larger than $p, q$ so that $1 = k\cdot \phi(n) + d\cdot e$

2) Now, say if a hacker knew $\phi (n)$, why would it be easy to find $p,q,d$?

1) Say if some hacker knew $p$, why would it be easy for them to find $q, \phi (n), d$?

Since $n = p \cdot q $ this implies $q$ is also known by simple division $p = n/q$.

Then $\phi(n) = (p-1)(q-1)$ is known

By using $e \cdot d \equiv 1 \bmod \phi(n)$ then $d$ is known. This can be found by the extended Euclidean algorithm.

  $d$ is a prime larger than $p, q$ so that $1 = k\cdot \phi(n) + d\cdot e$

$d$ doesn't need to be prime. It can be larger or smaller than the $p$ and $q$ depend on the value of $e,p,q$.

  2) Now, say if a hacker knew $\phi (n)$, why would it be easy to find $p,q,d$?

$d$ is as above.

1. Method with the knowledge of $\phi (n)$

$\phi(n) = (p-1)(q-1) = (n + 1)- (p+q) $ implies $$p+q = (n +1) - \phi(n)$$ and

$$q = (n+1) - \phi(n) - p $$ since we have $$ n = pq $$ substitue

$$n = p \left ( n + 1 - \phi{(n)} - p \right ) = -p^2 + (n + 1 - \phi{(n)})p$$
 $$p^2 - (n + 1 - \phi{(n)})p + n = 0$$

Now, we got a quadratic equation that can be solved by the quadratic polynomial root-finding formula;$$p = \frac{-b \pm \sqrt{b^2 -4ac}}{2a}.$$ Using the formula one gets;

$$p = \frac{(n + 1 - \phi{(n)}) \pm \sqrt{(n + 1 - \phi{(n)})^2 - 4n}}{2}$$

Therefore the knowledge of the $\phi(n)$ enables factoring the $n$ in constant time, $\mathcal{O}(1)$

2. Method with the knowledge of $\phi (n)$

$(p+q)$ can be obtained from $n$ and $\phi(n)$ as $$\phi(n) = (p-1)(q-1) = n - (p+q) +1$$
$(p-q)$ can be obtained from $(p+q)^2-4n$, since $(p-q)$ is the square root of it.

Then one can find $q$ as $$q = \frac{(p+q)-(p-q)}{2}.$$


Can ElGamal encryption and ElGamal signatures be used together sharing the same key-pairs? I'm working on a encryption system where each party can store exactly a single ElGamal private key in a device. This is a hardware limit. The system must be expanded to support signatures and encryption.

Can each party use the same key-pair for both schemes?

I know that encryption/signature key lifetimes and security key-lengths may be different, but this would not pose any serious risk to our system.

So the question can be restated as: Are there passive or active attacks (e.g. algebraic, chosen-plaintext/ciphertext) that are specifically targeted at  users sharing ElGamal Encryption/Signature key-pairs?

It depends.

It depends on a lot of things. For example a generator of 2 is great for encryption, but makes for awful signatures. If you use a generator of 2, then no. Your signatures will get broken. Then the encryption will.

Elgamal signatures are pretty controversial. They're tetchy to get right (see above) and there are many things you can get wrong. Also, they're large, when compared to DSA. DSA is a modification of Elgamal signatures and designed so that the size of the signature is proportional to the size of the hash, not the size of the key. They're thus smaller.

They were added into OpenPGP for RFC 2440, and implemented in GnuPG but not in PGP, because of security/implementation concerns that PGP developers had. A serious bug was found in the GnuPG implementation and then were removed from GnuPG, and then from RFC 4880 as no one was implementing them.

Ask yourself why you're doing them rather than DSA, research the problems people had in the past, and make sure you've done it right.

Jon


Is establishing a secret key possible given this characteristic primitive? I am wondering if there are any readily available solutions for the following problem:
I have a ring-topology network with several devices connected to it, some malicious, some legitimate. I want to authenticate / establish a shared key between two legitimate devices, without the malicious ones finding out the key. There are no preshared secrets or certificates or anything, only this: During startup (and perhaps in regular intervals) I can exchange several messages between two trusted devices knowing for certain that the messages were sent by that trusted device (due to device-specific characteristic voltage spikes on the network).
Is this sufficient to establish a shared secret or key? I personally dont see a way but wanted to ask. Thanks!

During startup (and perhaps in regular intervals) I can exchange several messages between two trusted devices knowing for certain that the messages were sent by that trusted device (due to device-specific characteristic voltage spikes on the network).
Is this sufficient to establish a shared secret or key?

Should be; during start-up, have each device select a random signature public key, and broadcast it (and have every other device remember the public keys that they can validate came from a specific device).
Assuming that honest device A knows honest device B's public key (and knows that it is, in fact, B's key), and B knows A's public key, then it becomes easy; for example, A can generate a Diffie-Hellman key share, sign it with his private signature key, and send it to B; B also picks a DH key share, and sends a signed copy to A.  A and B validate the signatures they received, and then compute the shared secret.
No third device can recover the shared secret based on the published key shares, signatures and public keys.  In addition, because the key shares are signed, no one can modify them without one of the signature verification steps giving an error.
Now, I suspect that doing the above may be a bit more than what you personally want to take on; however it is most assuredly a solvable problem.


Why can't I break ElGamal encryption by brute-forcing the secret exponent? I am doing a course on cryptography on coursera and one of the topics covered was the ElGamal Encryption system.
I am using the terms as defined in Wikipedia.

Alice publishes $g$ and $g^x$. Theoretically an attacker could calculate $g^i$ for all $i$ from 0 to $n$. At some point the attacker will get the value which is the public key $g^x$. However big a number $n$ is, surely it might be computationally feasible to try to get the value $g^x$ in this way, and thus $x$, especially if the pre-computations are done for using repeated squaring.

I am sure I am missing something obvious :-)
I am guessing it could be the size of the group $G$ is much larger than I am assuming.

Why wouldn't the above method work?

For ElGamal to be secure, the 'discrete log problem' (which is, given $g$ and $g^x$, find $x$) must be intractable.  You give a generic way to attack the discrete log problem for a group with $n$ elements with something like $n$ steps (I say about because your approach isn't the simplest version of this type of attack; the simplest does take $n$ steps); hence for ElGamal to be secure, the size of the subgroup $n$ must be big enough.

If the security assumption of the adversary is that he cannot possibly perform $2^{128}$ computations, this immediately means that we need a group with at least $2^{128}$ elements or so.

That means that, in practice, this attack will not be practical, because (as you guessed) we'll pick ElGamal groups that are too large for the attack.

Two comments:

When I talk about the size of the group, what's actually important is the size of the subgroup generated by $g$; that is, the number of distinct values in $g^1, g^2, g^3, ...$.  When we're in a multiplicative group modulo a prime, the size of this subgroup can be considerably smaller than the size of the modulus.
It turns out that there are cleverer generic ways to attack the discrete log problem; because of these ways, it turns out that if our assumption is that the attacker can't do more than $2^{128}$ operations, the size of the subgroup needs to be at least $2^{256}$ elements large.


Figure out chosen-plaintext-attack in Zerologon attack Actually, I'm reading the description about Zerologon attack from the original whitepaper document. In there, Tom Tervoort mention these sentences:
"So I tried to come up with some chosen-plaintext attacks myself and figured out
something interesting: for 1 in 256 keys, applying AES-CFB8 encryption to an all-zero plaintext will result in all-zero ciphertext."
and
"In fact, this property is a bit more general: when an IV consists of only zeroes, there will be one integer 0 ≤ X ≤ 255 for which it holds that a plaintext that starts with n bytes with value X will have a ciphertext that starts with n bytes with value 0. X depends on the encryption key and is randomly distributed."
I did a lot web searching about this topic, but I couldn't find any explanation or prove related to those sentences.
Could someone point me to the right direction about any article, paper, document or website where mentioned properties are proved?
Thank you very much for your support.

So just to be clear, these are not properties of the CFB8 scheme itself - rather, they exist specifically in the context of this attack due to this issue with how windows uses (..or used) the scheme:

The ComputeNetlogonCredential function, however, defines that this IV is fixed and should always consist of 16 zero bytes. This violates the requirements for using AES-CFB8 securely: its security properties only hold when IVs are random.

Regarding proof of the first claim, this excerpt explains it a bit more clearly:

Because AES is a high-quality cipher with no known statistical biases, you can put in any input and encrypt it with any key, and the chance of each individual bit in the output being zero (or one) is 50%.
Every output bit’s value is like a digital coin toss.
So the chance of the first output byte being zero is the same as the chance that the first 8 output bits are all zero, which is 50% × 50% × 50% … eight times over (50% is just another way of writing 0.50, which is the same as 1/2).
50%8 is 2-8, or 1/256.

The second claim is an extrapolation from the first and I'm afraid my math skills don't reach that far.


Security Consideration on The Use of Random Number in Digital Signature key-exchange protocol allows two parties to establish a shared key over public network. Lacking  of authentication the original Diffie–Hellman key exchange is insecure  under man-in- -the-middle attack. Later the concept of authenticated key exchange protocol is proposed.In the family of authenticated DH protocols,there are two method of authentication, there are implicit authentication(example: the HMQV) and explicit authentication(example:SIGMA).Implicit authentication is more efficient , while explicit authentication often needs digital signature, so it's less efficient. when signing a message, a random number is used.

When implement a key-exchange protocol authenticated with digital signature, two parties($\hat{A}$ and $\hat{B}$) need to generate their public and private key pairs and ephemeral keys. To party $\hat{A}$, private key is $a$, public key is $A=g^a$($g$ is a generator of a cyclic group), and ephemeral key $x$. Both $x$ and $a$ are choose randomly from a set. The same with party $\hat{B}$($b,B,x$).

My doubt is that when the party $\hat{A}$ is going to sign a message, if he can use the random number he has generated such as the $a$ or $x$, while generate a new random number specify for the signature ? Are there any security threat ,if he uses $a$ or $x$ to sign a message ?

You should in general never use randomness from one cryptosystem in another cryptosystem. Bad things can happen.

Note that pseudo-randomness is good enough for cryptography, so generating new randomness is cheap.

Consider the specific example of using signed Diffie-Hellman with Schnorr signatures. Alice chooses a random number $r$, sends $g^r$, and later signs everything using by hashing $g^r$ and some other stuff to $e$ and then computing $z = r - ae$, where $a$ is her long-term secret signing key.

Now suppose the secret signing key is compromised at some point in the future. An adversary that paid attention recorded $g^r$ and the signature $(e,z)$. That adversary now knows $e$, $z$ and $a$, he recovers $r$ and can then recompute the shared Diffie-Hellman secret.

Just don't do it.


Is the "secure-as-worst-case" version of NTRU patented? Does the improved version of NTRU — which is described in "Making NTRU as Secure as Worst-Case Problems over Ideal Lattices" by
Stehlé and Steinfeld — fall under the same patents as the original?

I work for Security Innovation, which owns the NTRU patents. We think the NTRU patents would cover this algorithm too -- the patents are written broadly enough to cover different types of keys.

Note that although there are patents, we try to be reasonable about licensing terms. We have granted a free license for non-commercial use on many occasions and are currently exploring our options about licensing both the patents and a reference implementation under an open-source license. If you're interested in learning more, you can contact me directly on wwhyte@securityinnovation.com.


Hill cipher, unknown letter value I've been struggling on this problem for a while now : the Hill cipher is well-known to be vulnerable to known-plaintext attack due to its linearity. Given a key matrix $K$ of size $n\times n$, one can retrieve the key with as little as $n^2$ plaintext/cipher text couples.

All examples found on the Internet assume an alphabet where $A=0, B=1 \dots Z=25$, but how could we break the Hill cipher using a know-plaintext attack without any clue over the alphabet permutation nor the key matrix ?

I've tried several things such as linearizing the whole set of equations together, however it requires several divisions in $\bf{Z}_{26}$ which aren't possible (i.e. division by even numbers or 13)

Well, I'll assume that we'll use the same mapping between letters and integers both to translate the plaintext into integers (to be matrix multipled), and the integers (after the matrix multiply) back into ciphertext.  And, we don't know that mapping, the key matrix $K$, and possibly the value of $n$.

If so, the obvious place to start is to attempt to solve this $\bmod \ 2$.  The key matrix $K$ consists of integers modulo 26; because 2 is a divisor of 26, it can be treated as if it consists of integers modulo 2.  The mapping assigns 13 characters to even integers and 13 characters to odd integers; there are $\binom{26}{13} = 10,400,600$ possibilities.  So, what we (actually, a computer, this is a bit much for hand computation) can do is scan through all 10 million possibilities (and through the reasonable values of $n$, if we don't know that), and check if that mapping to even/odd characters is consistent with the known plaintext/ciphertext.

The result of this will be the lsbits of the mapping (which are the 13 even characters, and which are the odd characters), the lsbits of the elements of $K$, and the value of $n$.

The next obvious thing to attack, if we have enough plaintext, is to recover the mapping of the even characters.  There are $13! = 6,227,020,800$ such possible mappings; if we can find (say) $n+1$ blocks that consist of only even characters (and both the plaintext and the ciphertext blocks will consist of even characters; we know this because the mapping is consistent $\bmod \ 2$), then we can scan through the 13! possible mappings, and see if each such mapping is consistent with all $n+1$ plaintext/ciphertext pairs.  If $n=5$, then we expect to be able to find 6 such blocks if we have at least 1200 characters of known plaintext; not unreasonable.

Once we have that, that gives us the value of $K$, and the mapping for the even characters.  With that, deducing the mapping of the odd characters is straight-forward.


Injecting salt into PyCrypto KDF - useful? I have noted some sources indicate that when using a KDF like PBKDF2 (alternatively) some advocate injecting the salt at the time of execution - like this:

dv = salt + PBKDF2(salt + password, salt)

Versus the "plain" usage of

dv = PBKDF2(password, salt)

When using the PyCrypto.Protocol.KDF  PBKDF2 function or Armin Ronacher's version (both linked above), do the extra salt parameters add any benefit if no two passwords will have the same salt (but the salt will be stored with the password)?

Presumably the risk is having an oracle whereby identical passwords would be revealed as-such, encoded. Is this the case or is there another concern one ought to be mindful of?

If this is the only concern I would expect, in the absence of a fault in the algorithms that permits short-circuiting, a plainly used salt obliges one to recheck every password the entire number of iterations. Is this the case?

(Incidentally, this is copied from my post on SO, which was inexplicably closed).

EDIT:

It is worth linking:

How to store a salt
How to securely hash passwords
and Password Hashing add salt + pepper or is salt enough?

The last link in particular states, in the question:

  As far as I know, the recommended/approved method for storing password verifiers is to store:

$verifier = $salt + hash( $salt + $password )

In a sense this question becomes "is it necessary to inject the salt into a KDF in the same way as is recommended for a hash"? (presuming of course that the theory supports the injection of a salt for a hash - though I believe it does)

Identical passwords will still get unique PBKDF2 hashes given a unique salt, regardless of which mechanism you use.

I don't think explicitly adding the salt improves the security of this scheme. The designer PBKDF2 have already considered and solved this problem. There is no need for you to try to duplicate their efforts.

I think it's safer to use the well tested and well understood construction of PBKDF2:

dv = PBKDF2(password, salt)


Attack RSA with very big module ($n$) and very small $e$ (7) As an exercise I'm given an RSA to attack. I have the module ($n$), the public exponent ($e$) and a single ciphertext ($c$).

For this particular case, $n$ is VERY big (5 thousand digits more or less), but the public exponent is small ($e=7$).

I know that, as $m \ll n$, this can cause no use of the module operation ($m^7\bmod n = m^7$). I tried reversing it doing $c^{1/7}=m^{7\cdot1/7}=m$ but this is not working.
It might be that $m^7 \bmod n \neq m^7$. What can I do in this case?

What am I missing/misunderstanding?

EDIT

I was given an hint: "Big $n$ is useless with small $e$". I assume it has more to do with the exponent rather then $n$.

I found the problem: my implementation was incorrect. It was indeed a vulnerability where it happens that $m^e \mod n = m^e$. Below there is a Python implementation used to calculate it correctly (the value of $n$ and $c$ is redacted for privacy reasons).

from decimal import *

n = {redacted}
c = {redacted}
e = 7

# https://docs.python.org/3/library/decimal.html
c = Decimal(c)
e = Decimal(e)

getcontext().prec = 500 # Set a big enough precision
root = pow(c, 1/e) # Calculate c^(1/e) = m^(e * 1/e) = m
print(root)

# Decode with no padding
m = hex(int(root))[2:-1] # Number to hex
m = ''.join(chr(int(m[i:i+2], 16)) for i in range(0, len(m), 2)) # Hex to Ascii
print(m)


I'm getting a non-integer (float) private key in Paillier encryption I'm trying to implement the Paillier cryptosystem in Matlab using the key generation guidance available here: https://en.wikipedia.org/wiki/Paillier_cryptosystem#Key_generation, but the problem is that with any combination of prime numbers I try, I get a float mu required for the private key.

The first step is:

  Choose two large prime numbers p and q

Just for a starting point I chose p = 17 and q = 19.

  Compute ${\displaystyle n=pq}$ and ${\displaystyle \lambda =\operatorname {lcm} (p-1,q-1)} $.

Which I achieved in Matlab using:

n = p*q;
lambda = lcm((p - 1), (q - 1));

This gives me n = 323 and lambda = 144

Third step:

Select random integer  ${\displaystyle g}$ where $g\in {\mathbb Z}_{{n^{{2}}}}^{{*}}$

I read that g = n + 1 satisfies all the required conditions so I went with that, which gives me a g = 324.

  Fourth step is to compute ${\displaystyle \mu}$ using:

${\displaystyle \mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}}$

where,
 ${\displaystyle L}$ is defined as ${\displaystyle L(x)={\frac {x-1}{n}}} $

I achieved this using:

a = (powermod(g, lambda, n*n) - 1) / n;

gMu = mod(inv(a),n);

So at this stage, the public key is supposed to be (n,g) = (323,324) and the private key would be (lambda,mu) which in my case comes to (144,0.0069).

Why am I getting a float value of gMu whereas all the implementations I have seen online provide a integer value of private keys.

Where am I getting this wrong?

Looks like you missed the note on wikipedia:

  Note that the notation ${\frac {a}{b}}$ does not denote the modular multiplication of $a$ times the modular multiplicative inverse of $b$ but rather the quotient of $a$ divided by $b$, i.e., the largest integer value $v\geq 0$ to satisfy the relation $a\geq vb$.

As a side note, to make key generation even simpler, there is another note on wikipedia you may be interested in:

  If using $p,q$ of equivalent length, a simpler variant of the above key generation steps would be to set $g=n+1,\lambda =\varphi (n)$, and $\mu =\varphi (n)^{{-1}}{\bmod  n}$, where $\varphi (n)=(p-1)(q-1)$.


Scalar Multiplication on Elliptic Curves In the elliptic curve: $y^2 = x^3 + 20x + 13 \bmod{2111}$.
Using the point $P=(3, 10)$

I am wondering how to multiply this point by the scalar $57$?

I realize I can write $57*P$ as $2^5*P + 2^4*P + 2^3*P + P = 2(2(2(2(2P)))) + 2(2(2(2P))) +2(2(2P)) + P$.

My question is what is the best way to calculate these doubles and additions?

Some pseudo code or real code would be greatly appreciated although even a tutorial on how to do this by hand would help a lot!

The typical way to do this is the double and add method.

You start with the binary expansion of the scalar $57_{10}=111001_2$

Then scanning right from left, for each bit you double and if the bit is set to $1$ you add.

With elliptic curves it would look like this:

$Q\gets\infty$ (or the point at infinity since it is the identity element)
$P_{tmp}\gets P$
$bin\gets [1,0,0,1,1,1]$ (i.e., the binary expansion of the scalar reversed)
for $i$ in $bin$:
$\ \ $if $i==1$:
$\ \ \ \ \ Q\mathrel{+}=P_{tmp}$
$\ \ P_{tmp}=P_{tmp}+P_{tmp}$
return $Q$


Why must IV/key-pairs not be reused in CTR mode? Many sources mention that IVs must not be reused with the same key in CTR mode, for encrypting 2 different pieces of data, because that totally destroys security - but I haven't found an explanation so far as to why this is the case.

The issue is obvious if the attacker can manage to obtain the plain text and its corresponding cipher text for one piece of the data - but if no known plain texts are available, how could an attacker reconstruct the key-stream from just the IV value?

Can the security issues be mitigated by keeping the IV secret too? E.g. would an attacker have any realistic chance of cracking the encryption by just knowing that key/IV-pairs have been reused in the creation of two different ciphertexts, but nothing more?

Yes, the attacker would have a realistic chance of recovering plaintext, and preventing him from knowing the IV values does not reduce this risk.

The problem is that CTR mode encryption is effectively:

$C = P \oplus F(Key, IV)$

where $P$ is the plaintext, $C$ is the ciphertext, and $F$ is a complex function of its two inputs.

The problem with this is if you encrypt two different plaintexts with the same $Key$, $IV$ values, then the attacker gets two pairs:

$C_1 = P_1 \oplus F(Key, IV)$

$C_2 = P_2 \oplus F(Key, IV)$

Where he can see the values $C_1$, $C_2$.  With those, he can then compute:

$C_1 \oplus C_2 = P_1 \oplus P_2$

and thus deriving the value of the two plaintexts exclusive-or'ed together.

As for how that can be attacked, well, you can find two examples against ASCII-English plaintexts here and here.

And, note that since the attacker didn't actually use the IV value, it doesn't matter to him whether he knows it or not.


RSA KeyPair generation with Bouncy Castle provider: $e*d(φ(n))$ not equal to one I am using the Java Bouncy Castle provider to generate RSA key pairs. I want to test if the generated keys are valid.

According to Wikipedia the RSA key pair is generated as follows:

Choose two distinct prime numbers $p$ and $q$
Compute $n = pq$
Compute $φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n − (p + q − 1)$
Choose an integer $e$ such that $1 < e < φ(n)$ and $\operatorname{gcd}(e, φ(n)) = 1$;
i.e., $e$ and $φ(n)$ are co-prime
Determine $d$ as $d ≡ e−1 \mod φ(n)$;This is more clearly stated as:
solve for $d$ given $d⋅e ≡ 1 \mod φ(n)$.

When trying to generate 1000 key pairs, I found that $d⋅e ≡ 1 \mod φ(n)$ is only valid for 30% of key pairs.

Test code in Java below:

public void testRSAKey() throws NoSuchAlgorithmException {
        KeyPairGenerator rsa = KeyPairGenerator.getInstance("RSA", new BouncyCastleProvider());
        rsa.initialize(1024,new SecureRandom());
        int total=0;
        int isOne=0,notOne=0;
        BigInteger one=  new BigInteger("1");
        while (total<1000) {
            KeyPair keyPair = rsa.generateKeyPair();
            PrivateKey privateKey = keyPair.getPrivate();
            BCRSAPrivateCrtKey privateCrtKey = (BCRSAPrivateCrtKey) privateKey;
            BigInteger primeP = privateCrtKey.getPrimeP();
            BigInteger primeQ = privateCrtKey.getPrimeQ();
            BigInteger p1 = primeP.add(new BigInteger("-1"));
            BigInteger q1 = primeQ.add(new BigInteger("-1"));
            BigInteger fn = p1.multiply(q1);
            BigInteger publicExponent = privateCrtKey.getPublicExponent();
            BigInteger privateExponent = privateCrtKey.getPrivateExponent();
            BigInteger mod = publicExponent.multiply(privateExponent).mod(fn);//mod  ought to be one
            if(mod.equals(one)) {
                System.out.println("e*d(mod fn)=" + mod);
                isOne++;
            }else {
                System.out.println("e*d(mod fn) not equal to one");
                notOne++;
            }
            total++;
        }
        System.out.println("total=" + total);
        System.out.println("isOne=" + isOne);
        System.out.println("notOne=" + notOne);
    }

As CodesInChaos notes in the comments, the necessary and sufficient condition for $m^{ed} \equiv m \pmod{n}$ to hold for all messages $m$ is that $ed \equiv 1 \pmod{\lambda(n)}$, where $\lambda(n) = \operatorname{lcm}(p-1, q-1)$ is the Carmichael reduced totient function of the modulus $n = pq$.

As it happens, the Euler totient $\varphi(n) = (p-1)(q-1)$ is an integer multiple of $\lambda(n)$, so if $ed \equiv 1$ modulo $\varphi(n)$, then this also holds modulo $\lambda(n)$.  Thus, when generating an RSA key, it's OK to compute the private exponent $d \equiv e^{-1}$ modulo $\varphi(n)$ rather than modulo $\lambda(n)$, and indeed quite a few introductory texts on RSA (including, apparently, Wikipedia) do that for some reason, perhaps because it's arguably a bit easier to explain the math that way, or perhaps simply because the authors also mistakenly think that the necessary condition for key validity is $ed \equiv 1 \pmod{\varphi(n)}$.

However, this is not actually the case, and it's indeed quite possible for $(n,e,d)$ to be a valid RSA key even if $ed \not\equiv 1 \pmod{\varphi(n)}$, as long as $ed \equiv 1 \pmod{\lambda(n)}$.  Since using $\lambda(n)$ also yields the smallest valid (positive) private exponent $d$ for any given $e$ and $n$, and since computing $\lambda(n)$ is not significantly more difficult than computing $\varphi(n)$, most practical RSA implementations indeed do just that.


XOR cipher for encrypting compiled C code I'm exploring ways of encrypting Intel hex files we send to customers for flashing onto an embedded device. The embedded processor itself has a built-in mechanism that prevents anyone from reading the contents of the flash memory unless you unlock it using a 128-bit password.

A trivial method I thought of to encrypt the contents of the hex file is to XOR its data fields with this 128-bit password. The embedded bootloader (which knows the password) would then XOR the incoming cipher text to recover the plain text before flashing it.

The hex files are several hundred kilobytes in size. Typically such a scheme is susceptible to a frequency analysis attack, but (according to Wikipedia) the success of such an attack is dependent on the ability to make assumptions about patterns in the plain text. I have two conflicting arguments with regard to this, and I can't decide which one is more accurate.

Since the underlying plain text is processor instructions one cannot make assumptions about repetition patterns.
Because the plain text consists of opcodes interspersed with operands for those opcodes, you're working with a finite set (the opcodes supported by this processor), this fact can be exploited to identify patterns.

Pertaining to the second argument, it is a CISC processor that supports several hundred instructions; some of these opcodes (parts of the opcode) vary depending on the operand. It is certainly not a small set we're talking about.

Is this approach flawed or does it make for reasonable encryption under these circumstances? (I realize the question is subjective, but I don't know how to make it more quantitative).

The password certainly does not have to be limited to 128 bits, but due to size concerns it'll always be several orders of magnitude smaller than the code being encrypted.

What if I were to introduce some heuristic where, depending on the data content, the password was first rotated before XORing with a given block of plain text?

Lastly, I'm open to other ideas of dealing with this situation as well.

The encryption scheme seems to be:

re-use an existing 128-bit secret, originally used to unlock a read-prevention mechanism, as the 128-bit key;
split the plaintext (data to protect from prying eyes) into 128-bit blocks;
XOR each block with that 128-bit key.

That approach is flawed. Two cardinal mistakes are made:

Use XOR with a keystream that repeats.
Reuse a secret (and what's worse, without any level of derivation).

Due to 1., if there is anything guessable in the plaintext (such as, a block with like 40 consecutive 00h bytes, or an ASCII string of about that size that appears in the user interface, or a code sequence from a common library), the 128-bit secret is easily recovered, and the confidentiality of the whole plaintext is lost; that's kid's play, really. Same (for more effort and data, like a some kilobytes) if some characteristics of the plaintext are known (like instruction set and compiler), enabling attacks like frequency analysis.

Due to 2., the above attack also reveals the 128-bit key used to unlock a read-prevention mechanism, ruining it. The confidentiality of both earlier and later code is lost.

Why not use true cryptography? See this answer, especially the final paragraph and what it links to.

  What if I were to introduce some heuristic where, depending on the data content, the password was first rotated before XORing with a given block of plain text?

If the rotation is the same for each block, that will not help at all to protect the confidentiality of the ciphertext; the above attacks guessing the key work unmodified. That helps, even so slightly, to protect the secret used to unlock a read-prevention mechanism (because it is now mildly different from the one used in a futile attempt to protect the code's condifdentiality).

If the rotation varies with each block (say, as the low 7 bits of block number), it might help slightly w.r.t. the confidentiality in some cases, but in many others it harms significantly: for example, knowing that rule for rotation, and on the sole assumption there exist a contiguous zone of few kbyte where 90% of the bytes have their bit 7 of zero (with about random distribution of those that do not), it is now trivial to recover the whole key by frequency analysis; then the whole plaintext. What's needed here (if for some reason it was indispensable to use the same secret for two uses) is a derivation mechanism, not security-by-obscurity.

Also, are we talking password, or key? That's not the same thing. A key is assumed chosen at random, a password is not.


If using large keysizes, is McOE-X actually safe? After reading the this question, I found the McOE mode of operation for tweakable block ciphers along with its "X" and "G" conversions for normal block ciphers. A quick research yielded the paper "A Simple Key-Recovery Attack on McOE-X" by Mendel, Mennink, Rijmen and Tischhauser which says that McOE-X is severely broken with $2\cdot 2^{n/2}$ effort (n being block / key size).

Now I want to implement McOE, because of the other nice properties it features but before I do that I need clarity on the security properties, namely:

Is McOE-G unbroken (to public knowledge) as of today?
With the hard requirement of at least 256-bit block / keysize, is using McOE-X still safe?

Basically they state that to break a key of length $n$, you need "just" $2^{n/2}$ complexity in both the offline and online phase. This is similar to the birthday paradox, where finding a collision also happens after $\approx 2^{n/2}$ steps for a $n$ bit hash.

With today's computation power, something like DES with 56 bits is possible to brute force. If you have a symmetric cipher with 128 bit, this is actually bad news, because $2^{64}$ isn't impossible to brute force (given enough ressources and time - in a realistic amount).

However, there is also that part of the attack, which is: $2^{n/2}$ online steps. If you willingly let that one happen in your system, and your server can actually handle that amount of requests, this becomes an issue. Actually, this might not really be possible in a realistic scenario, because $2^{64}$ is still a lot. And there is quite a difference when you compare the time for an online request from a server and an exeution of a symmetric cipher on an FPGA.

But anyway, going for a keysize of 256 bit solves that issue. Brute forcing 128 bit is well beyond anything we could ever achieve. Speaking in the terms of Universal security; from bits and mips to pools, lakes -- and beyond by Lenstra et al., 2013, this is more than "global security": The required energy would be more than to bring the water of the entire planet to boil.

Im summary, the attack is not a real danger, even with 128 bit encryption. The online phase should be far from realistic in a practical setup, easily noticable and easy to counter with a limit of requests your server answers. But you should nevertheless choose 256 bit keylength at least, and then it should be fine.

The switching of keys for the cipher might allow key-related attacks, like they were studied for AES. Then for the specific cipher of your choice there might be consequences. For example I am not aware if 3DES was analyzed for related-key attacks. But any decent modern symmetric cipher should be okay.


Why do the outputs of parties in an MPC protocol have to be indistinguishable from the ideal / real world (as opposed to inputs)? In this paper at the bottom of pg. 1235 and beginning of pg. 1236 it says:

  An MPC protocol is said to be secure, if for every real world leakage
  adversary A there exists an ideal world simulator S, such that the
  output of all the parties (including the adversary) in the real world,
  is computationally indistinguishable from the output of all the
  parties (including the simulator) in the ideal world.

Why do the outputs have to be indistinguishable? Why not the inputs? The paper talks about a "secret state".  Is the secrete state different from input/output ?

Suppose you have a black box with some buttons and some lights. When you push the buttons, the lights go on and off. You wonder what's inside, but you cannot open the box. The only way to figure out what's inside is by pushing buttons and observing the lights.

Now suppose you have two black boxes. You wonder if they are the same on the inside. Again, you cannot open the boxes, so you cannot decide by inspection. You are reduced to pushing buttons, observing lights and comparing. If a sequence of button pushes usually causes a light on one box to turn on, while the corresponding light on the other box usually stays off, you know the insides are different (probably).

Note that if you have two exactly identical black boxes and push the buttons in exactly the same way on both boxes, their lights may still behave differently. That's because inside the box, there is a source of randomness, and each box may produce different randomness.

Now suppose the insides of the black boxes really are different, but if you press the buttons in the same way, the lights always seem to go on and off in the same fashion. For you, the black boxes are effectively identical, because you now have no way of distinguishing one box from another.

If you push different buttons on the two black boxes, they will probably respond in different ways. But that doesn't allow you to distinguish them.

That was easy. The tricky part is the interpretation.

Protocol input and adversarial tampering correspond to button pushing. Flashing lights correspond to protocol output and whatever the adversary can observe during protocol runs.

On the inside of the first black box, we have the real protocol's honest users and whatever infrastructure they use.

In the second box, we have two things. One thing (often called the ideal functionality) gathers up the honest users' inputs and computes the outputs in the required way. The second thing (the simulator) gets certain information about the inputs and outputs (the specified allowed leakage) from the first thing. It simulates observations for the adversary to enjoy.

Now we observe two things about the second box:

It will always do the computation correctly.
The adversarial observations are computed using only the allowed leakage, so nothing more than the allowed leakage will leak.

If the first box cannot be distinguished from the second box, it follows logically that this must also apply to the first box. Which means that we have established that our protocol is secure.