Is Elliptic Curve Diffie-Hellman (ECDH) still secure if I use the public key more than one time? Elliptic Curve Diffie-Hellman (ECDH) with

Public parameters: Ep (a,b) and G  = (x, y)
Private Keys: Na, Nb
Public Key: Pa = Na x G, Pb = Nb x G
Secret key: k = Na x Pb = Nb x Pa

Is the algorithm still secure if public key Pb is used more than once with different private keys Nb? Or are there any requirements to use use a public key more than once in a secure way?

Is the algorithm still secure if public key Pb is used more than once? Or are there any requirements to use use a public key more than once in a secure way?

I'll amend the question to what I think you mean ("is ECDH secure if we reuse our private value across multiple exchanges"), and answer it, "yes, it can be done securely, but (under some scenarios) you MUST perform validity checking on the value you receive from the peer".

The biggest thing you need to check is "is the value you receive a point on the curve?".  After all, you take the values $x_b, y_b$ that you received, and plug them into the EC point multiplication routine, and perform a series of point additions/doublings.  These routines generally assume the point they're given is already on the curve; if not, they'll assume a curve that the point is on.  That is, you are performing the operations on a curve which may be $y^2 = x^3 + ax + c'$, for a $c'$ that the attacker selected.  The attacker can select such a curve to have an order with a small factor $r$, give you a point of order $r$, and so the shared secret would be one of $r$ values (and which one would indicate the value $N_a \bmod r$.  By doing this several times with different curves (and different values of $r$), he can deduce the value $N_a$.

Now, one variant of ECDH is for both sides exchange only the $x$ values (and have the shared secret depend only on $x$); this largely avoids this problem (but not entirely, unless you have a curve with "twist security"), and is done by (for example) Curve25519 .  However, it is not universal; sometimes you are implementing an existing protocol that insists on exchanging $x, y$ values.

If you must exchange both $x$ and $y$ values, the fix is actually pretty easy: just plug the values you receive into the curve equation and see if it satifies it; that is, if $y_b^2 = x_b^3 + ax_b + c$; if not, abort the key exchange.

There is also a second (far less serious) issue; suppose that you receive a public value that's a valid point on the curve (and so passes the above check), is not the point at infinity (you do check for that, don't you?), but isn't in the prime order subgroup that $G$ is in.  We normally do ECDH in a curve of order $hq$, where $h$ is a small integer, and $q$ is a large prime (and is the order of $G$).  By giving us a point that's in the larger curve, the attacker can potentially learn $N_a \bmod h$.  This isn't nearly as serious (as the attacker can't try different values of $h$), however it is still a leakage.

Things we can do about this:

Use a prime order curve; that is, one where $h=1$.  In that case, the attacker learns nothing (as any point on the curve he gives us is also within the subgroup)
Do "cofactor DH" instead; this modifies the secret derivation to $k = (hN_a)P_b = (hN_b)P_a$; by including $h$ in the final computation, this attack would give the attacker the value $hN_a \bmod h$, but that's always 0, independent of what $N_a$ is.  Of course, this may not be an option if you're implementing an existing protocol.
Verify that $qN_b = 0$ (that point at infinity); this works, but this is a fairly expensive computation; no cheaper than selecting a fresh ECDH private value each time.
Just live with it; even if $h>1$, it is typically a small value, such as 4 or 8; giving the attacker a few bits of the private value doesn't help him that much


How are these AES MixColumn multiplication tables calculated? I'm using the mul2, mul3, mul9, mul11, mul13 and mul14 tables for the MixColumn and InvMixColumn steps in AES-128. However, I got these off some Github repository, and now I'm looking for an actual source explaining how these were calculated and so on.

I cannot find anything proper on Google, can anyone help me out?

It looks like those are just precalculated tables for multiplication by the constants 2, 3, 9, 11, 13 and 14 in the AES finite field.  We already have several questions about how multiplication in finite fields in general, and in the AES representation of GF(28) specifically, is done, such as:

Galois fields in cryptography
How is multiplication in field $GF(2^{8})$ done?
How to optimise a finite field multiplication?
How to do Hexadecimal multiplication in GF(2^8)

and even:

Efficient pen-and-paper calculation of the Galois Field multiplication?

That said, I would not recommend using lookup tables for these multiplications at all, since they can be easily calculated at runtime.  Not only do lookup tables introduce the risk of timing attacks and other side channel attacks (since memory lookups don't always run in constant time), but they are also often less efficient than calculating the multiplication directly, both on high-end CPUs (where memory access is relatively slow) and on low-end microcontrollers (where memory itself is often a scarce resource).

The usual way to do multiplication in GF(2n) is using the double-and-add algorithm, also known as "Russian peasant multiplication", which uses only two primitive arithmetic operations:

addition, which in GF(2n) is simply bitwise XOR, and
doubling, i.e. multiplication by 2 (or by $x$, in the polynomial representation), which requires a left shift followed by a polynomial modular reduction, and can be efficiently implemented e.g. like this in C:

static inline uint8_t dbl(uint8_t a) {
    return (a << 1) ^ (0x11b & -(a >> 7));
}

Both of these operations can be fairly easily implemented without branches or table lookups, which means they can be usually expected to run in constant time (although one must, of course, always watch out for possibly compiler and/or CPU optimizations that could reintroduce data-dependent timing variations).  Using these primitive operations, we can write a general AES finite field multiplication routine e.g. like this:

uint8_t gmul(uint8_t a, uint8_t b) {
    uint8_t p = 0;
    while (b > 0) {
        p ^= a & -(b & 1);         /* add a to p if the lowest bit of b is set */
        a = dbl(a);                /* multiply a by 2 in the finite field */
        b >>= 1;                   /* shift the next bit of b to the lowest position */
    }
    return p;
}

Note that the running time of the code above depends on b, and specifically on the position of its highest set bit, but (hopefully, assuming a reasonable compiler and CPU) not on a.  If we wanted, we could also make the timing fully independent of b by replacing while (b > 0) with a fixed 8 iteration loop such as for (int i = 0; i < 8; i++), but this isn't really needed if b is a public constant.

However, for multiplication by a constant b, we don't really need this general routine at all; knowing the value of b, we can manually unroll the loop and eliminate any steps we know are not needed, leaving just e.g.:

uint8_t mul2(uint8_t a) {
    return dbl(a);
}
uint8_t mul3(uint8_t a) {  /* 3 = 2 + 1 */
    return dbl(a) ^ a;
}
uint8_t mul9(uint8_t a) {  /* 9 = 8 + 1 */
    return dbl(dbl(dbl(a))) ^ a;
}
uint8_t mul11(uint8_t a) {  /* 11 = 8 + 2 + 1 */
    uint8_t a2 = dbl(a), a4 = dbl(a2), a8 = dbl(a4);
    return a8 ^ a2 ^ a;
}
uint8_t mul13(uint8_t a) {  /* 13 = 8 + 4 + 1 */
    uint8_t a2 = dbl(a), a4 = dbl(a2), a8 = dbl(a4);
    return a8 ^ a4 ^ a;
}
uint8_t mul14(uint8_t a) {  /* 14 = 8 + 4 + 2 */
    uint8_t a2 = dbl(a), a4 = dbl(a2), a8 = dbl(a4);
    return a8 ^ a4 ^ a2;
}

Also note that, for AES (Inv)MixColumns, you're going to need to multiply each input byte by four different constants in a specific pattern and sum (i.e. XOR) the results.  It's possible to do this more efficiently by splitting the finite field multiplications into doublings and XORs and applying the distributive law dbl(x) ^ dbl(y) == dbl(x ^ y), e.g. like this:

void mix_columns(uint8_t cols[4]) {
    uint8_t a = cols[0], b = cols[1], c = cols[2], d = cols[3];
    cols[0] = dbl(a ^ b) ^ b ^ c ^ d;  /* 2a + 3b + c + d */
    cols[1] = dbl(b ^ c) ^ c ^ d ^ a;  /* 2b + 3c + d + a */
    cols[2] = dbl(c ^ d) ^ d ^ a ^ b;  /* 2c + 3d + a + b */
    cols[3] = dbl(d ^ a) ^ a ^ b ^ c;  /* 2d + 3a + b + c */
}

void inv_mix_columns(uint8_t cols[4]) {
    uint8_t a = cols[0], b = cols[1], c = cols[2], d = cols[3];
    uint8_t x = dbl(a ^ b ^ c ^ d), y = dbl(x ^ a ^ c), z = dbl(x ^ b ^ d);
    cols[0] = dbl(y ^ a ^ b) ^ b ^ c ^ d;  /* 14a + 11b + 13c + 9d */
    cols[1] = dbl(z ^ b ^ c) ^ c ^ d ^ a;  /* 14b + 11c + 13d + 9a */
    cols[2] = dbl(y ^ c ^ d) ^ d ^ a ^ b;  /* 14c + 11d + 13a + 9b */
    cols[3] = dbl(z ^ d ^ a) ^ a ^ b ^ c;  /* 14d + 11a + 13b + 9c */
}

(Online demo with self-test.)

Further performance improvements may be possible e.g. through the use of bitslicing techniques.


Does humanly verifiable one time pad authentication exist? Firstly some predicates:-

Sufficient hardware generated one time pad key material.
No pad reuse.
Messages of 160 characters length (think Twitter).
28 characters only in use (A-Z, space and full stop alphabet. Think
Morse).
The very vast majority of messages based on English grammatical form.
The messages would be typed on a computer and read via computer.

Would it be possible to authenticate a one time pad message manually by hand using say pen and paper?  Perhaps even a spread sheet, but certainly no programming languages. Hence the typical HMAC is out.  The character set and message length are not unmanageable with some determination.

But most importantly, the authentication only has to be manually provable to work. He will not be authenticating every message, just those he chooses to test.  That means that the user has to be able to verify to himself that the algorithm works on the messaging system.  So he can take an arbitrary message, authenticate and satisfy himself of correctness.  The purpose is to create confidence in a manually verifiable way that the system is working correctly and not a fraud or victim of a Man in the Middle attack.

High security is of secondary importance, subservient to the need for provable manual verification of authentication.  Whilst a one time pad is totally secure, the authentication algorithm needn't be.  Any degree of authentication will be of interest for this question. It would be nice if any proposed solution could have the security level quantified in bits.

I appreciate that there is a spectrum of levels of security for the authentication mechanism.  Clearly it ranges from no security (no authentication) to very secure (HMAC calculation). I think that unfortunately we're looking at the lower end of the scale towards the no security end, as the overriding criterion is human computation.

The most basic and brute force approach that occurs is simply sending the same message in multiples.  So m ⊕ k1 | m ⊕ k2 | ... and so on.  I believe that you'd get 4.8 bits of security for every concatenated message, but I'm probably wrong.

I'll use $m\boxplus k$ for combining characters $m$ and $k$ by addition (modulo $n=28$) within the character set, or strings of individual characters of equal-length, rather than " m ⊕ k " in the question. I consider alphabetical ordering of $n$ (e.g. 28) characters with letters first, such that $\;\mathtt{'A'}\boxplus\mathtt{'A'}\;=\;\mathtt{'A'}\;$ and $\;\mathtt{'B'}\boxplus\mathtt{'C'}\;=\;\mathtt{'D'}\;$.

The question's method of sending $M\boxplus K_1\;\|\;M\boxplus K_2\;\|\;\dots$ is extremely insecure: replacing each ciphertext character $x$ by $x\boxplus\mathtt{'B'}$ is not detected, but correspondingly alters the message. There is a partial fix: for each character $m$ of the message, append to the message the character $m\boxplus m\boxplus m$, then encipher with OTP; since $\gcd(3,28)=1$, this makes altering a plaintext character precisely as hard (or easy) as guessing it. Even with that improvement, if the message (or a segment thereof) is known, it is possible to change it (or that segment) to anything desired, with certainty that the change goes undetected. That's insatisfactory.

Goals

Integrity check should be based on the plaintext, thus catching decryption errors (accidental or not) introduced by whatever deciphers, and avoiding the need to keep the full ciphertext for integrity check.
It shall remain convenient to decipher first (including while receiving), postponing integrity check.
Same unconditional plaintext confidentiality as OTP in ciphertext-only attacks, and only practically negligible leak under an attack model where the MitM gets to know if an attempted forgery succeeds or not. The receiver does not know the message length in advance. We posit integrity of the random pad, that it is synchronized between sender and receiver at the beginning of each message, and is never reused by sender or receiver.
In order to keep the integrity check feasible by hand, we restrict to use of the same $\boxplus$ as used for encryption, public latin square(s), random characters supplied by the random Pad (after those used by en/decryption), a moderate number of characters (or integer) variables (perhaps selection among these, and simple decimal arithmetic). Paper and pencil is OK (even if plaintext-leaking material gets written on it), a calculator is not.
The amount of work for integrity check should be minimized, as well as the transmission overhead, and drain of the random pad.
Quantifiable level of security against forgery, including with known plaintext (which makes sense if we do not fully trust whatever deciphers, see 1).

Circular buffer with latin square and addition (2017-06-03b)

We spare the first $s\ge2$ characters of ciphertext for integrity check, computed from the plaintext and the first $t\ge s$ characters of the random pad (or stream generator); think of $s=4$, $t=10$. The $s$ integrity check characters are computed by the sender, and optionally recomputed and verified by the receiver. All the rest is standard One Time Pad (or stream generator) and we do not further discuss encryption and decryption.

The system uses a single public $n\times n$ latin square; assume for now a random one.

For manual computation, the first $s$ characters of the random pad are written down (with - for space and + for the extra character). For each character of the plaintext, and then for each of the $t-s$ next characters of the random pad:

fetch the latin square at the line defined by that character, and the column defined the last character that was written;
combine the result using $\boxplus$ (addition modulo $n$ as used in the OTP) with the first character not striked-out (which is also the $s^\text{th}$ from the end), and strike that character;
write the resulting character following the $s-1$ characters not striked.

The $s$ characters remaining are the check characters.

(In)Security:

Each step combines the newly added character, leftmost and rightmost check characters, into a new check character, in a manner such that knowing 3 our of these 4 characters the other can be uniquely determined. It follows that the $s$ check characters remain uniformly distributed during the whole computation, for constant plaintext. No information about the plaintext can leak from the check characters, and information leak from acceptance/rejection is limited by the forgery rate.
The tight alternation of the latin square and $\boxplus$ combiners quickly and non-linearly diffuse changes; this is critical (forgery is trivial if we replace the latin square with $\boxplus$).
There is a forgery with $(n-1)^{-2}$ odds of success ($2\log(n-1)\approx9.5$-bit security): alter randomly two consecutive characters, then a third with $n-2$ non altered characters in-between. Slightly better strategies tailored to the latin square (and known/chosen plaintext if applicable) are possible. For the desired $n=28$ it is possible to objectively rank latin squares for their resistance to such attacks.
Security can't be better than $s\log_2(n)$-bit (forgery by random choice of check characters); nor than $(t-s)\log_2(n)$-bit for known plaintext (guess of the $t-s$ characters at end of computation).

That's calling for future work.

Methods in Mark N. Wegman and J. Lawrence Carter's New Hash Functions and Their Use in Authentication and Set Equality, in Journal of Computer and System Sciences 22 (1981) would be great, but I did not find something easy to perform without a computer.


Is it secure to use TOTP with same key and different time-counters? If I use TOTP to generate codes with different "expiration" time, using the same key for HMAC, will I create some kind of weakness?

Yes, that's fine where TOTPs are generated in accordance with RFC 6238; this is because the time is combined with the secret before generating the HMAC. This means that it isn't practically possible to derive the time (or information about it, such as the time difference) based on the key alone because of the Avalanche effect in the hashing algorithm that is used.


How are public keys securely and reliably obtained across the internet? I've just decided to start learning all about PKIs, and I have come across what seems like a paradox.

When fetching a public key from either a server or a CA, how can we be sure that the public key we receive back has not been intercepted and modified by a man-in-the-middle?

Isn't a public-key required to verify a digital signature? If so, wouldn't that public-key also need to have a digital signature so we can verify its legitimacy? It sounds to me like this would almost certainly lead to a never-ending chain of digital-signatures.

This has been an incredibly baffling concept for me, one that I have not been able to reason out on my own. If anyone could point out any flaws in my understanding, I would greatly appreciate it.

I have read some similar questions, one being: How does the sender obtain the receiver's public key?
But, for me, this doesn't really explain how we can eliminate man-in-the-middle attacks from the channels used to fetch public-keys.

Thanks all.

TLDR; How exactly can we eliminate man-in-the-middle attacks from the channels used to fetch public-keys?

In a public-key infrastructure, there are two ways a public key can be trusted: either because it's signed by a certificate authority that you trust, or because you already have it in a list of trusted public keys. That's where the chain of signatures ends: in a list of pre-trusted public keys.

These pre-trusted public keys are usually called “root CAs” or “trust store”. They come with the operating system, with the application, or in a configuration.

Sometimes the OS/application/configuration might have its own special-purpose set of root CAs which are obtained via a different PKI provided by the operating system where the OS/application/configuration is installed. This might not be the same system where the application that relies on the PKI will run. For example, if you download firmware for an embedded device on your PC, then the PKI that your browser uses guarantees the authenticity of the firmware image. You trust the root CAs for PKI on the embedded device because they came as part of that firmware image that you trust.

But ultimately, it comes down to a public key that you trust, not because it has a digital signature made by a certificate authority, but because you obtained it from someone you trust by means that you trust. Usually it's the same entity that also provides the code that performs signature verification, and you have to trust that anyway: if the code to verify signatures might accept invalid signatures then it doesn't matter who didn't actually make these signatures. And often it's the same entity that also provides the hardware, and again if the hardware isn't executing the signature verification correctly then it doesn't matter whether the code and data are good.

For example, if you buy a computer with an operating system preinstalled that includes a web browser with HTTPS support, the reason you trust it to verify keys has nothing to do with cryptography. Cryptography is how that browser verifies the authenticity of connections, not why you trust it to do so.

That's in fact a general thing with cryptography: cryptography doesn't actually create security properties from scratch. Cryptography is a mathematical means to extend security properties to cover more ground. For example, encryption alone can't make data confidential: all encryption does is to extend the confidentiality of the key into the confidentiality of the data. A digital signature extends the confidentiality of the private key into the authenticity of the data. Likewise, a hash doesn't guarantee the integrity of data of its own, but extends the integrity of the hash into the integrity of the data. At the root, there has to be some non-cryptographic means of securing the key or hash.

I didn't find a duplicate question on this site, but this has been covered several times on Security Stack Exchange, in particular:

SSL Certificate framework 101: How does the browser actually verify the validity of a given server certificate?
How can we trust PKI, for example, Verisign?
How are public key certificates updated securely?
Where does the list of trusted content authorities come from when using a web browser?
How are Chrome and Firefox validating SSL Certificates?
SSL certificate chain verification


TCG design specification of TPM and nonce creation I am reading TPM Main Part 1 Design Principles (PDF) which states:

  The creation of all nonce values MUST use the next $n$ bits from the TPM RNG.

I do not know what this means, or how to find out what it means. What is “the next $n$ bits”?  There is no other comment or hint on this section which might explain $n$
.

In cryptography, $n$ is frequently used to point to some specific number.

The statement

  The creation of all nonce values MUST use the next $n$ bits from the TPM RNG.

simply clarifies that all nonce values have to be generated using the TPM RNG, by using/extracting the next $n$ number of bits from that RNG. Maybe it helps to think of “$n$ bits” as “x number of bits”, where “x” is the amount specified in the paper.

So, if a paper explains that (for example) a “nonce size is 64 bits” and later states you have to extract the next $n$ bits from some function or RNG to initialize that nonce, $n$ would be 64. Taking this example, the line you’ve stumbled upon would mean: “The creation of all nonce values MUST use the next 64 bits from the TPM RNG.”

But please note that that‘s merely an example. If a paper would point to 32 bits, or 128 bits, or whatever other number of bits, $n$ would have to be interpreted as another number/count/amount accordingly. Also note that we are talking about bits in this specific case and paper. Other papers might as well use $n$ to mention “$n$ bytes” or other units (eg: “$n$ rounds of encryption”).


What 'exactly' are AES dual ciphers? I recently posted a question about AES dual ciphers based on a certain understanding of them. Now I am not so sure if my understanding is correct. AES: a question about dual ciphers and security

Originally I thought $AES$ dual ciphers were essentially the same as the original,  but with slight (but equally secure) changes that would produce distinct ciphertexts.

For example, if we encrypted $M$ with $AES$, using key $K$, we would get ciphertext $C$.
But I thought if we encrypted the same $M$, using the same $K$, but using some dual cipher $AES*$ we would get $C*$ (i.e. a different ciphertext).

However, from this paper I read (in the Intro, par. 3):
 ... how to make dual ciphers which are equivalent to the original Rijndael in all aspects ... the idea is to make another ciphers which generate the same ciphertext as the original Rijndael for the given plaintext and key.

This makes it sound as though the same input $M$, in ANY dual cipher (or is it just some?), will produce exactly the same ciphertext regardless of the dual cipher being used.

Is this correct? Or is it just the case for some dual ciphers?

$\newcommand{\compose}{\mathbin{\circ}}\DeclareMathOperator{\AES}{AES}\DeclareMathOperator{\Round}{Round}\DeclareMathOperator{\Final}{Final}\DeclareMathOperator{\KeyExpansion}{KeyExpansion}\DeclareMathOperator{\SubBytes}{SubBytes}\DeclareMathOperator{\ShiftRows}{ShiftRows}\DeclareMathOperator{\MixColumns}{MixColumns}\DeclareMathOperator{\AddRoundKey}{AddRoundKey}$The AES function is mathematically a composition of other functions:
\begin{align*}
  \AES_k(m) &= \Final_\kappa({\Round_\kappa}^r(m))
    \quad \text{where} \quad \kappa = \KeyExpansion(k), \\
  \Round_\kappa(m) &= \AddRoundKey_\kappa(\MixColumns(\ShiftRows(\SubBytes(m)))), \\
  \Final_\kappa(m) &= \AddRoundKey_\kappa(\ShiftRows(\SubBytes(m))).
\end{align*}
This is a mathematical description.  You can write the same mathematical description as a composition of functions:
\begin{align*}
  \AES_k &= \Final_\kappa \compose {\Round_\kappa}^r
    \quad \text{where} \quad \kappa = \KeyExpansion(k), \\
  \Round_\kappa &= \AddRoundKey_\kappa \compose \MixColumns \compose \ShiftRows \compose \SubBytes, \\
  \Final_\kappa &= \AddRoundKey_\kappa \compose \ShiftRows \compose \SubBytes.
\end{align*}
(Here ${\Round_\kappa}^r$ means $\Round_\kappa$ iterated $r$ times, i.e. $\Round_\kappa \compose \cdots \compose \Round_\kappa$.)

To implement AES, you could write software instructions, or design a circuit, that follows exactly this structure, by making a $\SubBytes$ circuit, and wiring it to a $\ShiftRows$ circuit, etc.  Not all AES implementations do this.  For example, Paulo Barreto adapted the composition of column and row transpositions with a table lookup into just a composition of table lookups (mathematical description, example source code).

Any physical implementation of AES will have physical characteristics like timing and power usage.  Different physical implementations might be different approaches to evaluate the same function.  For example, here are two C implementations of the mathematically same table lookup:

uint8_t S[256];

uint8_t
fast_vartime_lookup(uint8_t b)
{
        return S[b];
}

uint8_t
slow_consttime_lookup(uint8_t b)
{
        uint8_t m, r = 0, i = 0;

        do {
                m = ((b ^ i) - 1) >> 8;
                r |= S[i] & m;
        } while (++i);

        return r;
}

These are two ways to implement the $\SubBytes$ round function, and they could be written mathematically by two different compositions of different mathematical functions, although they always give the same results for the same inputs.

An AES implementation using fast_vartime_lookup and an AES implementation using slow_consttime_lookup could be called implementations of two self-dual ciphers—recall the definition of dual ciphers $E$ and $E'$ as the existence of functions $f$, $g$, and $h$ such that for every key $K$ and plaintext $P$, $f(E_K(P)) = E'_{g(K)}(h(P))$; in this case of self-dual ciphers, $f$, $g$, and $h$ are all the identity function, so that $E_K(P) = E'_K(P)$.

The pragmatic differences of fast_vartime_lookup and slow_consttime_lookup are in the mean and variance of the time they take to execute.  The mean time of fast_vartime_lookup is much shorter than the mean time of slow_consttime_lookup, to the point that if handed an AES implementation using slow_consttime_lookup you would probably throw it away in disgust.  But the variance of slow_consttime_lookup is near zero, whereas the variance of fast_vartime_lookup is significant, and the time that it takes depends on the values of secrets and the state of the machine's CPU cache—this is what enables cache-timing attacks to recover secrets by timing AES computations.  Newer cipher designs like Threefish avoid the temptation to use leaky operations like fast_vartime_lookup in the first place.

The paper you cited is about thwarting different classes of attacks, namely power analysis, by using a circuit implementing a different self-dual cipher (or, just a differently structured circuit implementing the same cipher—same idea) for each round, and randomly chosen for each round, so that the adversary not only has to guess the key and/or plaintext and any other variations in power usage of the device, but also the choice of circuit at any given time when sampling.

This is not the only technique for thwarting power analysis—there is a large public literature on the subject, and doubtless an even larger secret proprietary literature because it usually lies in the domain of hardware manufacturers who clutch at trade secrets like pearls even though most of it is probably rediscovered over and over and over again by different hardware vendors.

Another example countermeasure in hardware is to compute everything simultaneously with its complement; of course, this costs extra area.  Another one—which also works in software—is some form of blinding, typically in asymmetric crypto like RSA which has additional structure that is invariant under the private key operation: $(r c)^d \equiv r^d c^d \pmod n$, so since $r^e r^d \equiv 1 \pmod n$, $c^d \equiv r^e r^d c^d \equiv r^e (r c)^d \pmod n$; thus you can pre-multiply by a random $r$ and post-multiply by $r^e$ so that the base of the modular exponentiation is uniform random and independent of the secret $c$.  This doesn't work generically with AES because AES is designed to destroy all structure coming into it like a supervillain bent on bringing the apocalypse, but the randomization of circuits implementing the round function is a variation on the theme.


Anonymous location hashing Is it possible to know if two geographic locations are within a certain distance of each other without revealing the location?

I'm thinking about contact tracing during the COVID-19 outbreak. Assuming users have an app that records their location history, more specifically where the stopped and spend a few minutes. When a user is diagnosed with COVID-19 imagine they could share where and when they've been somewhere but without revealing the actual location and time. Other users could compare their own location history and know if there's a match.

Here's what I'm thinking so far, but I'm not sure if it's secure or not:

Let's say that locations within roughly 7.5 meters and 7.5 minutes of each other are considered a match.

Take your coordinates with enough precision up to 5 meters
Take the 5 meter squares around you, so you have a 3x3 grid
Take the current time rounded to the nearest 5 minutes
Take the 5 minutes before and 5 minutes after
Hash each combination of coordinate squares and 5 minute intervals

Now you have a set of 27 hashes. Other users can hash their own location and time (with the same precision) and see if it matches any of your hashes, but otherwise cannot know where or when that set of hashes corresponds to.

Granted, it's not precise there's a margin of error (is it 2.5?) but that's acceptable IMO.

Would this work?

Your solution is not resistant to a rainbow table attack. Furthermore, what if an adversary supposes your locality: ask you about your "private" location information, fake his/her one and tries to retrieve yours?

When you say "Anonymous location" and "without revealing the location" you are demanding a very difficult problem of Multiparty Computation: see MPC millionaire problem.

B.T.W, we can find more robust solutions that mix hash and location privacy: have you ever heard about "Spatial Bloom Filter"?


Set/change password functionality on password: should I apply bcrypt server- or client-side? I am writing a webpage on which a user can set (when registering) and change his/her password. This page is only served over HTTPS. When the user is altering his/her password, he/she is already authenticated with his/her current password.

I am planning to use bcrypt to encrypt and salt the password. Should this be done client-side (browser) or at the server? In case of client-side, I could verify on the server that bcrypt was applied with at least X (for example, 12) iterations.

Normally password hashing is done server side. It doesn't need to be, but if you use client-side password stretching there are a few things to be concerned about.

Your web clients will need to have javascript enabled. People may disable it for security, privacy  or accessibility reasons. Or because noscript browsing is more convenient. Or because they want to reduce battery drain.
Resource limitations - If the client doesn't have a high end computer then advanced password hashing might take longer than expected. Maybe their CPU is much slower than a desktop, laptop, or server. Maybe they don't have much RAM available. (For memory-hard password hash algorithms, which bcrypt isn't.)
Attacker/Defender Efficiency - Given the option to do server-side hashing with a native optimized implementation of a hash function or a client-side implementation in javascript the serverside implementation will be more efficient. Consider an algorithm running both client-side and server-side with the same parameters. Both do the same amount of work, but the server will finish first. To meet user demands for responsiveness you will lower the cost parameters of client-side hashing, compared to the cost parameters for server-side. This makes an offline password cracker's job easier if your password database does get breached.
If you do client-side password hashing then the salt needs to be known to anyone attempting to log in. This would allow attackers to use a pre-computation based attack against specific targets if they could anticipate stealing password hashes from the server.

Some people also add "A password hash is password-equivalent so client side hashing adds no security at all." This is good advice for people that think password hashing is an alternative to authenticated encryption (it isn't) but often people mistakenly use it as an argument to not do client side password-stretching. It's a bad argument because client- or server-side, you're still vulnerable to eavesdropping if you don't use encryption

One major advantage to client-side hashing is that it takes the burden of password stretching away from the server. To validate passwords the server needs to stretch every password submission it gets. (Ignoring successful brute-force prevention.) This could be exploited for a denial of service attack.

For desktop applications I might recommend client side hashing. (With end-to-end encryption with pinned server keys.)

If you use client-side password stretching then you SHOULD NOT store raw password hashes in your database. This would let anyone who stole a password-hash database to log in as any user without determining what their password was. Instead store a hash of the hash. As in something like $\text{SHA-512}(\text{bccrypt}(password, salt))$.

(Bcrypt would be done client-side and SHA-2 server-side. Normally plain-old-hashing of passwords is not secure, but hashing the hash is okay because the input has already been salted and stretched. People won't bypass the bcrypt part and go directly to searching for SHA-2 preimages because finding preimages would be a waste of time compared to guessing and hashing passwords.)

You said:

  I could verify on the server that bcrypt was applied with at least X (for example, 12) iterations.

Which leads me to believe you're misunderstanding something. It sounds like you want to hash both client-side and server-side.

First, that isn't possible unless you also have the original (plaintext) password. Second, that is a waste of effort, assuming you're testing $H(p) == H(p)$ not $H(H(p)) == \text{StoredHash}$. (The latter being splitting hash-stretching work between client and server. The former being redundant because both client and server do the same work.)

To verify that enough bcrypt rounds were used you only need to password-hash (using bcrypt) each new password once. Just hash the plaintext password server-side whenever an account's password is changed with the appropriate parameters. Then save that hash to use for password verification from that point on, for the remaining lifespan of that password.

Lastly, I think I should recommend against client-side hashing. Not because it's inherently bad, but because I think server-side hashing will be safer and easier to implement.

You also should be using argon2, which is designed to be costly by requiring both CPU and RAM resources. bcrypt requires small amounts of RAM and it's cost parameter is only used to alter CPU time. argon2 was the winner of the password hashing competition.

If you're using PHP consider using the built-in password hashing API, whether you use bcrypt or argon2. It supports both algorithms, takes care of salt generation for you, and is a very simple API.


Best modern cipher for morse code? I am looking for a modern cipher to encode morse code, ie. input is [A-Z 0-9] (base36 as I learned in the comments below) and output is the same, one character at a time. The old enigma does a good job at doing this, but is obviously broken.

The cipher doesn't necessarily have to be usable "by hand" (as the "classic ciphers" per definition do), yet it would be interesting if it would.

Is there such a cipher that maps input to output 1:1 and which keeps the output within the above bounds (or maybe ASCII 7bit)?

Of course I know about base64 and codegroup, yet the first uses small letters and the latter doesn't map 1:1.

If such a cipher doesn't exist or is not feasible I'd be interested in "why" - why can't we map 1:1 and why can't the output stay within certain "bounds"?

The other answer correctly explains how we could make a modern stream cipher, with a public random IV at the beginning of ciphertext used (together with the key) in the setup of a keystream generator, restricted to the range $[0..35]$, and using addition modulo $36$ (Beaufort cipher) to encipher each character.

Here is a more detailed description of such a system, built from AES-128 in CTR mode. Encryption goes:

Randomly generate an IV of 12 bytes using 24 hexadecimal dice throws (some of the first hexadecimal digits can be replaced by a public message number, origin/destination if that's public, the date.., but enough randomness must remain so that the IV is unique with overwhelming odds); the IV will form the beginning of the ciphertext;
Initialize the counter $N$ to the IV followed by 32 zero bits (that will be a 128-bit quantity), and $\text{available raw keystream}$ to empty;
While there is a character $p$ to encipher, converted to an integer in range $[0..35]$ per some public table;

Repeat ..

If $\text{available raw keystream}$ is empty

(optional) stop with plaintext too long if the rightmost 32 bits of $N$ are all ones; that will occur after over 33 billion characters have been enciphered.
Set $\text{available raw keystream}$ to the 8 bytes formed by encrypting $N$ using AES-128 and an agreed secret key;
Increment (the low 32 bits of) the 128-bit $N$

Get the leftmost byte $b$ of $\text{available raw keystream}$, and remove it;

.. until $b<252$ (that's $2^8-(2^8\bmod36)$);
$b\gets b\bmod36$; that's our uniformly distributed keystream character in the range $[0..35]$;
$c\gets p+b\bmod36$, output that ciphertext character (converted per the public table);

Decryption works as:

Acquire IV as the beginning of the ciphertext, over the first 24 symbols;
Initialize the counter $N$ to IV followed by 32 zero bits (that will be a 128-bit quantity), and $\text{available raw keystream}$ to empty;
While there is a character $c$ to decipher, converted to an integer in range $[0..35]$ per the public table

Repeat ..

If $\text{available raw keystream}$ is empty

Set $\text{available raw keystream}$ to the 8 bytes formed by encrypting $N$ using AES-128 and the agreed secret key;
Increment (the low 32 bits of) the 128-bit $N$;

Get the leftmost byte $b$ of $\text{available raw keystream}$, and remove it;

Until $b<252$;
$b\gets b\bmod36$; that's the same uniformly distributed keystream character in the range $[0..35]$ that was used for encryption;
$p\gets 36+c-b\bmod36$, output that plaintext character (converted per the public table).

This is modern; academically secure from a confidentiality standpoint; and answers the question as worded; but has serious operational drawbacks:

The message is not authenticated; an adversary can replace the ciphertext by one that will decipher to another message, and if the original plaintext is known, the adversary can make the substitution decipher to whatever the adversary wants, without knowing the key.
That works, to a degree, with partial knowledge of the plaintext. If for example the adversary knows that a 19-character messages is of the form AMOLEFT123REPEAT123, and the digits are encoded to 0..9 in the public table, and the number encoded is in range [000..299], then increasing the 8th and 17th character of the ciphertext by 2 (modulo 36) will increase the transmitted number by 200, perhaps giving the impression that there is ample amo, when really there is shortage.
If the IV does not contain the date, there's an even simpler attack: replay an old message from a past day where the amo stock was high.
Any error in the IV makes the whole ciphertext undecipherable (that can be fixed by sending the IV thrice, a primitive form of Forward Error Correction).
Even an accidental error in the ciphertext can go undetected.
A slip in the ciphertext (loosing synchronization between sender and receiver) makes the message following the slip garbled (this can often be detected and largely fixed using the redundancy in the plaintext);
If the ciphertext is transmitted in morse code, even though it has (within the constant overhead of the IV) the same number of characters as the plaintext, it is significantly longer to transmit than the plaintext, because frequent symbols in the plaintext use short morse sequences, but that optimization is lost for the ciphertext.

Therefore, a good modern system (say, engineered to comply to rules of a contest or ancient treaty stating that messages must be sent using morse code by human operators, but not banning computers for anything else) will work quite differently:

The plaintext will be compressed as the first step of encryption. One possible way to do this is to use e.g. gzip, with constant public fixed prefix to the plaintext consisting of public dummy plaintext with the same characteristic as the real plaintext (same character set, frequent words and sentences), and the constant compressed header resulting from this suppressed from the gzip output; this will give fair compression, and adapt easily to any alphabet and usage pattern. A caveat is that using infrequent words and sentences in the actual plaintext will lower the compression ratio, which will be detectable to some degree from the length of the ciphertext.
The resulting compressed plaintext bytestream will be enciphered using a scheme also providing message integrity. If we stick to symmetric crypto, AES-GCM comes to mind. With integrity insured, replay can be made detectable by putting a sequence number (or UTC date/time) in the message. Or we could move to asymmetric crypto (with the advantage that if the enemy fully compromises a sending station, that still does not allow decryption); if done right (hybrid encryption), it will add very little overhead.
The resulting ciphertext will be re-encoded to morse code using a method optimized for the medium at hand (with frequency of output symbols inversely proportional to their transmission duration; thus more E encoded as " . " than there are 0 encoded as " — — — — — "), and providing some degree of forward error correction. Techniques like Hufffman or arithmetic coding, and Reed–Solomon error-correction (or some ad-hoc system), will be used.

All in all, even for short messages, the ciphertext will transmit faster than for the previous system, while insuring message integrity; and for large messages the ciphertext will transmit several times faster than the plaintext would have.


special public keys and modulo n I just picked up cryptography and have some questions on RSA cryptosystem:

Say there are two public keys (n, e1), (n, e2), e1 is coprime to e2. They share the same n. Is it possible to find the plaintext if both of them encrypt the same message if I have both 2 public keys and 2 ciphertexts?
Usually, we use two primes p, q to construct modulo n = pq. I am wondering if we change n to pqr....... which is the multiplication of more than two primes, is the phi(n) equal to (p-1)(q-1)(r-1)..... and nothing else need to be changed to make RSA still work?

1) Yes. This is the common modulus attack and has actually been answered many times on this forum.

2) Assuming $r$ is prime, yes. $\phi(n)$, (the totient of $n$) can be computed by subtracting 1 from each of $n$'s prime factors and multiplying them together.


What are the advantages of SM3 and SM4 compared to NIST-approved algorithms (SHA3 and AES) Armv8.4-A will add extended support for more cryptographic primitives, to include SM3, which is a cryptographic hash function used in the Chinese National Standard; and SM4, a 128-bit block cipher; along with SHA2-512 and SHA3. 1

I am just curious as to why Armv8.4-A added support for SM3 and SM4? It's odd, especially since SHA3 is slightly more secure than SM3 (in collision attacks, but SM3 is more secure in distinguishing attacks). 2 The SM3 cryptographic hash function and AES offer better security than SM4. 3

Question:
Is there any advantage in using SM3 or SM4 over NIST-approved algorithms?

If you are seeking a government contract with China, you might be required to use Chinese government standards for cryptography, just like if you are seeking a government contract with the United States, you might be required to use United States government standards for cryptography.  There are many national pride cryptography standards that have little technical reason to recommend over widely used systems like BLAKE2, Ed25519, etc.  Some of them become prominent enough to matter commercially.


Can a Message Authenticaty Code recover original data from corrupted data? I am new to cryptography and have been studying for Dan Boneh's Stanford Course on Coursera, after going through encrytpion and decryption I've started the integrity portion of the Course.

Sir brought up MACs and how they use a key to ensure that data is not tampered. If my understanding is correct, data that is known to a hacker/eavesdropper(say the bootstrap in a windows 10 device) is kept secure since the system has a private key that can verify the data with it's own private key. That under ideal circumstances, the correct message would yield the correct tag and corrupted data would not, therefore any tampered with data would not fool the system(lack of better words).

Is my understanding correct so far?

Coming to the crux of my question, let's say that someone has used an XOR gate with one of the inputs as some random noise, the original data would get altered to some other data set. Is such a case possible if the authentication system is poorly designed? And if it is possible, how would the system get back the original data?

let's say that someone has used an XOR gate with one of the inputs as some random noise, the original data would get altered to some other data set. Is such a case possible if the authentication system is poorly designed?

If you change the message $m$ than the MAC will have a different value. Let see HMAC, fips-198-1;

$$MAC(m) = HMAC(K, m) = H((K_0 \oplus opad )|| H((K_0 \oplus ipad) || m))$$

Let say you modified even a single bit of $m$, now we have $m'$

Concentrate on this part; $H((K_0 \oplus ipad) || m'))$, and the $H$ is an approved Hash function, means that finding a collision is negligible. We assume that you have access to the keys$.

In any case, when you modify the message $m$ to $m'$ with x-oring, you have to find a collision, i.e;
$$H((K_0 \oplus ipad) || m'))=H((K_0 \oplus ipad) || m))$$

Finding collision is very hard, and if you find you will be very famous as in SHA-1, that still require $2^{63}$ calculations.

  And if it is possible, how would the system get back the original data?

If a message is changed and there is no a MAC failure, there is no way to turn back to old value, except file history etc in your operating system.

Even there is a MAC failure, you cannot turn back to the original data. MAC's are not Error Correction Codes.

In a better short wording from Maarten's Comment;

a MAC is there to make the message tamper evident rather than tamper proof


Is it safe to use a MAC as iv for CTR encoding? I have devised the following encryption algorithm and would like to know if it is safe. The goal is to use it to encrypt cookie values. I thus want to keep the encoding overhead as small as possible.

The encoding steps are as follow:

Append 3 to 5 random bytes to the value. The number of random bytes is encoded in the two less significant bits of the last random byte. The number is picked so that the value length plus random number and MAC is a multiple of 3 bytes. This is to simplify base64 encoding.
Compute the hmac(md5) value and append it after the random bytes. It might also be hmac(shaX) but md5 yields 16 bytes which is the block size of AES.
Cipher the last 16 bytes of the constructed byte sequence with AES and use the product as iv to cipher the other bytes with CTR AES. The product must have a byte length multiple of 3.
Encode the cipher text with base64.

The MAC cumulates all bit variations in the encoded value. The random bytes add some randomness in the produced digest which can be assumed to be pseudo random.

The only weakness I see is the risk to get two identical iv. But the iv should be assumed to be random because it is an encrypted MAC.

The resulting encoding is quite compact because the overhead is limited to the 16 hmac bytes and the 3 to 5 random bytes.

Do you see any problem or defect with this encoding ?

EDIT:

my question differ slightly from the other question Can I use MAC as CTR mode nonce if my messages are non repeating in that I suggest to use the encrypted MAC instead of the MAC.

The question may also be a duplicate of Using HMAC as a nonce with AES-CTR Encrypt-and-MAC. But still differ in that I cipher the MAC, and thus conceal it and randomize the iv.
My algorithm differ from the SIV algorithm defined in RFC 5297 by using hmac instead of CMAC-AES defined in RFC 4493 and by using the encrypted MAC as iv. Appart from that the algorithms are equivalent. This indirectly proves the validity of my algorithm. The advantage of SIV over my algorithm is that is uses only the AES encryption primitive and no hashing primitive.
The 3 to 5 random number is another difference between SIV and my algorithm. SIV doesn't have this and thus doesn't conceal data equality and length. The user may add random padding bytes to its plain text when this is critical for its application.

Regarding the number of random bytes, this still needs investigation. What is relevant here is the probability that two same cipher text encode the same clear text. I tend to think that it's not the same as the probability that two identical plain text yield the same cipher text.

First remark here should be don't roll your own crypto.  That said, your idea seems to be a variant of Synthetic Initialization Vector mode (SIV, RFC 5297), where a pseudorandom function of the plaintext and associated data is used to generate a value that doubles as the message authentication tag and the IV for the cipher.  Your random 3-5 byte value is an optional nonce, which in SIV is just an associated data field.

Note that SIV was designed for deterministic encryption (exceptional cases where it's OK if encrypting the same plaintext twice with the same associated data produces the same ciphertext) and for nonce misuse resistant encryption (cases you don't actually want nonce reuse but you want to minimize the damage if it does happen).  This ties to @EnTaroAdun's answer—the low diversity of random nonce values may be a problem, but if it isn't, then SIV is a well-designed, well-vetted mode that handles your scenario out of the box.  SIV also allows for arbitrary associated data fields, which can help mitigate potential duplication problems by including other contextual data other than the 3-5 random bytes into the synthetic IV computation.

SIV is not a common mode, so there's a good chance you won't find a ready-made implementation for your language.  So apart from a several nasty details (e.g., why not just use truncated HMAC-SHA2 directly?  Are you vulnerable to MAC equality comparison timing attacks?  How are you generating keys for the MAC and cipher?), your idea is neither obviously wrong nor obviously right either.


Weaknesses in vanity PGP keys The program Scallion can generate vanity PGP keys and .onion addresses using the following method:

  Generate RSA key using OpenSSL on the CPU
  Send the key to the GPU
  Increase the key's public exponent
  Hash the key
  If the hashed key is not a partial collision go to step 3
  If the key does not pass the sanity checks recommended by PKCS #1 v2.1 (checked on the CPU) go to step 3
  Brand new key with partial collision!

As RSA is susceptible to various attacks when its parameters are not properly selected, e.g. small difference of prime factors, does this method of iteratively increasing the public exponent yield any weaknesses in the generated keys?

Of course, it is possible to generate a key with a fingerprint you desire using gpg itself but it is much slower.

This method is fine (if it does actually check for short private exponents).

Any choice of public exponent is functionally and security-wise equivalent as long as it doesn't induce a short private exponent and as long as it is co-prime to $\lambda(n)$. The latter being caught by the fact that key generation won't be able to finish and the former being caught by the PKCS#1 v2.1 induced check (which I couldn't actually find, so beware!), which should check for short private exponents.


How to generate two different keys out of a single password? I'm designing a system in which a password is used both for logging in as well as for encrypting some payload.

To encrypt a payload I derive a key from the password. Very straightforward so far.

Since that encryption should be end to end, the password is not sent to the server, but it is hashed first and then sent to the server. The server then re-hashes that password to store it in the database (for the same reason you hash a password).

It is paramount that the server cannot rebuild the password not the password-derived key that was used to encrypt the payload.

So, my question is about which algorithms to chose for each of these instances.

I'm pretty sure that to hash the password for authentication purposes I want to use Scrypt. I'm aware it hasn't been tested long enough but it seems to be offering the best security these days.

To derive the key from the password, my plan was to use PBKDF2. Reading about it, some people do recommend to use Scrypt instead of PBKDF2 as it's more resilient to GPU attacks. My problem with doing that is that if I use Scrypt for both, auth and key derivation, I could be exposing the key to the server (during authentication).

How should I resolve that problem other than by using two different algorithms?

For the record, for encryption I'm using AES, specifically, AES/GCM/NoPadding, although this is not set in stone.

My implementation is done in Java and currently I'm using Bouncy Castle.

My problem with doing that is that if I use Scrypt for both, auth and key derivation, I could be exposing the key to the server (during authentication).

If you use two hashes then one failing breaks whole system. Using one reduces chance of being broken than using two.

  I'm pretty sure that to hash the password for authentication purposes I want to use Scrypt.

Scrypt isn't a hash, it is PBKDF. PBKDF2 is also a PBKDF, not a hash.

  How should I resolve that problem other than by using two different algorithms?

First of all, don't use two different PBKDFs. Then you have two different attack vectors, and you spend less time per PBKDF than with one strong PBKDF.

You should derive master key first, using some PBKDF (I would recommend Argon2, making sure strong settings are used and using salt). After master key is derived you should use KDF (Key Derivation Function) to do exactly what you ask for: Make two keys from one. Then you have K1 and K2. K1 can be used for encryption and K2 can be sent to server which also should hash it(PBKDF is useless there).

You should also consider if server should store salt (+you can access your data after HDD fail; -Server can try to break your password).


What's the best block cipher mode of operation for RSA? I know that you should never use RSA with any block cipher mode of operation, but theoretically, what's the best block cipher mode (safest) we can use with RSA encryption - without adding any kind of padding?

I already know that CTR is not the best choice and that ECB with RSA and without padding is a really bad idea cause we can see the repeated blocks, but between CBC, CTR, and OFB, I can't understand what would be the best choice.

The question is asking for a block cipher mode of operation usable with RSA.

Caveat: this is unusual and (almost certainly) not a right or valid solution to the problem at hand. See last section for the secure, common, simple, fast alternative.

RSA with proper random encryption padding (like RSAES-OAEP) is believed to give IND-CPA and even IND-CCA2 confidentiality. But it has limited capacity: like 190-byte message for 256-byte cryptogram (using RSA-2048 and SHA-256). Above that limit, ECB can safely be used if one does not care about the large speed penalty (especially for decryption) and significant size penalty due to repeated use of RSAES-OAEP.

RSA without random encryption padding (textbook RSA) is not secure. In particular, it allows to check a guess of the plaintext. Also, care must be taken that a plaintext block should be at least 1 bit less than than the public modulus is.

None of the modes of operation used for symmetric block ciphers make RSA secure:

ECB, CBC, PCBC all inherit the weakness of textbook RSA that a guess of a plaintext block can be trivially verified by re-performing the encryption of that block (which requires the public key only), and comparing with the actual ciphertext block.
CTR, CFB and OFB are totally insecure. Anyone can trivially decipher, since decryption uses the block cipher in encryption mode only.

Secure variations would amount to a specialized random padding. I'll refrain from suggesting any.

An efficient (and the most used in practice) solution to the problem of encrypting large messages with RSA is hybrid encryption: symmetric encryption with a random key, and encryption of that key per RSA. A slightly different option is RSA-KEM, where the key is secured (not encrypted) using RSA.


Public key homomorphic encryption based on secret key homomorphic Let $(E,D)$ be a secret-key bit-encryption scheme that is homomorphic to xor, and assume that each bit encryption is of size n (this concerns both fresh encryption and encryptions that have been homomorphically manipulated).
For two ciphertexts $ct$ and $ct'$, we abuse notation and will denote by $ct \oplus ct'$ the ciphertext resulting from their homomorphic xor.
Consider the following suggestions for a public-key encryption scheme:

$G'$ sample $r \gets \{0,1\}^{2n}, sk \gets \{0,1\}^n$.
$pk = (r, ct_1, . . . , ct_{2n})$, where $ct_i = E_{sk}(r_i)$. The secret key is sk.
$E'_{pk}(m) = (\oplus_{i:x_i =1} ct_i, m \oplus_{i:x_i=1} r_i)$ is done by sampling $x \gets \{0,1\}^{2n}$
$D'_{sk}(a, b) = D_{sk}(a) \oplus b$.

I already proved that $(E',D')$ is CPA secure based on $(E,D)$ CPA secure. Now I want to prove that if $(E,D)$ is fully homormorphic encryption scheme, so does $(E',D')$.
In order to do so, I think that it is enough to show support of homomorphically $\times, \oplus$ in $(E',D')$.

Let $(a_1,b_1),(a_2,b_2)$ denote 2 encryptions. The problem I encounter is the second term $b_j$ in the encryption: $m_j \oplus_{i:x_i = 1} r_i$.

Supporting homomorphic xor in $(E',D')$ can be made simply by outputting $(a_1 \oplus a_2, b1 \oplus b2)$. In order to support $\times$ homomorphically, I defined $b_j = m_j \oplus R_j$, and tried to set:
$$ (a_1 \times a_2, b_1 \times b_2) = (a_1 \times a_2, (m_1 \oplus R_1) \times (m_2 \oplus R_2)) = (a_1 \times a_2, m_1m_2 + R_1R_2 + m_1R_2 + m_2R_1)$$

where + is like $\oplus$ in our case (mod 2). Trying now to decrypt, we get $m_1m_2 + m_1R_2 + m_2R_1$ which is wrong, and in general this is my problem: how can set homomorphically "the correct" value, which should be $(SOMETHING, m_1\times m_2 \oplus SOMETHING)$.

I'd appreciate any suggestions.

Clarification:

Please note that I want to prove it based on the above, and not modify the scheme.
The scheme is initially assumed to be xor homomorphic, and next assumed to be FHE.

What you found out is really close to the result you want. In fact, your $SOMETHING$ will be $m_1R_2+m_2R_1+R_1R_2$.

The only missing step is giving out an encryption of $SOMETHING$ as the first component of your ciphertext.

In order to do so, notice that you can easily multiply $a_1$ by $b_2$, since $b_2$ is a bit:
$a_1 \times b_2 = a_1$ if $b_2 = 1$, and $0$ otherwise. (this $0$ can be computed as $a_1⊕a_1$, and $b_2$ is a public value)

Now, $a_1 \times b_2$ encrypts $m_2 R_1 + R_1 R_2$. By symmetry, you can remove $a_2 \times b_1$ that encrypts $m_1 R_2 + R_1 R_2$.

Finally, notice that $a_1 \times a_2$ encrypts $R_1R_2$.

We are now ready to give $a_1\times b_2 + a_2\times b_1 - a_1 \times a_2$ which encrypts $m_2R_1+R_1R_2+m_1R_2+R_1R_2-R_1R_2=SOMETHING$.

Your final homomorphic multiplication for your public key scheme is thus:

$$(a_1,b_1)\times(a_2,b_2) = (a_1\times b_2 + a_2\times b_1 - a_1 \times a_2,\, b_1 \times b_2)$$


Is this an acceptable implementation of ARC4 encryption for my system? I am building an open source hardware system that will be used to control things over the internet. The system consists of a Base Station and Modules which use wireless communication at 2.4GHz to exchange data.

Now I have come to the point where I need to protect the transmitted RF data against re-transmission and decryption. I also need to protect the system so that nobody can pose as a Base Station and send RF packets to some Module and for example turn on my lights or unlock the door.

Details about data that needs to be protected:

Message is always 27 bytes long (this can be reduced to 20 bytes to leave room for proper MAC)
Format of message (protocol) is known to public
Message contents are sometimes known to public because it is usually a simple command such as "1" for turn-on command, and "0" for turn-off command. Other future Modules might contain data that should be kept secret from a potential eavesdropper
Messages are transmitted rarely, there is no constant RF activity

Since this project is implemented on microcontrollers with limited amount of RAM (some 4kB for the entire thing) and FLASH memory for program (usually 32kB) there is not much room for state-of-the-art encryption algorithms and hash generation functions for MAC. There is also a limitation of data that is being transferred to 29 bytes in each packet. Data should not be split to multiple packets and re-assembled on the receiving side, so 29 bytes is all we have to work with.

These are the specifications of my current implementation:

Messages are encrypted using ARC4
Key for ARC4 is 27+1 bytes long
Key is used for maximum of 256 transmissions or for 30 minutes of RF no-activity (whichever comes first). After that new key is generated inside the Module, encrypted and sent to Base Station so it can decrypt further data
Key (27 bytes) is appended with 1 byte (SYNC) which is incremented after each encryption solving vulnerability of re-transmissions. After rollover this byte starts from 0 again (0-255). In the end this makes the key for ARC4 28 bytes long and different for each transmission

Encryption process

27 bytes of unencrypted data message is first padded with SYNC byte (the last byte of final ARC4 key), then this is padded with CRC-8 checksum calculated over the previous 28 bytes. These resulting 29 bytes are encrypted using current ARC4 key (27 bytes and the SYNC counter (1 byte)).

The CRC-8 checksum in combination with the SYNC byte is used as a MAC on the decrypting side. The packet is decrypted using current KEY+SYNC and if the SYNC byte in the decrypted packet is the same as the one expected and used during the decryption, and if the CRC-8 is calculated over the entire decrypted package as the one received - all is good.

Questions

I think this is not a very smart way to implement MAC. Is there something else that I could implement here that would take at most 9 bytes of my unencrypted data space? I could reduce the application data space from 27 to 20 bytes to make space for improved MAC.
How safe is this current implementation of the system because I am worried that someone might inject their own RF packets that will be decrypted by Modules and matched the SYNC & CRC-8. Is there any way to analyze this?

I hope I didn't give too much irrelevant information in this post, this is my first time to implement some kind of encryption, and first post on SE.

UPDATE

I have decided to abandon this design as it is not safe. Thanks to poncho for suggesting the alternative. I have found CMAC AES implementation in AVR411 document which also targets the same hardware I am currently using. You can find this document by simply searching for AVR411 on Google.

There are a bunch of problems with this protocol.

First of all, the way you generate your RC4 key (concatenate a secret key with a public nonce) is known to be weak.  The one thing that saves you is that you only do it 256 times before generating a fresh secret key; however it is known that if you were to do it, say, 2000 times with a secret key, you would have a small probability of leaking the secret key.  In my opinion, that's close enough to be scary; I'd rethink this.

Now, on to your actual question:

  I think this is not a very smart way to implement MAC

That's putting it mildly; it's a very bad way to implement it.  The problem is that CRC-8 is perfectly linear; someone who intercepts a packet can flip bits in the ciphertext, and then predict which bits in the CRC-8 he would need to flip to compensate; the decrypted plaintext will have precisely those bits flipped.  The only thing that can save you is you will reject the same message twice; an inventive attacker can get around this by causing the reception of the authentic message to fail.

It would appear that the main restriction you have is on memory (for the program and data), and not so much on execution speed. If so, I would suggest you look at small AES implementations, such as talked about in this stack exchange.  They would appear to fit well within your budget, and can be used as the basis for a truly secure protocol.


What makes lattice-based cryptography quantum-resistant? As opposed to RSA or elliptic curve cryptography?

The attacks on RSA and Elliptic curve cryptography(ECC) are based on Shor's quantum algorithm which is used for integer factorization in the context of RSA.

Correction: Note that, as pointed out by @yyyyyyy in the comments, Shor's algorithm for DLP does not factor; neither is it based on finding the order of an element (which is usually known anyway in a DLP context). Both variants have in common that Shor finds the period lattice of a certain map, and while in the factoring context this period is indeed (the $\mathbb{Z}$-multiples of) the order of an element, the lattice is two-dimensional in the discrete-logarithm setting (and contains a vector of the form $(,−1)$ where $$ is the solution to the DLP instance).

Cyclic groups are at the heart of RSA (over integer rings) and ECC (over additive groups defined on an elliptic curve over finite fields), thus the vulnerability.

However, lattice based crypto does not rely on such structures. Neither do code-based cryptosystems (McEliece, for example) so they are resistant to known quantum attacks.


Given PRNG $G(s)$, why is $G(s) || G(s+1)$ not a PRNG? I have given a pseudorandom Generator $G(s)$, $|s|=n$ whose expansion $l(n)$ is $>2n$. I also know that $G^\prime(s) := G(s_1,\ldots,s_{\lfloor\frac{n}{2}\rfloor})$ is a pseudorandom generator. Now the function

$\begin{equation}L(s) := G(s) ~||~ G(s+1)\end{equation}$

with $||$ being concatenation is supposed to be no pseudorandom generator and I struggle to prove it. Intuitively, I would think that since $L$ passes two different seeds to $G$ and $G$ is pseudorandom, $L$ must be pseudorandom too. $G(s+1)$ should be unpredictably different from $G(s+1)$ for a PRNG, should it not? Could someone point me into the right direction?

$L$ is not necessarily a pseudorandom generator, but it may be. Hence, there is no hope of proving that $L$ is not a pseudorandom generator from what you are given. Rather, you must exhibit a pseudorandom generator $G$ such that $L$ is not a pseudorandom generator. Here is the canonical example with expansion factor $n+1$.

Let $f$ be a one-way permutation (i.e., an injective, length-preserving one-way function). Then it is known that the following is a pseudorandom generator with expansion factor $n+1$:

  Choose uniformly a seed $s$ of even length $s_1s_2\dots s_{2n}$.
  Compute $b = \sum_{i=1}^n s_is_{n+i}$ (with arithmetic in $\mathbf{F}_2$).
  Output $f(s_1s_2\dots s_n)s_{n+1}s_{n+2}\dots s_{2n}b$.

Now, if $s$ is uniformly chosen, with probability $1/2$ its last bit will be $0$, meaning that $s+1$ will be just $s$ with the last bit ($s_{2n}$) flipped, and in turn it means that $G(s+1)$ will equal $G(s)$ except possibly in the last two bits. Hence, a distinguisher can check whether the second half of its input string equals the first one disregarding the last two bits of each. If the string is $G(s)G(s+1)$, this happens with probability at least $1/2$, whereas if the string is truly random this happens with probability $1/2^{n-2}$.


Pick faster private exponent I recently tried to send 1536-bit modulus CSR to COMODO. They refused to sign the certificate.
I later found out that it's because NIST mandated 2048-bit modulus on the SSL certificate.
I think it's overkill so maybe I can use smaller private exponent. (which I hope will lessen server load with reduced security margin as a trade off)

I inspected the keys generated by OpenSSL and found that private exponent is about the same size (slightly smaller) as the modulus (256 bytes).
Just 96 bytes private exponent should suffice (with some margin) from Wiener's attack.

The problem is I can't think of a way to generate such key. Since public exponent is fixed (I'm not sure but it's supposed to. I never see other value than 65537 used.) IMHO to make such key possible it should begin at picking 2 primes. At my level of mathematics that's out of the question.

I gave up on trying to generate special certificate but I just curious is it possible and practical to accomplish what I can't?
And if the answer is yes how?

Well, it is certainly possible to generate an RSA public/private key pair like what you're asking about -- I don't know what the OpenSSL API allows you can do, but if you don't restrict yourself to that, well, it is certainly possible to craft such a keypair.  You'll come up with a public key with an enormous exponent (and I wouldn't be shocked if not everyone would accept it), but it'd be possible.

On the other hand, I would argue that it's not a good idea.  For one, you're looking at only a 25% speed up.  You may be thinking "96 bytes is roughly a third of 256 bytes; given that modular exponentiation is linear in the log of the exponent (keeping everything else constant), shouldn't I see a not-quite 3 times improvement?

Well, no, you won't (or, if you do, you're doing it wrong).  The key is the Chinese Remainder Theorem optimization (already referenced by Ricky Demer); here, you do the private operation both "mod p" and "mod q", and then recombine the two halves.  That is, you compute:

$M_p = (C \bmod p) ^ {d\  \bmod\  p-1} \bmod p$

$M_q = (C \bmod q) ^ {d\  \bmod\  q-1} \bmod q$

Look at the exponents; you're not using the full $d$ (roughly 256 bytes); you're using $d\ \bmod\ p-1$ and $d\ \bmod\ q-1$; those are 128 bytes each.  So, if you replace $d$ with a 96 byte number, what you're doing is replacing those 128 byte numbers with a 96 byte number; that gives you a far smaller speedup than what you were thinking of.

We're not sure whether Weiner's attack can be extended to a private exponent of size 0.375 times the modulus size; however given the relatively small speedup this gives, it wouldn't appear to be worth the risk.

Instead, if you are concerned with performance, you might want to investigate Elliptic Curve certificates.


What is a rank-1 constraint system? Why not rank-2 constraint system or rank-3 constraint system?

How do rank-1 constraint systems link to circuits?

The "rank-1" specifically refers to the rank of the matrix which is produced.

As for the link to circuits, in zk-SNARKS at least, an arithmetic circuit is converted into a R1CS. Each constraint corresponds to one logic gate.

Here's a more detailed walkthrough by Vitalik Buterin: https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649


Are well designed crypographic codes unbreakable? (NOT ciphers) Codes are not to be confused with ciphers. It is known that all known ciphers are theoretically breakable except the one-time pad and this isn't what the question is about.

Some cryptographic codes are akin to inventing one's own secret language, along with new words, new expressions, and new grammar. I'll refer to these strong codes as "secret languages". Note that when all speakers of an ancient language dies, it becomes a secret language.

It seems to me that cracking secret languages is beyond the realms of cryptanalysis. After extensive search, I haven't found a single secret language that was ever cracked without any known plaintexts such as finding available translations. Are there any ways to crack or even crypto-analyze secret languages only using raw text written in that secret language? It is obviously possible with ciphers because they operate on the syntax level, but secret languages operate on abstractions and high-level meanings.

If the answer is yes, then why is cracking some ancient secret languages is a really hard thing to do unless one finds a translation? I challenge you to crack the The Na'vi language only by reading excerpts written in Na'vi. Also, can you point to one example of a secret language that was cracked only by looking at the text of that language?

If the answer is no, why isn't this used in modern computer cryptography? I presume it's because computers have a hard time manipulating meanings, abstractions and grammar and are better suited for manipulating syntax, letters and bits, and hence only ciphers are practical. But any more info would be appreciated.

A similar question was asked here but the two answers were contradictory, and it was closed, probably because it was focused on ancient languages and was considered a history question.

The answer is "irrelevant", because of a wrong assumption about security.

Today, ciphertext only attacks are not considered any more for real security, because it is much too weak. Known plaintext attacks are the very least to be considered, and that breaks any construction of codes or obscure languages. The reason for this is simple: Laymen might only see the ciphertext/encoded text. But specialists will find ways to get additional information to enable known plaintext or chosen plaintext attacks (for symmetric encryption. Asymmetric has a different playing field)

This is very similar to the argument "security through obscurity", as it is still practiced quite often. Sure, on the first glance it seems a good idea not to give an attacker information about your system. And then later you realize: If that is the only security mechanism, you're screwed when he finds out anyway.

Edit:

In order to avoid further discussions, the answer to

  Are there any ways to crack or even crypto-analyze secret languages only using raw text written in that secret language?

is "No". Under these assumptions (no knowledge about the code), you can't break a single encoded message.

Second question:

  If the answer is no, why isn't this used in modern computer cryptography?

Because your reasoning stops being valid after the first message send or if your assumption is no longer true. Multiple messages start showing correlations, which make single words translatable, then often used statements, then sentences, ...

Additionally, today's cryptography does not consider "ciphertext only" attacks to be a useful argument any more. If you present a new symmetric cipher which is only secure against such attacks, it gets labeled "not secure". Today at the very least, security must hold against known plaintext attacks. And at that point, no classical code can withstand.

Finally, you said in the comments "Codes are just ciphers with a very large key that always gets reused.". This is just wrong. Codes are not ciphers. The two are quite distinct and have their own properties. If anything, you could argue that ciphers are codes, extended with real security. Surely not the other way around.


Distributed knowledge problem I need a way to distribute knowledge among multiple parties - lets start with two. The idea is while the knowledge is originally created by one party I need to transform it into a situation where no party can access the information without the other's help.

I actually have an idea about how to solve this but cryptography is not my strong suit and I would like to ask you if there is a better way to do it.

Scenario

Alice and Bob each have written their favorite movies on cards (one movie per card). I need a way for them to address each card in a way that neither of them knows what movie is on the card.

Edit: It is totally acceptable to know to whom a card belongs. As for being honest about the reveal, that's what my other question was about. Each party would have to pass a commitment token along with the random number.

Proposed Solution

Both parties assign random numbers to each of their movies.
They write cards with those numbers, shuffle them and hand it to the other party.
The other party assigns new random numbers to each of the received numbers.
They write cards with those new numbers, shuffle them and place it openly in the middle.

Now if I'm right, neither of them should know which numbered card corresponds to which movie, yet each card uniquely represents one of those movies.

Extension for more parties

Option A: The cards go through all parties, each assigning a new number. All parties are required to determine the movie.
Option B: Each party distributes his number cards equally among the other parties but no further iterations is performed. Only two parties are required to determine a movie but not always the same...

There is an obvious problem with your solution; it allows cheating during the reveal.

Here's how it'd work; suppose Alice's favorite movies are Avatar and Titanic.  She assigns a random number 19 to Avatar (along with Commit(Avatar)) and 28 (and Commit(Titanic)) to Titanic.  She passes them to Bob, who assigns 42 to 19 (which was originally Avatar), and 37 to 28 (which was original Titanic).  Note that he can't include Alice's commitments, otherwise Alice would know which card was which.  So, Bob publishes 37 and 42 (in some order).

Now, it comes time to reveal 42.  We ask Bob what 42 originally stood for; Bob is supposed to answer 19 (and Commit(Avatar)); however, there's nothing stopping him from answering 28 (and Commit(Titanic)); only he knows the mapping, and it's not detectable if he changes his mind.

The obvious solution is to make Bob do commitments as well.  That is, Alice sends Commit_A(Avatar) and Commit_A(Titanic) (the random numbers really don't do anything that the commitments themselves don't); Bob then publishes Commit_B(Commit_A(Avatar)) and Commit_B(Commit_A(Titanic)) in some order; when it comes time to reveal a card, we send Commit_B(Commit_A(Avatar)) to Bob, which opens his commitment (and publishes the random number he used, so others can confirm it), and then sends the Commit_A(Avatar) to Alice, which reveals the original Avator (and, again, she publishes her random number so others can again confirm it).

It generalizes in the obvious way if Carol and Dave also want to play.  However, one problem with it (and it's really a problem with the problem statement, not the protocol) is that if Dave decides to quit (either because his computer crashed, or if he is just feeling ornery), then we can't reveal any of the cards.  A more sophisticated protocol can be designed that will allow any M of the N parties to reveal a card; however, this is going to be a lot more complicated.


Orignal Schnorr Signature vs Discrete logarithmic Schnorr Signature I have currently started a course on cryptography and am an absolute beginner. While reading through Schnorr's Protocol I came across several ways in which it was described.

One of the approach is described here: - https://www.youtube.com/watch?v=mV9hXEFUB6A

A second approach using discrete logarithmic is described here - https://asecuritysite.com/encryption/schnorr

The third article had a slightly different mathematics to the discrete log implementation- https://blockgeeks.com/guides/what-is-zksnarks/#The_Schnorr_Identification_Protocol

I apologize if this is completely novice. I just want to know how are they different and which protocol was initially published by Claus Schnorr?

edit:
Thanks for the reply. My main doubt is while learning Schnorr's signature, The implementation on the Asecurity source given and the Blockgeeks source given is different. What is the difference between them?
What Asecurity says:

With Schnorr identification, Peggy (the prover) has a proving public key of (N,g,X)(N,g,X) and a proving secret key of (N,x)(N,x). NN is a prime number for the modulus operation, and xx is the secret, and where:

X←gx(modN)X←gx(modN)

On the registration of the secret, Peggy generates a random value (yy), and then computes YY:

Y←gy(modN)Y←gy(modN)

This value is sent to Victor (who is the verifier). Victor then generates a random value (c)(c) and sends this to Peggy. This is a challenge to Peggy to produce the correct result. Peggy then computes:

z←(y+xc)(modN)z←(y+xc)(modN)

He then sends this to Victor in order to prove that he knows xx. Victor then computes two values:

val1=YXc(modN)val1=YXc(modN)

val2=gz(modN)val2=gz(modN)

If the values are the same (val1≡val2val1≡val2), Peggy has proven that she knows xx.

This works because:

YXc=gygxc=gy+cxYXc=gygxc=gy+cx

gz=gy+cxgz=gy+cx

Blockgeeks

Anna wants to prove to Carl that she knows a value x such that y = g^x to a base g.

Anna picks a random value v from a set of values Z, and computes t = g^v.

Anna computes c = H(g,y,t) where H() is a hash function.

Anna computes r = v – c*x.

Carl or anyone can then check if t = g^r * y^c.

The first publication using the Discrete Logarithm Problem (DLP) for asymmetric cryptography is in Diffie-Hellman key exchange. The original works in the multiplicative group $\Bbb Z_p^*$, or a typically large subgroup of that.

The first use for signature is ElGamal signature. It uses the same kind of groups, and that makes its signature rather large. It does not use a hash. That and other issues make the original description unsatisfactory; it's more a building block for later signature schemes based on the DLP.

The most notable is the original Schnorr signature. It works in a slightly different group, called Schnorr group, which is a small subgroup of $\Bbb Z_p^*$, with $q$ elements where $q$ is a prime dividing $p-1$, and much less wide/large. That provides what long was (and if we restrict to practice, remains) the shortest known secure signature with appendix (that is, added to the unmodified message): $3b$-bit signature for $b$-bit security. The signature consists of a $b$-bit hash and an integer modulo $q$ over $2b$ bits.

A variant differing only by using a $2b$-bit hash is cleaner from a math standpoint and slightly less difficult to prove secure, thus was much studied, and is stated as being Schnorr signature in many textbooks. That one has a $4b$-bit signature, for a group with a little less than $2^{2b}$ elements. The exposition in the HAC is among these, and it's signature has the hash second, contrary to the original. It is followed by an example with small integers.

The later DSA of FIPS 186 is often seen as a way to work around Schnorr's patent. It is significantly different and more complex. It has $4b$-bit signature.

There are many later signatures also called Schnorr signature, typically with $4b$-bit signature, also based on the DLP, but in an Elliptic-curve group. Study these later!

"original Schnorr signature" unambiguously means a scheme in a Schnorr group, with $3b$-bit signature having one component a $b$-bit hash, the other $2b$-bit coding an integer.
"Schnorr signature" can be any number of things. In introductory material that could be either the original, or the variant where the hash is made $2b$-bit. Other possibilities are too many to enumerate.

Note: "Discrete logarithmic Schnorr Signature" is a naming error. "Logarithmic" is an adjective applying to quantities, mostly continuous. A complexity can be logarithmic, perhaps by extension a count including the bit length of a bitsring, rather not a bitstring like signatures are, not a signature scheme which is a method to obtain and verify a signature. Make that: "Schnorr signature" (thus) based on the Discrete Logarithm Problem (in some group).

Remark: some videos are a great way to learn for their author.


AES-GCM and its IV/nonce value I was reading about the differences between the GCM and the CBC more here and I have a follow up doubt on the same.

In the CBC mode the person who performs the encryption is the one who provides the IV for the encryption -- and the IV is required to decrypt the ciphertext.

However, in GCM i read that the nonce value is internal -- so is it a value which needs to be kept in track off by the person who encrypts / decrypts the values? I'm specifically referring to the Java BouncyCastle implementation of AES-GCM.

Is the nonce value effectively an IV supplied by the person who encrypts the data appended with an internal counter?

Yes, the nonce will be used with a counter appended in order to generate the CTR mode keystream.

It will also be used as an input to GHASH: which is a polynomial MAC used to authenticate the data.

The nonce itself does not have to be random, it can be a counter. But it absolutely must be unique for each message encrypted with the same key. Using GCM on two different messages with the same key and nonce basically allows an attacker to decrypt both messages and forge further messages. (There are some limitations, but they aren't significant enough for it not to be devastating to the cryptosystem.)

So you can either have each side keep track of a counter as the nonce, or you can send it in the clear before each message; so long as it's unique.

For an example in a real-world protocol, see the GCM spec for TLS 1.2: https://tools.ietf.org/html/rfc5288#section-3. It concatenates a value from the handshake and a counter to form the nonce.


What is the difference between a hash and a permutation? As defined by Wikipedia a hash function is

  [...] any algorithm or subroutine that maps large data sets of variable length to smaller data sets of a fixed length. For example, a person's name, having a variable length, could be hashed to a single integer. The values returned by a hash function are called hash values, hash codes, hash sums, checksums or simply hashes.

and when you search for a permutation you find:

  In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting (rearranging) objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order.

Interestingly none of the pages mention the other term when you quick-search for it.

As I understand it, a hash function will map a universe of preimages into a fixed set of outputs (fixed because they have a fixed length, therefore the group is finite) where a permutation will rearrange the input producing something of arbitrary length.

How fair is it to say that a hash is a limited permutation or that a permutation is an unbounded hash? I ask this because I haven't seen the comparison between the two anywhere so far and from my understanding, a permutation is more of a theoretical concept while a hash is more of a practical one.

As Henrick notes, permutation is a mathematical term for a function (or map; these two words are essentially synonymous in mathematics) that rearranges the elements of its domain so that exactly one input is mapped to each output.

In other words, a function $f$ from a set $S$ to $S$ is a permutation if and only if:

no two inputs are mapped to the same output: $f(x) = f(y) \implies x = y$, and
some input is mapped to every output: for all $y \in S$ there exists $x \in S$ such that $f(x) = y$.

For finite sets $S$, these two conditions are in fact equivalent: either one implies the other.  This is easy to see using a counting argument: since the number of possible inputs equals the number of possible outputs, if any two inputs are mapped to the same output, there must be at least one output which is left without any corresponding input, and vice versa.

(In fact, some mathematicians prefer to reserve the word "permutation" only for the case where the domain is finite, and use the word "bijection" for the more general case described above; others treat the two words as more or less synonymous.  Also, in some branches of mathematics, a permutation of an $n$-element set $S$ is commonly defined as a function from the set $\{1, 2, \dotsc, n\}$ to $S$, rather than from $S$ to $S$.  However, these variations in usage don't really make any significant difference for most purposes, certainly not in cryptography.)

A useful mathematical property of permutations is that they are uniquely invertible: that is, given a permutation $f: S \to S$, there exists a unique permutation $g: S \to S$ such that $g(f(x)) = x$ for all $x \in S$.

The number of different permutations of an $n$-element set $S$ — that is, functions $f: S \to S$ which satisfy the definition above — is $k! = 1 \times 2 \times 3 \times \dotsb \times n$.  A random permutation of a set $S$ is simply a function chosen uniformly at random from the set of these $n!$ possible permutations of $S$.

For cryptography, the significance of random permutations is that they are ideal ciphers for messages in the set $S$: the invertibility means that a message encrypted using the permutation $f$ can be decrypted using the corresponding inverse permutation $g$, and if $f$ is chosen randomly from the set of all permutations of $S$, the encryption $y = f(x)$ of any given message $x \in S$ will also be uniformly random, and thus provides no information about the original message $x$ to anyone who does not know $f$.

For small sets $S$, it's possible to examine all the possible permutations of $S$ one by one, but as the size of the set grows, the number of possible permutations quickly becomes truly enormous, and it becomes meaningful to speak of pseudorandom permutations.  These are functions chosen from some smaller (but still very large) subset of the full set of permutations of $S$, but in such a way that there is (hopefully) no way for anyone to efficiently distinguish a permutation randomly chosen from the subset from a truly random permutation chosen from the full set of permutations of $S$.

A common type of pseudorandom permutations in cryptography are block ciphers.  These are permutations of $b$-bit bitstrings, for some fixed number $b$, where the mapping of inputs to output is determined in some complicated way by a $k$-bit bitstring called the key.  (Block ciphers are normally also constructed in such a way that the inverse permutation can also be easily computed based on the key.)

Typical values for $b$ and $k$ might be, say, 128 bits each.  Now, clearly, the number of possible keys, $2^{128}$ (which generally equals the number of distinct permutations achievable using a given cipher algorithm, assuming that the cipher has no equivalent keys) is a vanishingly small fraction of the total number $(2^{128})! \approx 2^{2^{133}} \approx 2^{1.3 \times 10^{40}}$ of possible permutations of 128-bit bitstrings.  However, it's still a huge number: if we had a billion ($10^9$) computers, each running at 1 THz with one instruction per cycle, it would still take 10 billion years for these computers just to execute $2^{128}$ instructions.  Thus, it's completely impossible to tell if a permutation is chosen from a $2^{128}$-element subset or from the full set of $(2^{128})!$ permutations of $128$-bit bitstrings just by comparing it with each of the permutations in the subset in turn; and we hope that, for modern block ciphers like AES, there is also no other, significantly more efficient way to distinguish them from a random permutation than such a "brute force" attack.

OK, so that's what a permutation is and how they're used in cryptography.  What about hashes?  A hash function is a map from the infinite set of all bitstrings of any length to the finite set of bitstrings of length $b$ for some fixed number $b$.  Thus, a hash cannot be a permutation (in any sense of the word): the set of possible inputs of a hash is strictly larger than the set of possible outputs, and thus it must map multiple inputs (in fact, infinitely many of them) to the same output.

In particular, this means that a hash function cannot be invertible, since, at least for some outputs, there's no way to tell which of the many possible equivalent inputs produced that output.  Even if we restrict the inputs to bitstrings of some constant length $\ell$, this holds whenever $\ell > b$ (and is likely to hold even for somewhat shorter inputs).

Hashes are closely related to message authentication codes (MACs), which can, in some ways, be viewed as families of hash functions, where the choice of the specific function from the family is determined by some secret key — just like a block cipher is a family of permutations, from which one permutation of chosen by a key.  In this sense, secure MACs can be seen as pseudorandom functions, which resemble truly randomly chosen functions from their respective input set to their output set in the same way as pseudorandom permutations resemble truly random permutations.

(Actually, the usual definition of a secure MAC doesn't really require complete pseudorandomness, but merely "unforgeability".  However, any pseudorandom function from the set of all bitstrings to a set of fixed-length ones does satisfy the definition of a secure MAC, even if not all MACs are necessarily  pseudorandom functions.)

However, what we normally require from cryptographic hash functions is both something more and something less than pseudorandomness.  This is because hash functions differ from MACs in that they have no secret key, and so anyone can calculate the same hash for a given input equally well.  In particular, this means that it's trivially easy to distinguish any given hash from a random function just by comparing the outputs to those of a known instance of the same hash function.

Instead, what we typically require from cryptographic hash functions is resistance to collision and preimage attacks.  That is, even an attacker who knows how the hash function is calculated, and can calculate the hash for any input they want, should be practically unable to either:

find an input that hashes to a given output value (first preimage resistance),
find another input that hashes to the same output as a given input (second preimage resistance), or
find any two inputs that hash to the same output (collision resistance).

So, no, a hash is never a permutation — and, other than that, the two concepts really don't have much to do with each other at all.


Insecure private-key encryption I am learning about crytography and the differences between the public and private keys encryption examples and I was wondering if it is possible to have a private key encryption scheme that is completely insecure? I have not been able to find what that could look like but I'm curious? Or is this not possible? Is the encryption scheme always secure with private keys?

Any encryption scheme can be insecure if the key space is small enough.

For example, you could perform encryption with an 8 bit RSA key.  For a key of that size, it's trivial to determine the private key given the public key.


ECDSA Public key randomness If I have a 256bit ECDSA public key how likely is it that the same public key will be generated by another person. Will it take on average 2^256 tries to generate same public key? If I xor the first 32bytes of the public key over the second 32bytes and only have 32bytes is it now 2^128 tries to generate the same 32byte data? Or less? Thanks

ECC public keys are not random numbers.

They are generated through a scalar multiplication of a random scalar with a known/public point on the curve, called Generator.

The entropy lies entirely in the random scalar. Two public keys will collide if the random scalars collide.

When you say "256bit ECDSA  public key" you probably mean that your elliptic curve curve is defined over a finite field whose size is approximatively $2^{256}$. This would explain why you are mentioning a public key of 64 bytes in your question.

Now, in cryptographic secure elliptic curves, that size is closely related to the size of order of the generator, which is actually the size of your random scalar.

Therefore, without knowing the exact curve you are using I can't exactly answer the question. But approximatively the expected probability is: $\frac1{2^{256}}$

This has nothing to do with the encoding, so xoring the key over itself doesn't really make sense to me, or I didn't understand it.