additive ElGamal encryption algorithm I'm performing ElGamal encryption algorithm and using the additive homomorphic property so the product of two ciphertexts is the encryption of the sum of the plaintexts.

The problem is that I need to return the original plaintext sum values.
How could I get them using decryption?
Is there an algorithm I can follow, given that I have both the private and public keys?

I have tried to decrypt it, but it returns the value $((g^{x+y}) \bmod P)$ where $p$ is prime, $g$ is a generator, and $x$ and $y$ are the plaintext which I need to know.

$x+y$ is usually a very large number.

Normal El Gamal is multiplicatively homomorphic: $E(x) E(y) = E(xy)$.

If you want to make it additively homomorphic, you fix some generator $g$; then you transform the integer $x$ to the group element $g^x$ before encrypting with El Gamal.  With this transformation, $E(g^x) E(g^y) = E(g^x g^y) = E(g^{x+y})$, so now you have an additive homomorphic property.

To decrypt, you need to be able to take the discrete logarithm.  This can be done efficiently if the value $x+y$ is known to be "not too large".

For a bit more of an overview of this approach to making El Gamal additively homomorphic, see the following question: Can Elgamal be made additively homomorphic and how could it be used for E-voting?.  Then, check out Why is the discrete log problem easy when the exponent comes from a binomial distribution? for details of specifically how to do the decryption, and how small the messages need to be to ensure you can decrypt in a reasonable amount of time.
In the future I encourage you to use the search function to check whether the question has been asked before.

If $x+y$ is usually so large that the above methods don't work, then you'll need a different cryptosystem; simple El Gamal isn't gonna work for you.  The Paillier cryptosystem might be a good choice.


Random permutation of bit strings of length $n$, where $n$ can be any positive integer? I need an efficient, invertible random permutation of $n$-bit strings, defined by a $128$-bit key. $n$ can be any positive integer from $6$ to $128$. I have no requirements on the security of the permutation; only that it is random (i.e. that outputs for different keys are uncorrelated).

Many standard algorithms exist for $n$ of $32$, $64$, and $128$ bits. I wondered if the Sponge Construction of Keccak could be used to transform such permutations into $n$-bit permutations. I understand the sponge construction generates a function of variable input length and arbitrary output length. However, it is not clear that if I use it to generate a function to turn one $n$-bit string into another $n$-bit string, that that function will encode a random permutation. Does it?

Format Preserving Encryption is the name for a standard way of doing what you are asking.  It does a keyed mapping from a (potentially small) domain to itself.  It does more than you are asking (it tries to be secure; you specified that you didn't need that), however there should not be an issue with this.

You have already found it yourself, however if you were to ask me which FPE primitive to use, I would have suggested FF1.

(I'm putting this as an answer so you can accept it)


Is there any more asymetric-time permutation than x^3 (mod p)? I've been using "asymetric-time bijective functions (or permutations)" for several practical uses. I've applied them to solve problems in software-attestation and proof of unique blockchain storage.

An asymmetric-time permutation is basically a public permutation F that takes a lot of time to perform in one direction (expensive direction) and very short time in the inverse direction (cheap direction). The most interesting property of an a-t permutation is the asymmetry ratio, which is the (average) ratio between expensive and cheap computation times.

This is a practical construction that is evaluated both ways in a protocol so the expensive computation must not be unfeasible: it may take 1 second of computation for a target CPU. Generally the expensive direction time is chosen so that is takes more than the time a response must be sent by a prover in an interactive challenge-response protocol.

One of the best a-t permutations I found is $f^{-1}(x)= x^3 (\bmod p)$, where $p$ is a large prime. The ratio is $O(n)$, where $n$ is the number of bits in $p$.

Another desired property is that you cannot break F by pre-computing and then turn expensive evaluations into cheap ones. So the domain size must be $> 2^{64}$.

The a-t function may have other desired properties, such as the ability to probabilistically test if $f^{-1}(x) = y$, given only a part of $x$ chosen by the challenger.

Are there other a-t functions with comparable or higher asymmetry ratios?

Candidates may be a trapdoor function such that the trapdoor is unknown and no third-party trust is required (nothing up my sleeve number). In other words, the verification logic must be public, and not limited to the challenger.

Note: I think I'm the first to specifically focus on a-t functions and its practical applications, but let me know if you find any prior mention.

One approach is suggested by the ideas introduced by this paper.  I'll spell them out for you:

The verifier selects two large safe primes $p, q$ (that is, primes where $(p-1)/2$ and $(q-1)/2$ are also prime), the value $n = p \times q$, an integer $z$, and a quadratic residue ($\bmod n$) $a$.
The challenge (the "hard direction") is, given the values $n, z$ and $a$, compute $a^{2^{z}} \bmod n$
The verification (the "easy direction") is, given $a^{2^z} \bmod n$, recover $a$ (which is moderately easy to do, effectively an RSA operation, if you know the factorization of $n$).

This is a trapdoor function, but one which the verifier knows the trap door (and doesn't need to rely on anyone else).  This works fine if we have a unique verifier (as in a challenge-response system); it's less useful if the verification logic needs to be public.

And, the function is a permutation, if we restrict ourselves to the quadratic residues modulo $n$.

The point of this construction is that the asymmetry ratio can be as large as desired; it's effectively $O(z / \log n)$, as $z$ is an arbitrary integer, we can set this to whatever we feel like.


How do salt and initialization vector differ? Reading through the NodeJS API docs I came across IV for the first time. From what I can tell it has the same role as a salt in password hashing? Are they equivalent?

The term salt and IV are indeed largely used to provide the same functionality. They differ mainly for the type of algorithm. Both are used to ensure that the output is not purely determined by the input.
IV's or salts don't necessarily have to be random, they may just be unique. In that case the functions output is pseudo-random; the randomness is taken from the entropy in the key material (or password) instead. The requirements (the output size, if they need to be randomized or not) for the salt and IV depend on the algorithm used.
The term IV - Initialization Vector - is generally associated with block cipher modes of operation. Most of these modes use some kind of chaining of operations. As the name implies the IV is just the "first vector". This can be most easily shown by looking at CBC-mode of operation: here every plaintext block is XOR'ed with the previous ciphertext  block (the vector) before it is fed into the block cipher, but the first plaintext block is XOR'ed with the IV instead.
Salt is a more generic term which is often used in combination with KDF and KDF-related algorithms. You'll often see the term mentioned in combination with password hashing (i.e. a PBKDF) and password based encryption (PBE). The salt is then used to derive unique key material. You may also see the term salt used for other pseudo-random functions such as MGF1 which is used for modern RSA encryption (RSA-OAEP) and signature generation (RSA-PSS).


Why does GnuPG save an array of remainders when generating prime numbers? In looking at GPG's gen_prime() function, found within the cyphers/primegen.c file of libgcrypt, I noticed that the functions saves a list of the remainders from dividing the initial, randomly generated large number by the first 669 or so small prime numbers. What is the purpose of doing that? I don't see any reasoning behind doing so within the file.

What they're doing is doing a fast test to see if a candidate prime prime+step has any of the smallest 669 primes as a factor (by testing whether prime%p + step is a multiple of the small prime p.  If they do find that the candidate has a small factor, then it is obviously not prime (and so they don't need to spend the comparatively long time running the Fermat test).

That being said, the code in primegen.c could have been done more efficiently.  What is more usually done is creating a sieve; that is, you create an initially clear bitmap corresponding to the first (perhaps) 2000 entries of prime+step; for each small prime p, you compute prime%p, and based on that value, mark off every entry in the bitmap that corresponds to a multiple of p.  Once you've done that, you can then step through the bitmask; any bit which is still clear corresponds to an entry with no small factors; you can then run your expensive primality tests on that.  The advantage of this method is that you need to deal with each small factor only once; this means it is more effective to have far more small primes that you test against (and so you eliminate more composites during the cheap part of your primality search)


A missing step in ECDSA signature verification implementation On the Wikipedia page of ECDSA, it is stated in step 6 of the verification algorithm that If (x1,y1)=O then the signature is invalid.

In X9.62, it is also stated that If u1G + u2Q is the point at
infinity, then reject the signature.

However, I cannot find explicit checking for this condition in multiple open-source libraries.

python-ecdsa for example:

xy = u1 * G + u2 * self.point
v = xy.x() % n
return v == r

Is there any implicit checking that I missed?

And is there any possible attacking against this, if such a verification was missed?

A lot of libraries will define the point at infinity as $\mathcal{O} = (0, 1, 0)$ (or as $(0, 1)$ if using affine coordinates). Note that the Wikipedia article you link states:

  Verify that $r$ and $s$ are integers in $[1,n-1]$. If not, the signature is invalid.

And a little further down:

  The signature is valid if $r\equiv x_1 \pmod{n}$, invalid otherwise.

So if we represent the point of infinity as having an x-coordinate of zero then we see that $r$ can never be equal to $x_1$ as $r$ must be explicitly checked to be in the range $[1, n-1]$ which implies $r > 0$.

python-ecdsa performs the checks from step 1 in lines 132-135. It does not, however, represent $\mathcal{O}$ as mentioned above, but rather sets INFINITY = Point(None, None, None). So If we get xy = INFINITY in the verification call the method will throw an exception as the modulo operator in v = xy.x() % n will be called on None.

It's not clear if this exception is caught or expected by the calling code, but in any case the verification call will not return that the signature is valid when this happens.


Is there any chance of failure in Cryptography With my limited knowledge of cryptography and its correct terms, functions (md5, base64, sha, aes or whatever) turn an input into encrypted output. For example, if the following input turns into following output:
input | output
______________
A     |  XX
B     |  YY
AB    |  ZZ

my question is: do such cryptography functions involve proven mechanism to avoid the failure of "repeated-output"? I mean, is there any chance, if inputing AB provides ZZ output, can there be any other input (like %) that might have the same output ZZ ?
What is the mechanism to ensure there doesn't exist two different input that provide the same output?

What you are talking about is called collision resistance.
Base 64 is an encoding technique. It doesn't use a key and therefore it is not a cipher. Encoding techniques commonly have a 1:1 relation with the output of course, so no collisions there.
Pseudo-random permutations such as block ciphers have a 100% collision resistance as a permutation always has a 1:1 relationship between the input and the output. So AES and (3)DES will never repeat output for different input. Beware that this changes if a block cipher mode of operation is used to turn it into a real semantically secure (probabilistic) cipher; in that case you'd would expect collisions that depend on the output size, see the final part of this answer.
MD5 is a message digest or cryptographically secure hash function. Hash functions are supposed to have a certain collision resistance. Collisions are of course certain as there are more messages than output values (see the pigeon hole principle). However, it should be computationally infeasible to find them. MD5 is considered broken and fails on this principle, which is why it is not actually considered "cryptographically secure" anymore.
As for the "whatever": cryptography consists of many algorithms, and the outcome depends on the algorithm. If the output is supposed to be indistinguishable from random and there are $n$ different outputs then you'd expect a $1 \over n$ chance of that a value is equal to a preset earlier output value. However, due to the birthday bound you'd expect to compare only $\sqrt n$ values against each other before you find a collision with a 50% chance of success.
In the case of MD5 with an output size of 128 bits, so $n = 2^{128}$- you'd expect a collision in about $\sqrt {2^{128}} = 2^{64}$ compares. That means a collisions resistance of 64 bits in other words. However, because it is broken attackers can create collisions much more easily. Generally cryptographers aim to have a security margin of 128 bits, which means that MD5 is considered insecure with regards to collision resistance even if it was not broken.


AES key with DES3_CBC_PAD mechainsm I am new to cryptography and have a question.
If I try to wrap some key using an AES key using DES3_CBC_PAD as a wrapping mechanism will this go to work?
I am doing this operation inside an HSM.

No, likely this won't work. Almost all HSM's will only accept wrapping keys of a type that is compatible with the encryption / wrapping algorithm. Commonly it is impossible to get to the value of the key as well, so that won't save you.

Sometimes you can wrap a key to export it and then re-import it again. Then you might be able to create a new AES key from the remnants of the exported key. You would of course then use AES-192 or AES-128 if you use only the first 16 bytes of the ciphertext. Generally this won't work for FIPS mode though, so applicability might be limited. And you'd of course loose 16 bits or more of key space because of the parity bits - so security would be at the same level as 3DES.

A better option would be to derive an AES key from the triple DES key. Of course, this also needs to be possible in your HSM and the key must be usable for the key derivation mechanism. That way you would get a different key value, but one that is still linked to the value of the DES key(s).


When do I need to use CBC and HMAC? As I know CBC does not provide integrity for the message, thus HMAC is used to provide integrity for CBC message. Also, I hear about CBC-MAC which can provide integrity and confidentiality. Which one is better CBC-MAC or CBC with HMAC?
And when do I need to use CBC and HMAC?

Also, there is CBC-MAC for providing integrity and confidentiality. Which one is better CBC-MAC or CBC with HMAC?

Generally, asking which one is better results in opinionated answers.

However, since CBC-MAC cannot be used for dynamically sized messages and may lead to compromise when the same key is used, HMAC definitely is less prone to abuse. Differently worded: CBC-MAC is more brittle than HMAC: it may break when abused.

That CBC-MAC it can still be used correctly is shown by the CCM authenticated mode of operation, which uses AES-CTR for confidentiality and AES-CBC-MAC for message integrity & authenticity. It is unwise to replace CTR mode with CBC in CCM mode because CBC with CBC-MAC is likely to introduce security vulnerabilities.

[EDIT]: I completely read over the fact that this says "integrity and confidentiality". CBC-MAC is a MAC algorithm that has been derived from the CBC mode of operation, hence the name. It does not provide confidentiality itself, it provides just message integrity and message authentication. See Luis' answer for more details. This is also why it is unwise to pair CBC and CBC-MAC (see previous section).

  And when do I need to use CBC and HMAC?

You could use it when message integrity and/or message authenticity is required on top of the confidentiality that CBC mode offers. That is: if you are afraid that the ciphertext can be altered by an adversary. Generally transport protocols require message integrity / authenticity.

However, generally we use a modern authenticated mode of operation for that. AEAD ciphers such as AES-GCM and EAX are more robust than putting CBC and HMAC together. For instance, it would be easy to forget to include the IV into the calculation of the authentication tag. If that's forgotten than the adversary can still alter the first block of ciphertext. Likewise, CBC requires an IV that is indistinguishable from random to the adversary, while most AEAD ciphers require a nonce (which could be random, but it could also be a counter).

EAX uses CMAC (or OMAC) as MAC internally. CMAC has been build on top of CBC-MAC to make it secure for dynamically sized messages. The earlier mentioned CCM mode that does use CBC-MAC is also secure, but as a packet mode cipher it can be hard to use (let alone implement, as I found out).

There is an RFC draft called Authenticated Encryption with AES-CBC and HMAC-SHA which tried to standardize CBC and HMAC as an AEAD cipher. That didn't succeed (most other modes are more efficient) but if you want to use CBC with HMAC then it shows a few best practices.


Multiplying two additively shared values Alice has $p_a,q_a$ and Bob has $p_b,q_b$, all elements of a ring $R$.
They want to obtain shares of the value $pq$ where $p=p_a+p_b$, $q=q_a+q_b$. How do they do this ? Does revealing their shares of $pq$ leaks their shares of $p,q$? I am supposing that in the ring $R$, it is hard to deduce $p$ and $q$ from $pq$.

This cannot be achieved information-theoretically. This is typically the task that requires multiparty computation protocol to be achieved. In particular, the common method for what you want is called "secure multiplication protocol", and is in general constructed from an additively homomorphic encryption scheme (over the ring $R$), or from oblivious transfer.

Exemple with the encryption scheme:
Alice holds $p_a,q_a$; Bob holds $p_b,q_b$. Alice picks an encryption scheme $E()$ and sends the public key to Bob. She keeps the secret key. Then, she sends $E(p_a), E(q_a)$ to Bob, who computes (using the homomorphic properties of the scheme $E()$) and sends back $E(p_aq_b + r_1), E(p_bq_a+r_2)$, where $r_1$ and $r_2$ are fresh random coin. Alice decrypts these values and get $(u_1,u_2)$. She computes $n_a = u_1 + u_2 + p_aq_a$; Bob computes $n_b = -(r_1 + r_2) + p_bq_b$. You can see that $n_a + n_b = (p_a+p_b)(q_a+q_b) = pq$; the fact that this does not reveal $p$ nor $q$ can be proven assuming the encryption scheme is IND-CPA secure (id est indistinguishable against chosen plaintext attacks).

To answer your second question, if $pq$ is hard to factor, then even knowing it, it is computationally infeasible to recover the shares of $p$ and $q$ of the opponent - however, it does obviously not leak "nothing" in an information theoretical sense.


Enumerating the bias of NIST and Pearson randomness extractors The following is an extract from a paper about using your mobile phone as a true random number generator (TRNG). The mobile phone bit is incidental to this question though.  I'm interested in the calculated bias of the $M \times r$ matrix extraction mechanism. Specifically equation 5 at the bottom.

A. Does a similar bias equation exist for a cryptographic hash based extractor such as SHA-X? NIST advice simply states that if you extract less than half of the input entropy, you'll be fine.  If you plug in values for SHA-1 with a 320 bits of entropy input you get   $\epsilon = 2^{-80}$. That's below the NIST (DRAFT Special Publication 800-90B, August 2012) bias threshold of $2^{-64}$ for declaring a sequence as having 'full entropy'. I suspect that it is exactly the same equation, and that it's generic to all extractors.

B.  Could one derive another similar bias equation for using an 8 bit Pearson hash as an extractor? Using Pearson with it's random permutation is not a million miles away from a vector matrix. Yes it's got that XORy thing in it, but otherwise the transmission of bias principle must still exist, and equally similarly must depend on the length of the input entropy.

Part A takes precedence.

If $M$ is a uniform random $l \times k$ matrix, then the random function $H\colon x \mapsto M \cdot x$ is a 2-universal hash family[1] (paywall-free: (a), (b)).  This means that for any $l$-bit strings $x$ and $y$, $\Pr[H(x) = H(y)] \leq 1/2^k$.

If $H\colon \{0,1\}^l \to \{0,1\}^k$ is a 2-universal hash family and the random variable $X \in \{0,1\}^l$ has min-entropy $H_\infty[X] = s\cdot l$, then $H(X)$ has total variation distance at most $\epsilon$ from the uniform distribution on $k$ bits, where $\epsilon = 2^{-(s l - k)/2}$.  This is the leftover hash lemma.  (Sometimes it is phrased instead as: if you want TVD $\epsilon$ from uniform, then you must pick $k \leq s\cdot l - \log(1/\epsilon^2)$.)

The total variation distance between two discrete random variables $R$ and $S$ is $$\frac 1 2 \sum_x |\Pr[R = x] - \Pr[S = x]|.$$

What does this all mean?

We are considering a probabilistic model.  This is a model of an uncertain state of knowledge, such as the adversary's, about the specific values of $H$ and $X$ in this model, but we can quantify the uncertainty of this knowledge by giving numeric weights to each of the possible values:

$H$ has a probability distribution on $l \cdot k$ matrices that is uniform.

This means for any specific value $h$ that $H$ could take on, $\Pr[H = h] = 1/(l \cdot k)$, since there are $l \cdot k$ distinct $l \times k$ matrices.

One possible matrix is the matrix that returns the first $k$ bits of an $l$-bit string.  For this particular choice of matrix, the min-entropy of the result depends entirely on the first $k$ bits of the input and not at all on the last $l - k$ bits.
Another possible matrix is the all-zero matrix, in which case $H(x) = 0$ for all $x$.  For this particular choice of matrix, the min-entropy of the result is always exactly zero!  But it is only with probability $1/2^{l \cdot k}$ that $H$ is the all-zero matrix.
The point is that no particular matrix makes a randomness extractor; it is rather a probability distribution on matrices that does.

You could pick a value for $H$ by flipping a coin $l \cdot k$ times and filling in the matrix entries with the outcomes.
$H$ is not uniformly distributed in all functions from $l$-bit strings to $k$-bit strings: there are many functions that $H$ cannot be, namely those that do not have matrix representations.  For example, $H$ cannot be SHAKE128.

$X$ has a probability distribution that has min-entropy $s \cdot l$.

This means that the maximum probability of any specific value that $X$ could be is $2^{-s\cdot l}$; that is, $-\max_x \log_2 \Pr[X = x] = s \cdot l$.

Given this state of knowledge about $H$ and $X$, the two theorems let us conclude that our state of knowledge about the output $H(X)$, a $k$-bit string, is a probability distribution with at most $\epsilon$ in total variation distance from the uniform distribution.  That is, $$\frac{1}{2}\sum_y \bigl|\Pr[H(X) = y] - 1/2^k\bigr| \leq 2^{-(s l - k)/2}.$$

The total variation distance between two random variables $R$ and $S$ is relevant to usual theorems in cryptography because it turns out to be a bound on the advantage of a random algorithm $A$ at distinguishing them, $|\Pr[A(R)] - \Pr[A(S)]|$.  (There are other metrics of probability distributions too, such as KL divergence (or symmetrized KL divergence to get a proper metric), Hellinger distance, etc.  Which one you use depends on what your needs are.)  So this almost says something useful for cryptography.

But what if the adversary knows $H$?  Then the conclusion goes out the window!  In the paper you cited, the matrix $M$ is a pregenerated constant.  So either,

by Kerckhoffs' principle, you should assume that the adversary knows $M$, i.e. $M$ is public, so it cannot satisfy the conditions of the leftover hash lemma and it is meaningless to use with a randomness extractor; or
you already have a sufficiently large uniform random secret, namely $M$, that you can use with a standard cryptography like ChaCha or SHA-3 to expand into as many keys as you need; or
you don't believe in cryptography, but then you probably wouldn't be hanging around here.

In other words, as this paper applies randomness extractors, either it fails to satisfy the premises of the theorem ($H$ is secret), or it does satisfy the premises of the theorem which makes the conclusion unnecessary for cryptography.

On to the specific questions you asked:

A: What if we choose $H$ to be a fixed function, yet instead of choosing a fixed matrix we choose a fixed ‘cryptographic hash function’ like SHAKE128?  It is hard to say, because unlike universal hash families, cryptographic hash functions are designed not to have any interesting properties like linearity of matrix multiplication.

Suppose we model it as a uniform random function from $l$-bit strings to $k$-bit strings.  For every distinct input $x$, the output $H(x)$ is an independent uniform random $k$-bit string—every possible output is equiprobable.  This model is much stronger than a randomness extractor in some sense even though the adversary has access to it as a public oracle, and this model, like all models, is wrong, but some models are useful.

Suppose $X$ has $s \cdot l$ bits of min-entropy.  What is the expected min-entropy of $H(X)$, over uniform random choice of $H$?  To make a conservative estimate of this, let's say $X$ is really just a uniform random $\lambda = \lfloor s \cdot l \rfloor$-bit string.  For any fixed function $h$, the min-entropy of $h(X)$ is $-\max_y \log_2 \Pr[h(X) = y]$.  Note that $\Pr[h(X) = y] \leq (C(h) + 1)/2^k$, where $C(h)$ is the number of possible $k$-bit strings that $h$ does not reach, since in the worst case of min-entropy, there is a single output that is reached $C(h) + 1$ times instead.  Consequently, $$-\max_y \log_2 \Pr[h(X) = y] \geq -\log_2 (C(h) + 1)/2^k = k - \log_2 (C(h) + 1).$$  $\log_2$ is concave, so $E[\log_2 (C(H) + 1)] \leq \log_2 (E[C(H)] + 1)$.  What's $E[C(H)]$?  First, the probability that we do not reach a particular output $y$ is

\begin{align*}
 \Pr[\lnot\exists x. H(x) = y]
 &= \Pr[\forall x. H(x) \ne y] \\
 &= \prod_x \Pr[H(x) \ne y] \\
 &= \prod_x (1 - \Pr[H(x) = y]) \\
 &= \prod_x (1 - 1/2^k) \\
 &= (1 - 1/2^k)^{2^\lambda}.
   \end{align*}

By linearity of expectations, this is also the expected fraction of unreachable outputs, so the expected number of unreachable outputs is $E[C(H)] = 2^k (1 - 1/2^k)^{2^\lambda}$.  When $\lambda \leq k$ this puts an unsatisfying bound on the min-entropy, which happens because to set a hard bound we made an extremely conservative estimate of a colossal collision of all inputs with any collisions into a single output that feels very abused right now.

But $E[C(H)]$ rapidly goes to zero as $\lambda$ increases.  Specifically, for $k \geq 1$, we have $1 - 1/2^k \leq e^{-1/2^k}$, so $$E[C(H)] \leq 2^k e^{-2^\lambda/2^k} = 2^k e^{-2^{\lambda - k}} \leq 2^{k - 2^{\lambda - k}}.$$  Consequently, as long as $\lambda \geq k + \log_2 k$, $E[C(H)] \leq 1$, so the min-entropy is at least $k - \log_2 (E[C(H)] + 1) \geq k - 1$.

For a distribution on $k$-bit strings with min-entropy $k - \delta$, where $\delta = \log_2 (E[C(H)] + 1)$, can we set an upper bound on the total variation distance from uniform?  Suppose for simplicity that $N = 2^{k - \delta}$ is an integer; the greatest TVD is attained by assigning probability $1/N$ to $N$ of the $k$-bit strings, and probability $0$ to the remaining $2^k - N$, so that the TVD is bounded by

\begin{multline}
 \varepsilon
 = \frac 1 2 N \biggl|\frac{1}N - \frac{1}{2^k}\biggr| + \frac 1 2 (2^k - N) \biggl|0 - \frac{1}{2^k}\biggr| \\
 = \frac 1 2 N \frac{2^k - N}{N 2^k} + \frac 1 2 \cdot \frac{2^k - N}{2^k}
 = \frac 1 2 \cdot \frac{2^k - N}{2^k} + \frac 1 2 \cdot \frac{2^k - N}{2^k} \\
 = \frac{2^k - N}{2^k}
 = \frac{2^k - 2^{k - \delta}}{2^k}
 = 1 - 2^{-\delta}.
   \end{multline}

For $\delta = 1$, the the TVD is bounded by $\varepsilon = 1 - 2^{-1} = 1/2$, but the bound $\varepsilon = 1 - 2^{-\delta}$ rapidly approaches zero as $\delta \to 0$.

A more practical way to put it is: The security conjecture of, e.g., SHAKE128 is that there is no better attack at guessing $X$ given $\operatorname{SHAKE128-}\!k(X)$ than a generic search through all possible values of $X$, whose expected cost is at least $2^{H_\infty[X]}/2$ trials, or $2^k/2$, or $2^{256}/2$, whichever is smaller.

(Of course, if there are $n$ targets $X_1, X_2, \dots, X_n$, the cost to find at least one of them given $\operatorname{SHAKE128-}\!k(X_1),$ $\operatorname{SHAKE128-}\!k(X_2),$ $\dots,$ $\operatorname{SHAKE128-}\!k(X_n)$ is $2^{\min\{256, H_\infty[X_1], \dots\}}/(2n)$ instead, i.e. there is a standard factor of $n$ cost reduction for an $n$-way multi-target attack.  This is why it is a good idea either to use 256-bit seeds $X_i$, or to use a globally unique per-seed salt.)
B: What if we choose $H$ to be a Pearson hash, i.e. CBC mode of a uniform random permutation?  By the standard CBC theorem, algorithm limited to $q$ queries on inputs up to $m$ $b$-bit blocks can't attain better advantage than $mq(mq - 1)/2^{b+1}$ at distinguishing $H$ from a uniform random function, and any algorithm to distinguish the output from uniform random bit strings would serve as an algorithm to distinguish the hash from a uniform random function, so the ‘bias’ (here meaning distinguishing advantage) of the resulting distribution is bounded by $mq(mq - 1)/2^{b + 1}$.

Of course, you need at least about $2^b b - 2^b \log_2 e$ bits to store such a permutation, which rapidly becomes impractical as $b$ exceeds 8, the typical size for what gets called a Pearson hash.  You could accommodate a much larger block $b$ by choosing the permutation to be $\operatorname{AES}_k$ for a uniform random key $k$.  But that's only a minor setback.  Much worse: The whole premise is nonsensical, because however you do this, you need a secret permutation to begin with, which is back to begging the question with a randomness extractor: If you already had a long enough secret, you wouldn't need a randomness extractor or a Pearson hash; if you don't have a long enough secret, you can't use a randomness extractor or a Pearson hash and get anything meaningful out of the use.


What primitives are needed to generically implement public-key cryptography? Public-key cryptographic systems are often implemented on top of an existing problem. For example, RSA is built on top of integers and the difficulty of factoring. ECDSA/ECIES are built on top of elliptic curves and the difficulty of the discrete logarithm.

My question is, what are, mathematically speaking, the exact primitives needed to implement public-key based signature and encryption cryptography in a generic way?

Unfortunately there is no real answer to this. We know that one-way trapdoor permutations suffice, but this is really just an abstraction of factoring. ECDSA/ECIES/ElGamal don't work via any trapdoor permutation, and neither do lattice-based public-key encryption schemes.

In the private-key world, we know that one-way functions are necessary and sufficient. However, we have no analogous primitive that is both necessary and sufficient for public-key encryption, beyond itself. (That is, of course, public key encryption is both sufficient and necessary for public-key encryption, but this is a very annoying answer that means nothing.)

Note, that one-way functions are sufficient for building digital signatures, and so the question of what is necessary is really only for public-key encryption.


Free software for randomness test I have a sequence of integers between 0 to 100. Is there any free software like Sage, where I can test randomness of this sequence? I have Linux machine.

To clarify:

I have huge data set. Actually I have my own generator. I want to test its randomness.

Tests of randomness with only data as input can give proof of non-randomness, but never a credible indication of randomness unless their result is coupled with an analysis of how the random data tested has been generated. Without such knowledge, such tests give a falsely reassuring PASS, or a FAIL.

Illustration: consider the PRNG that outputs 512-bit blocks computed as the HMAC-SHA-512 of the previous block under some key. That pass any randomness test for one not knowing the key, yet is trivially predictable from past output with that knowledge.

In cryptography, randomness tests with PASS result can only be useful when and if we have a model of the source tested. This is at the heart of the AIS31 methodology of Common Criteria evaluation for True Random Numbers Generators in things like Smart Cards; see there (under AIS31; the page exists in German only AFAIK, but has links to many documents in English and a Reference implementation of the statistical tests).

Per the AIS 31 methodology, it is made some model matching the device, and justified that per that model, any likely defect that do not raise alarm won't result in using a significantly predictable bitstream. Typically there is:

a TRNG based on some analog phenomenon, e.g. sampling of a noise source, delivering a bitstream that can be sampled for testing purposes;
hardware or/and software testing that source, at startup and/or runtime, in order to check that this source delivers entropy; including, at least, something that raise alarm if anything makes that source totally defective (that could be an attacker with a needle, a laser, evaporation of some liquefied gas..);
a hardware or/and software conditioning of the output of that source, into another bitstream, that won't have discernible bias even if the source is only passable; that conditioned bitstream can be used e.g. as source of randomness for DPA countermeasures, or a key generator.
possibly, an additional test that conditioning works as intended.


Is AES-GCM length extension attack possible using authenticated decryption? I am looking to encrypt a piece of data using AES-GCM with a full 16-byte GCM Tag and send it over the network using UDP. Is it safe to assume using the AEAD nature of AES-GCM that performing authenticated decryption will prevent ciphertext length extension attacks with an implicit length?

In short, I want to determine the length of the ciphertext by looking at the UDP packet size and removing my app specific headers. This avoids the need for an explicit ciphertext length. Explicit length would increase the per-packet overhead, and every byte counts on the network.

Can I derive the length or must I specify it explicitly?

Section 5.3 (Page 44) of https://eprint.iacr.org/2013/144.pdf suggests while the GCM Tag includes length, it is still vulnerable to at least one weakness. But reading that, I'm not left with the impression that adding an explicit length into the AD would make a difference.

(Note: Originally asked this question on security.stackexchange.com, realised it was wrong site so re-posting here)

I did some more research and yes it does include both AD length and ciphertext length, so is not vulnerable to a length extension attack as length is part of GCM GHASH.

Based on NIST SP-800-38D (PDF) page 18 len(A) and len(C) are both part of the input into the GHASH function.

And double-checked this in an implementation gcm_finish method: both lengths are added to the hash at the very end.
https://github.com/polarssl/polarssl/blob/master/library/gcm.c


Can big numbers multiplication be a valid form of encryption? I have a vector of int called $Xreg = [x1, x2, ..., xn]$ that I need to send from a client to a server for storage in a database.

If an attacker gains access to the database or the server he shouldn't be able to recover the original vector $Xreg$.

To do so, I had the idea to multiply each component of $Xreg$ with two big numbers ($S0$ and $S1$) of 512 bits each.

Therefore the client will send $S0.S1.Xreg$ = $[S0.S1.x1, S0.S1.x2, ..., S0.S1.xn]$.

The client will keep the record of $S0$ and creates a new $Si$ each time he wants to connect to the server.
Therefore the second time, client will send $S0.S2.Xreg$ and server will replace it in the database.

My question is, if a malicious or semi-honest adversaries gains access to the server or the database will he be able to recover the original $Xreg$ ? Let's suppose that if the server is compromised, the communications will stop so the attacker could possibly get only one record of $S0.Si.Xreg$ and possibly $S0.S_{i-1}.Xreg$ and $S_i/S_{i-1}$

Thanks in advance.

Given a vector $[S_0 S_1 x_1, S_0 S_1 x_2, ...]$, it is quite easy to recover $S_0 S_1$ (by computing the GCD of the various elements).  With that information, the attacker can then recover the values $x_1, x_2, ...$, and so yes, a semihonest adversary could easily recover the $X_{reg}$ values.


Winternitz Signature Scheme Verfication I am reading page 39 in this "Post Quantum Cryptography" book. Why does equation 15 hold? There is no further knowledge about f and you definitely cannot use any power laws. So, why is $f^{2^w-1-b_i}(f^{b_i}(x_i)) = f^{2^w-1} $ valid?

I have my doubts, because $f(x) = x+1$ is already a counterexample.

In this notation, $f^k(x)$ means "apply $f$ $k$ times in succession".  For example, $f^3(x)$ is defined to be $f(f(f(x)))$.

Because of this definition $f^a(f^b(x)) = f^{a+b}(x)$ holds trivially (even though we known nothing else about $f$), as the the left side means "do $f$ $b$ times, and then do it $a$ times", while the right means "do $f$ $a+b$ times".

$f(x) = x+1$ is not a counterexample.  In this case, we have the simplification $f^k(x) = x+k$ (for example, $f^3(x) = f(f(f(x))) = (((x + 1) + 1) + 1) = x+3$, and so $f^{2^w-1-b_i}(f^{b_i}(x)) = 2^w - 1 - b_i + (b_i + x) = 2^w-1 + x = f^{2^w-1}(x)$


Generating a key pair using a signature generated by an existing key I’ve built an app in which each user has a private/public key pair and I want to generate a second one for them, however I cannot store the second private key anywhere.

What would be the drawbacks of deterministically generating the second private key from static information signed by the first one, compared to generating it randomly? I could generate it again each time a user opens the app but is it safe?

This is in the context of a web app on Ethereum, which uses deterministic ECDSA.

Several issues with the proposition of generating a derived private/public key pair as (or from) a signature computed with a master private key.

Not all signature schemes are deterministic, thus what's proposed might end up not allowing reproduction of the derived key.
We would need to discriminate the particular message input to the signature scheme used to generate the derived key, and ensure that an adversary can not obtain the signature of that message with the master key, thus ruining the confidentiality of the derived key.
For arbitrary signature scheme, we could imagine some security issue where signatures (past and future) with the master key weaken signatures with the derived key.

A more conservative option is to use the master private key itself as the key input of a symmetric Key Derivation Function (unrelated to the signature scheme), which output is (or is used to deterministically generate) the derived key. This can be generalized to any number of derived keys, using an auxiliary input of the KDF for a derived key type or index. That option assumes that the master private key is not in a box/HSM/Smart Card/enclave restricting its use to signature, and that a strict policy to the same effect is not in force (which is common, e.g. by reference to FIPS 186-4).

Update: a comment mentions that the master private key is not directly accessible (making the above conservative option impossible); and a deterministic (variant of) ECDSA.

If we can reserve a message $C_D$ (solving 2.), post-processing as$$\text{DK}\gets(H(\text{Sign}_\text{MK}(C_D))\bmod(n–1))+1$$seems to be good way to derive a private key $\text{DK}$ from master private key $\text{MK}$, with $n$ the generator's order and $H$ a hash at least 64-bit as wide as $n$ is. The modular reduction and 64-bit limit is per FIPS 186-4 apendix B.4.1. If $H$ is secure in the Random Oracle Model and as costly as a signature verification, then this is computationally secure (argument: an attack allows to forge the signature of $C_D$, or otherwise breaks the signature scheme, or the hash). It can only help to use a purposely slow KDF for $H$.

The above formula assumes ECDSA with only the signature TRNG changed to a deterministic PRF keyed by the private key. For EdDSA, we only need to hash the signature of the reserved message $C_D$ to the width of a private key, and condition that with the masking prescribed in EdDSA.

More generally, with a deterministic signature scheme, a reserved message, and a key generation procedure using a KDF independent of the signature scheme and at least as costly as signature verification, we are good to go.

Caveat: any key derivation should be performed in a safe environment, or otherwise guarded from side channels.


Solving discret log problem Can the discret log problem be solved when the modulus is a hard to factor composite number, i.e. when modulus $n=p*q$, where $p$ and $q$ are two large prime numbers?

The problem is solving for $x$ the equation $g^x\bmod n=a$, given integers $n$, $g$, $a$, with $n$ a large composite too difficult to factor (which implies $n$ is several hundreds bits). It is not stated how instances of the problem are generated.

That is hard at least for some instances of the problem. In particular, if one of the factor $p$ of $n$ is large (say, at least 1536-bit), and $p-1$ has a large factor $p_0$ (say, at least 256-bit), and the order of $g$ in $\Bbb Z_p^*$ is $p_0$ or a larger multiple, then an instance of the problem where $x$ was chosen at random in $[1,n/2]$ and $a$ computed as $g^x\bmod n=a$ is hard. Argument: ability to solve $g^x\bmod n=a$ for $x$ and knowledge of the factorization of $n$ trivially implies ability of solving $g^x\bmod p=a\bmod p$ for $x$ (modulo $p-1$), which is is believed hard; and lacking knowledge of the factorization of $n$ can only make the question's problem harder.

I conjecture without proof that the condition "$p$ large" can be replaced by the existing "$n$ too difficult to factor"; and that a random instance is hard.

Among the usual Discrete Logarithm methods, Baby-step/Giant-step and Pollard's Rho remain applicable, with cost $O(\sqrt x)$ multiplications modulo $n$ (and moderate memory for Pollard's Rho). That allows to solve instances with moderate $x$ (say 80-bit with a standard PC), but I see no better method to solve a random instance.


Proof that a hash matches an encrypted file Assume that Alice has a file $F$ which she is going to send, in encrypted form to Bob.  Alice possesses $F$ and an encryption key $K$. She sends to Bob the encryption of $F$ using $K$, $E(F,K)$ as well as a compact message authentication code which could be the hash of the file $H = {\rm hash}(F)$, which is used as a unique blinded identifier of the file.  It's assumed that multiple users may have the same file, encrypted with different keys, and we wish to detect that they are the same by virtue of $H$ being the same, but Bob needs to know that $H$ matches $F$ without having $F$ unencrypted.

Does there exist any kind of proof that the hash $H$ (or other compact MAC) corresponds to the file $F$?  The hashing/MAC algorithm and encryption algorithm (symmetric, asymmetric, homomorphic) are secondary to being able to prove this.

If you use a one-time pad as your encryption function then this simplifies to a proof that Alice knows some $F$ that hashes to $H$. $K$ can be trivially derived from $F$ and $E(K, F)$ by xor-ing.

An interactive zero-knowledge proof of this simpler problem - Alice proving she knows a pre-image of $H(F)$ - would go something like this:

You need to use a partially homomorphic hash such that $H(A+B) = H(A) \oplus H(B)$ for some composition operation on each domain. An example might be to add/xor the pre-images and use scalar multiplication of an elliptic curve base point as your hashing function - though note for an arbitrary length message this is going to be magnitudes slower than a traditional cryptographic hash function.

In a single trial in the proof Alice generates a one-time pad - $P$ - and commits to $H(P)$. Bob calculates $H(F+P) = H(F) \oplus H(P)$. He can challenge Alice to reveal either $P$ or $F+P$. Each trial halves the probability that Alice is cheating.

You can turn this into a non-interactive proof by Fiat-Shamir. It's not very succinct however, the proof ends up being many times longer than $F$.

I guess with a homomorphic DRBG you could extend the proof to show that Alice knows a stream cipher key $K$ that defines the tranformation $F \rightarrow E(K, F)$. This would improve the succinctness of the proof as well as being a closer match for what you asked for.


What does "$<\!\!<\!\!<$" mean? What does the symbol $<\!\!<\!\!<$ mean? It is normally followed by a number. An example:

It would be appreciated if you could explain it in fairly basic terms.

$$x<\!\!<\!\!<k$$ normally means cyclic rotation of a bit string $x$ to the left by $k$ bits.


One Encryption, Many Decryption Keys I would like to share access to encrypted data among many recipients. I do not know the recipients ahead of time (when encrypting the data). Once the data is encrypted, I do not have access to the plaintext (so I cannot re-encrypt).

Right now, I have a shared secret key that is distributed to recipients as they are granted access to the data (again, encrypted so I do not have access ot the shared key). Unfortunately, that means any recipient of the shared secret can leak the key, compromising the data for everybody.

I can't really prevent "bad" recipients from the leaking the key (or the plaintext, for that matter), but I would like to be able to distribute unique keys to each recipient so that if a key is leaked, I can determine who did it.

I think I want a symmetric encryption scheme where the ciphertext can be decrypted by a set of keys, rather than a single key. Each secret key is unique and it's hard to derive one secret key from another (so one recipient cannot forge another's key), but its simple for me to generate new secret keys (so I can easily add new recipients).

Does such a schema sound familiar?

This is known in the cryptographic literature as "traitor tracing".  See, e.g., the following seminal paper:

An efficient public key traitor tracing scheme.  Dan Boneh and Matt Franklin.  CRYPTO 1999.

They show a public-key encryption scheme where each  possible recipient has their own private decryption key.  If an authorized recipient discloses their decryption key, it's possible for the authority to figure out whose key it was.  Moreover, they consider a further challenge -- what if a coalition of authorized recipients pool everything they know, and come up with another decryption key that is different from each of theirs but still works, and they leak that new key? -- and they show how to deal with that challenge as well.

There is an entire line of research that proceeds forward from there.

That said, this is often the wrong kind of solution in practice, for most situations.  You are assuming/hoping that the adversary will publish their decryption key.  But what if they don't?  What if they do something else?  There are all sorts of ways the adversary could cause problems without publishing their decryption key:

For instance, the adversary can leak the decrypted data without leaking the decryption key (this is the killer problem with all of these traitor tracing schemes that has rendered them mostly irrelevant in practice).
Alternatively, the adversary could make available an API that provides "decryption as a service".
Or, the adversary might release software for decryption that embeds the key but in an obfuscated form.

Traitor tracing doesn't help with any of those adversarial strategies.  So, beware that your threat analysis might be based on too narrow a view of what an attacker can do.

More fundamentally: this approach has seen no adoption in commercial systems (as far as I am aware), because of the extreme ease of acquiring false identities.  If you're going to sell access to paid content for $20, and you accept credit cards for payment, it's far too easy for someone to get a stolen credit card number, sign up and gain access, and then publish the decryption key (or the decrypted content).  Now what are you gonna do?  Even if you can trace back to the associated credit card number and name provided during signup, that name is surely fake, and the name on the credit card account is someone else.   At that point you realistically have no way to identify the perpetrator and no recourse.  All the fancy crypto in the world won't save you.

That's why these kinds of schemes might not be as useful as they at first appear, except in some special and limited circumstances.


openSSL ECDH private key size When you are using a named curve like P-256 in openSSL, is there any standard key size for ECDH private key keys?

If you look at the ec_key.c file in the openSSL source this is what you see:

BN_rand_range(priv_key, order)

Here a cryptographically strong random number is generated which is smaller than the order.

Yes, P-256 generates 256 bit private keys (give or take a single bit).

The confusion here is that this key is 256 bit effective (giving ~128 bit security) even if it starts with zero bits. So the private key is 256 bit even if the representation as a large integer can be smaller than the requested size. This simply means that the full key space is being used. So there is a relatively big chance (about 1/256) that the big endian encoding of the integer is one byte smaller. Most libraries however require an integer to octet string primitive to be used (I2OS or I2OSP). This represents the private key in a static number of bits, e.g. 256 for the above.

The same is true for RSA by the way. Always expect numbers to start with a random number of zero bits, unless this is explicitly not possible. And be warned against signed/unsigned representations, of course.


Can you identify this algorithm? We are attempting to integrate our application in to a third party system. To do this we need to pass encrypted passwords in to this system. I have decompiled the assembly and looking at the code it seems that they are using something similar to XOR encryption (In a production system...) From what I can see from the decompiled code it does something like this:

The pseudo code bellow is wrong. Here is a link to the source code, decompiled , converted to C# and cleaned up a bit: http://pastebin.com/rAcXPvL6

string key = "1234567890123456"
string plainText = "test"
int[] keyData = GetAsciiValuesAsArray(key)
int[] plainData = GetAsciiValuesAsArray(plainText)
int prime = GeneratePrimeNumber()
string cipherText = ""

foreach(plainTextChar in plainData)
{
     int a = prime / 256.0 * 256.0 - prime % 256 / 256.0
     int b = prime % 256
     for(int i = 0; i < 16;i++)
     {
          keyData[i] = keyData[i] ^ GetAsciiValue(plainTextChar);
     }
     plainTextChar = plainTextChar ^ (a ^ b)
     int c = (plainTextChar / 16.0 * 16.0 - (plainTextChar % 16)) / 16.0;
     int d = plainTextChar = % 16
     cipherText = cipherText + ConvertFromAscii(c + 97) + ConvertFromAscii(d + 97)
}

Does this seem familiar to anyone? Hopefully it's a recognized algorithm and not something they have cobbled together themselves.

Thanks,

Joe

First: Analyzing code is off-topic on this site, don't expect much.

To the question: "Never write your own crypto" is a statement, that is all too often disregarded. Without digging deep, it looks like some self-made (and totally insecure) algorithm: The key is not used at all, therefore it is basically a streamcipher (one symbol at a time) with a deterministic keystream.

Recommendation: Do not use this, and don't use their crypto implementations in the future. Not every error is as easy to detect as this one. And in crypto you can do lots of things wrong.


How to secure Elliptic Curve ElGamal encryption against known plaintext attacks? If I have an encoding function  $f(x)$ that maps a message $m$ to a point $P$ on a suitable Elliptic Curve $E$ . If I have the public key $Q$ of my recepient then I can encrypt the message as follows:

Choosing a random number $k < n -1 $ where $n$ is the order of the curve E .

Calculating $C = [k] G $ where $G$ is the generator point of the curve E

Calculating $R = [k]Q $ where $Q$ is the recipient's public key

Now the message is encrypted by adding $P$ to $R$ to get
        $C_e$ $( = R + P)$ which is sent along with $C$ to the recepient.

DECRYPTION:

Now for the recepient to decrypt my message they compute $R = [privatekey] C $ (where $C = [k]G $) and simply subtract $R$ from $C_e$ to get the encoded point $P$ back which is then decoded by an inverse function $f^{-1}(x)$ to recover $m$.
Now , two problems arise : If the attacker knows the plaintext (suppose if I follow a particular format of data while sending messages ) he could encode his guessed plaintext and subtract it from $C_e$ to recover $ R $ back ! . If I used that same $ R  $ to encrypt further "blocks" of my message then the security of the later parts of my message has been breached!

I realize that doing  something like a scalar multiplication over and over again for every block of data, would be a huge drawback in efficiency and speed.

Is there any way to compute a different $ R $ for every block of data, without using much resources and that too quickly ?

Does reusing the same $R$ for another message break security ?

NOTE: This question is for educational purposes only. It's for the sake of expanding my knowledge on Crypto.

Is there any way to compute a different $R$ for every block of data, without using much resources and that too quickly ?

There's no common way. Standard practice is hybrid encryption per ECIES.

In a nutshell, ECIES is the same as EC-ElGamal with regard to $E$, $G$, $\text{privatekey}$, $Q$, $k$, $C$, $R$, but the shared secret $R$ is used (after a key derivation step) as the key to a symmetric authenticated cipher that conveys the message $m$. This removes the burden of mapping $m$ to a point on the curve, which severely limits the size of $m$, and typically is iterative thus has the potential to leak information about $m$ by side channels.

  Does reusing the same $R$ for another message break security (in EC-ElGamal)?

Yes. Assume $m_0$ and $m_1$ mapped to $P_0$ and $P_1$ are encrypted with the same $R$, into $C_0$ and $C_1$. It holds $C_0=R+P_0$ and $C_1=R+P_1$, therefore $P_1=P_0-C_0+C_1$. Thus $m_1$ can be found from $m_0$ and ciphertext. With $R$ fixed, the cipher is insecure under known-plaintext attack.

Additions per comment:

Even if the attacker has no knowledge of a plaintext $m_0$, s/he does learn something about the plaintext. In particular she can tell if $m_0=m_1$, since that's equivalent to $C_0=C_1$. This qualifies as a break, since the objective of encryption is to prevent adversaries from learning anything about plaintext (except its length). As an example, this allows to distinguish between a routine Have a quiet nightshift Joe ($m_0=m_1$) from an exceptional Launch missile to target A ($m_0\ne m_1$).
Doubling $R$ at each message would be extremely insecure. It would hold $P_j+P_j-P_{j+1}=C_j+C_j-C_{j+1}$, and that allows to decipher any message sent encrypted twice, as $P_j=P_{j+1}=C_j+C_j-C_{j+1}$.


Difference between single-pass and two-pass MACs I am having trouble understanding where the count of "passes" come in. What constitutes a pass in the context of message authentication codes? How are single-pass MACs achieved?

I suspect the questioner is asking not about MAC's per say, but rather Authenticated Encryption (AE, and if there is additional data, AEAD).  I've been wondering this myself, so I asked Phillip Rogaway of UC Davis, who is one of the creators of EAX - a "two pass" "online" operation mode for block ciphers that - since it provides AE (confidentiality and integrity in the same process) does not need a MAC.
His response is really quite helpful - so (with his permission) I'm quoting it here:

There's no standard and rigorous definition of "one pass" vs. "two pass" for AE / AEAD schemes.  Focusing only on encryption and the processing of plaintext, people mean either of two things by the terms “one pass” and “two pass”:

“One pass” (or “online”) could mean that the algorithm is constructed so that you can process an arbitrary length plaintext, left-to-right, spitting out the corresponding bits of ciphertext, again left to right, as you  go, while you use only constant memory.   In this sense, EAX is one-pass. This notion is easy to make rigorous. “Two pass” would then be interpreted to mean that you can make due with two constant-memory left-to-right passes through the plaintext, but not one.  And so on.

Alternatively, “two pass” might mean that, when a human being looks at the description of the mode, there is one logical part of the design, this comprising a significant portion of the computational cost, that is clearly designed for privacy; and there is another logical part of the design, again a significant portion of the computational cost, intended for authenticity.  One pass would mean that you can’t partition things up like this: that the privacy and authenticity are more tightly interwoven (often with an “authentication tag” being computed cheaply as a byproduct of whatever else is going on for privacy).  I don’t know any way to make this concept rigorous, but I think it’s the more traditional use. Under this (informal) notion, EAX is two-pass, despite it being online. To help separate these uses, and stop calling something “two pass” when it could easily be implemented so as to be online, my paper with Krovetz on OCB3 introduced, for sense (2),  “integrated” and “composed” instead of “one pass” and “two pass”. I don’t think these terms caught on ;-)

And for the curious, the papers he refers to is (I think) The Software Performance of Authenticated-Encryption Modes
I found (after getting his answer) his FAQ quite helpful - especially this answer.


Derived Shared Key vs Distinct Keys? I've seen a lot of 2-party applications that derive a shared key from distinct keys created by each party.

Why is this technique employed? Would it not be better to use those two distinct keys for each party (where both parties know both keys, but each key is used to encrypt and decrypt the messages of the party who created it)?

As an example, I've seen socket servers that use this. Assume 2 servers are running. Both servers send a random 256-bit key, encrypted with the other's RSA public key to each other. This leads to 2 distinct keys that both servers now know. Then both servers XOR these two keys together to derive a common key. Why this is done instead of using both keys in the way I described above?

For your example protocol with RSA-exchange in both directions, combining both keys to one protects against some weaknesses:

By combining the random numbers from both sides, the result is really random,
even if one of them has a weak or compromised randomness source.
If one of the private keys is compromised, in your protocol the attacker can
read all the data flowing to its owner. If we combine the random data by XOR
with the other random data to derive the session key, the resulting key is
still unknown to an attacker, and she can't read anything.

Of course, for the actual encryption (and authentication, i.e. a MAC key), you should then use not this combined master secret directly, but derive different keys for the different purposes from it. This avoids some replay attacks.


Will our app be FIPS 140-2 compliant if we use our own AES algorithm implementation? We are in the processing to understand if our software applications is FIPS 140-2 compliant or not. Currently in our application, we are using our own implementation of AES algorithm. AES is a FIPS 140-2 compliant algorithm.

The question would be whether this would render our app not FIPS 140-2 compliant since we are not using FIPS validated library (Advanced Encryption Standard Algorithm Validation List) even though we are using a FIPS compliant cryptographical algorithm.

Again, we are not try to certify our application for FIPS 140-2, rather we just want to make sure that we are FIPS 140-2 compliant.

If you are using an AES library that has not undergone the FIPS validation process, then you are not FIPS compliant (or, at least, your use of AES is not).

FIPS compliant means more than "we use algorithms that FIPS likes", it means "having passed the FIPS certification process"; that is how NIST defines it.

Sorry, but NIST is quite strict about this; if you haven't undergone the full testing, then NIST is concerned that you haven't implemented AES correctly; there may be subtle bugs that affect the security.  And, since NIST makes up the rules for what's "FIPS compliant", well, there's no point in arguing about its likelihood.

In addition, FIPS talks more than what algorithms you use; it also talks about health tests and key zeroization and other such things; the FIPS certification process checks all that as well.

If you need to be FIPS compliant, then your choices are:

Use a FIPS-certified library to perform all the FIPS-approved crypto operations
Go through the FIPS-certification process for your application (or, at least, the crypto pieces of your application).

The FIPS certification process is surprisingly complicated; I'd advise you to use a FIPS-certified library.


With known ciphertext and plaintext, find other party's Three Pass Protocol Key? If I'm the second party participating in a three pass protocol (for simplicity, let's say Shamir's Three Pass Protocol) such that:

Bob sends me a ciphertext
I encrypt it and send it back
He removes his encryption and sends it back to me
I decrypt it fully

Using the information in steps 1 (ciphertext) and 4 (plaintext), how difficult is it for me to determine the key that Bob is using?

I know that this is a somewhat esoteric use-case, but I'm curious.

how difficult is it for me to determine the key that Bob is using?

This is essentially the discrete log problem; Bob's key is a value $b$, and his encryption mechanism is computing the value $P^b \bmod p$.  Given $P$, $P^b \bmod p$, recover $b$ is the definition of discrete log.

Actually, you get two pairs of values encrypted with Bob's key; the plaintext (encrypted in step 1, and recovered in step 4), and the exchanged ciphertext (which you see encrypted in step 2 and decrypted in step 3); however having multiple pairs doesn't actually make the discrete log problem any easier.

So, if the group is large enough to make the three pass algorithm secure (for example, large enough that someone hearing the values in steps 2 and 3 could not recover Bob's key), it's also large enough to make recovering the symmetric keys by you infeasible as well.


Is linear secret sharing over the addittive group of integers modulo $p$ with $p$ non-prime secure? In Maurer, Ueli. "Secure multi-party computation made simple." Discrete Applied Mathematics 154.2 (2006): 370-381. I have found the following technique for $k$-out-of-$k$ linear secret sharing:

And the note regarding the domain says this:

Is using as domain $\mathbb{Z}_p$ (additive group of integers modulo $p$) with $p$ non-prime secure? Does it make any difference if $p$ is prime or not? What is the most general definition for the domain (I do not get exactly the meaning of the note)? My guess is that $p$ can be any integer.

What is the most general definition for the domain (I do not get exactly the meaning of the note)? My guess is that $p$ can be any integer.

In short, a domain is the input space. As said the input space can be any domain. Note that the secret $s$ is from the domain, too.
The note simply says that whatever the domain $\mathscr{D}$ is we can simply impose an addition operation on it. Order them, and number them starting from 0. Now, if the number of elements in the domain is $n = |\mathscr{D}|$ then it is equal to $\mathbb{Z}_n$ which is a cyclic group under addition.

Is using as domain $\mathbb{Z}_p$ (additive group of integers modulo $p$) with $p$ non-prime secure?

Yes.

Does it make any difference if $p$ is prime or not?

It doesn't make any difference. This secret-sharing doesn't need the multiplicative inverses. Any finite group can be safe. All we need is the group operations.

As Kodlu mentioned in the comments

This secret scheme can also be defined on the multiplicative groups where the inverse exists naturally. Take each $s_i$ for $1\leq i\leq k-1$ random from the domain and calculate $$s_k = s \cdot s_1^{-1} \cdot s_2^{-1} \cdots s_{k-1}^{-1}$$


Can a salt for a password hash be public? From my understanding, salts in password hashes are used to prevent the precomputation of plaintext→hash values (rainbow tables).
I know from different threads that it is unnecessary to keep the salt secret (i.e., it doesn't need to be encrypted), but I wondered if it would be a problem by making it public.
The background of this question is the following idea:
For password authentication, a strong hashing function like bcrypt or scrypt is used. Every user has their own random and unique salt. However, to minimize the load on the server, the hash is calculated on the client-side. For this to be possible, a function must exist that allows an unauthenticated user to retrieve any registered user's salt.

The usual answer is that a salt can be make public; if that was a problem, then the salt would not be called a "salt" but a "key".

In some protocols, unauthenticated obtention of the salt is the norm, and is not considered to be a problem. E.g. with SRP, a password-authenticated key exchange, where any salting and hashing must necessarily occur client-side.

Some people have argued that if the attacker can know the salt in advance, then he can do precomputations. This is a gain for the attacker only in a specific scenario, where the context is such that the attacker must be able to crack a password within a very short time frame (say, one second) but has a few weeks to prepare for his one-second attempt, for a specific target user. This is a fringe scenario which very rarely applies.


How does the sender obtain the receiver's public key? Cryptography process includes encryption and decryption process. In public key cryptography public key of receiver is being used for encryption.

I want to know how public key of receiver is sent to sender?

The sender receives the public key through some other (secure) channel.

The whole security of public key encryption relies on precisely this "small detail": there must be a way for the sender to obtain the receiver's public key through some other, secure channel. The definition of "channel" is actually very broad here, and denotes simply a means of transferring information.

To name but a few real world examples of what can be used to exchange keys:

A trusted key server or repository, e.g. OpenPGP public key servers like sks-keyservers.net.
A file downloaded from a website which is trusted to belong to the person whose public key you wish to obtain, and the connection to this website is secure and properly authenticated (i.e. using HTTPS).
The receiver sends the public key on the same channel as the one it intends to receive the message, but the key's authenticity can be verified by a trusted external party such as a PKI (Public Key Infrastructure).
A USB stick, disk, piece of paper or some other type of media handed over in person.
A telephone call (!).

Of course, one should nevertheless not forget that there is a myriad of attacks which can be performed on these channels too, such as using fake certificates issued by rogue CAs in order to bypass HTTPS or also flooding public keyservers with fake PGP keys. After all, a cryptographic protocol can only be as secure as the less secure of its parts.


Using related pair of cryptographic keys to open/seal plaintext I am using curve25519xsalsa20poly1305/fn.seal from sodiumoxide crate written in Rust language which is a wrapper over libsodium c library and that function calls crypto_box_curve25519xsalsa20poly1305 in libsodium library.

The rust code would look something like this:

let (pub_key, sec_key) = ::sodiumoxide::crypto::box_::gen_keypair();
let nonce = ::sodiumoxide::crypto::box_::gen_nonce();

let data = vec![0; 10]; // plain-text

// Cipher-text
let encrypted = ::sodiumoxide::crypto::box_::seal(&data,
                                                  &nonce,
                                                  &pub_key,
                                                  &sec_key);

println!("Encrypted: {:?}", encrypted);
assert!(data != encrypted);

How much is it a security concern if i use a related key-pair (Public, Secret Key pair) generated through crypto_box_curve25519xsalsa20poly1305_keypair in calling that function?

Will this be regarded as a potential weakness, given that only I intend to encrypt and decrypt it? I know it is better to use symmetric encryption in this case but just for learning purposes – what is the security risk ?

You are effectively using symmetric encryption.

The crypto_box function uses elliptic curve Diffie–Hellman on Curve25519. With a given input private key and public key it always generates the same symmetric key, which is then used for authenticated encryption. By using the private and public key from the same key pair you are generating the point $a^2G$, which with a random $a$ is just a random point on the curve. This point is then used to derive a symmetric key for authenticated encryption.

Of course, it would be more efficient to just use that derived key (or a random key) in the first place, but as long as you keep the key pair secret, what you are doing is secure.


Which hash function is used for signatures ssh-rsa and ssh-dss? I'm building a fuse client for ssh/sftp. I write the required ssh and sftp functions myself. Now I read in RFC4253 that before signing the data to sign is default hashed. In RFC4253 8. "Diffie-Hellman Key Exchange" SHA1 is mentioned as the default for ssh-dss. What is it for ssh-rsa?

In section 6 of RFC 4253 it says on page 15:

  The "ssh-rsa" key format has the following specific encoding:

  string    "ssh-rsa"
  mpint     e
  mpint     n

  Here the 'e' and 'n' parameters form the signature key blob.

  Signing and verifying using this key format is performed according
  to    the RSASSA-PKCS1-v1_5 scheme in [RFC3447] using the SHA-1 hash.

So the answer is "SHA-1" as well.


How can two different passphrases unlock the same content? I have heard that in enterprises it is common that the IT admin has a master passphrase that can unlock any content that an employee encrypts.

It would be temping to think, that the IT admin's passphrase is encrypted with the employees passphrase, but then the IT can't change his passphrase.

How does such encryption actually work?

Is there a cryptographic secure method of doing this?

Another method to the ones described above would be ID-based encryption where a trusted third party, called the Private Key Generator (PKG), generates the corresponding private key based on the user's identity (whether it be domain name or email address).

Given the master public key, any party can compute a public key corresponding to the identity ID by combining the master public key with the identity value. To obtain a corresponding private key, the party authorized to use the identity ID contacts the PKG, which uses the master private key to generate the private key for identity ID.  If only part of the master private key is used to generate the corresponding private key, then the PKG can generate two private keys by using different parts of the master key.  That way, the user will have one private key, and management the other.

Whether or not this is secure depends on how much you trust the third party PKG.

For further information, have a look at the following link.

ID Based Encryption

Also have a look at the following article:

Identity-Based Encryption from the Weil Pair

If you do a search on the title, you should be able to find the associated PDF.


How to truncate MAC to 32 bit? I want to use MAC as an additional protection of UDP-server from DoS attacks.
I prefer to keep MAC as short as possible and I assume 32 bit is good enough for this purpose.

I'm going to make it based on some well-known MAC (e.g. KECCAK Message Authentication Code)
Is it bad idea to use CRC32 of this MAC?
Or it is better to use first 4 bytes of MAC?

Don't truncate one-time-macs (e.g. GHash or Poly1305) because a successful forgery reveals part of the key. Poly1305 might be fine, if the receiver ensures nonce uniqueness and you derive the complete Poly1305 key from the nonce (i.e. both the multiplier and the mask).

On the other hand, truncating HMAC or MACs based on CBC-MAC (e.g. CMAC) is fine (I think it even avoids the prefix-weakness of plain CBC-MAC).

I would not consider CRC32, it's unkeyed and I can't think of an easy to build a secure MAC from it (GHash is probably the closest thing to a secure CRC).

I recommend going with a truncated HMAC. It's designed to be a PRF and since truncated PRFs are still PRFs, you can be certain that it has no weaknesses beyond the obvious $2^{-32}$ forgery chance.


Possible combinations of 8 digits, 6 upper case letters, 2 distinct numbers Assume I want to find out how many combinations there are for a 8 digit word with 6 uppercase letters and 2 distinct numbers, e.g. A7BC9DEF, 1A0CRDEF, ... how many combinations are there?

My approach's solution is : $26^6 \cdot 90 \cdot 8 \cdot 7$

90 because there are 90 possible numbers with two distinct digits, i.e. $01, 02, \ldots, 09, 10, 12, \ldots, 21, 23, \ldots, 98 \rightarrow 99 - 9$ valid numbers)

$8 \cdot 7$ because the digits of the 90 possible numbers can be found at $8 \cdot 7$ different indices.

I had combinatorics a long time ago in school so I thought asking here for clarification might be a good idea. Thanks in advance!

Close.

It's $26^6 \times 90 \times 8 \times 7 / 2$; the $/2$ is there because having the digits appear in locations 1 and 3 is exactly the same as having the digits appear in locations 3 and 1, and hence there are only 45, not 90 distinct locations where the digits may appear.


Is it possible to test 15-bit PRNG with the library TestU01? The library TestU01 inconvenient for generators that don't produce 32-bit outputs.  But is it possible to somehow test say a 15-bit generator with it?  How could that be done?

For instance, the generator included in the book ``The C Programming Language'' by Brian Kernighan and Dennis Ritchie is a 15-bit generator.  Is there any way to test it against the TestU01 library?

For example, I could take 2 numbers from the generator and concatenate its bits, giving me a number with 30 bits.  I still need 2 more bits to make 32 bits.  I can get these two last one from another number from the generator (and ignore the 13 bits left of the third number).  But this is changing the generator.  It's a different thing now.

It can be taken groups of 32 samples of 15 bits, and turned each into 15 samples of 32 bits, either by transposition, or concatenation then splitting.

The best of the two method depends on the nature of the test, and TestU01 has several tests (as test suites do). If in doubt, use both methods. Should any valid test consistently fail more than predicted by its P-value, the generator has been demonstrated broken.

As always: absent any information on the generator tested, passing a statistical test gives zero insurance about its suitability for cryptographic purposes.

  For instance, the generator included in the book The C Programming Language by Brian Kernighan and Dennis Ritchie is a 15-bit generator.

/* rand: return pseudo-random integer in 0..32767 */
int rand(void);

A 15-bit wide output can be cryptographically OK, but this generator's narrow key (an int) makes it a no-no from a cryptographic standpoint, even when we consider only its interface to set the key:

/* srand: set seed for (rand) */
void srand(unsigned int seed);

Further, when we consider the details of the implementation

unsigned long int next = 1;

/* rand: return pseudo-random integer in 0..32767 */
int rand(void)
{
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
}

/* srand: set seed for (rand) */
void srand(unsigned int seed)
{
    next = seed;
}

we note that

Only the low-order 31 bits of next and seed matter to the output, even when intand long are much wider (since next * 1103515245 + 12345 gets truncated to some number of low-order bits of the mathematically accurate result when it overflows; bits of next diffuse on the left only; and those above 31 do not make it to the result of rand).
Among these operative 31 bits of next, 15 are known from one output, making it trivial to perform a brute-force search of the other 16 bits to recover the full state from 3 consecutive output. And there are even simple methods avoiding enumeration, thus scaling the generator from 31-bit to 256-bit would not make it secure.

Thus this particular generator is totally weak from a cryptographic perspective. Yet it still gets a pass from many statistical tests (including Ent applied to a few kilobytes of its output); and a scaled-up version of that generator would pass even more tests for all practical sizes.

Due to the particular structure of this generator, the best way to demonstrate that it is weak from the results of a byte-oriented Chi-squared test like Ent might be to keep the low-order 8 bits of each 15-bit output, and throw away the rest. But that's not a general rule, it depends a lot on the generator, and also on the test.


secp256k1 point density I am working on a crypto project using the secp256k1 elliptic curve.

I know that I can select a random point $P = (x, y)$ from the curve by randomly selecting the first coordinate $x \in \mathbb{Z}_p$ (where $p$ is the prime of the elliptic curve field $\mathbb{F}_p$) and computing the second coordinate $y$ using the curve equation $y^2 = x^3 + 7$. Because the cofactor of the curve is $h = 1$, for every value $x \in \mathbb{Z}_p$ that spawns a valid $y \in \mathbb{Z}_p$, there is a point on the curve with coordinates $x, y$. In case there is a value $x \in \mathbb{Z}_p$ for which the curve equation does not find a valid value for $y \in \mathbb{Z}_p$, that means there is simply no point on the curve at that $x$ coordinate.

I also know that the curve order is $q$, with $q < p$. That means there exist $q$ valid points on the curve, which is less than all the values that $x$ could have in $\mathbb{Z}_p$.

My question is: How far are points from each other, in respect to the $x$ coordinate? What is the largest distance between two points on the curve? Is there any documentation in this regard?

I  also know that the curve order is $q$, with $q<p$. That means there exist $q$ valid points on the curve,

True

  which is less than all the values that $x$ could have in $\mathbb{Z}_p$

Actually, that's less relevant than you think.

For every $x$ value in $\mathbb{Z}_p$ that has a valid solution, there are two values of $y$ that satisfy the equation (and hence correspond to two points).  It's easy to see, if $(x, y)$ is a solution, then so is $(x, -y)$ (aka $(x, p-y)$)

Note: some elliptic curve have 1 or 3 $x$ values that correspond to a single $y$ value (which is the $y$ value 0) - secp256k1 is not one of those curves.

In addition, there is a single 'point of infinity' which doesn't correspond to a solution to the equation, but is thrown in as an additional group element.

Hence, there are exactly $(q-1)/2$ $x$ values that correspond to (at least one) valid point.  Since $p \approx. q$, this if you pick an $x$ value at random, you have almost exactly a 50% probability of picking one with a solution.


About LFSR based M209 Cipher Machine Can some one please express M209 Cipher Machine in terms of LFSR with Diagram or any simple method?

The M-209 cipher machine cannot be expressed as an LFSR because it is not LFSR-based. It is its own construction, using six adjustable key wheels whose initial positions acted as the key for ciphering. Its operation is vaguely similar to a standard substitution cipher, but the substitution positions would change for each letter, making cryptanalysis more difficult. It had a period length of 101,405,850.

See also https://en.wikipedia.org/wiki/M-209


How to use `openssl asn1parse` or equivalent on output files from `ssh-keygen -t rsa -b 4096`? I generate an ssh key:

~ ssh-keygen -t rsa -b 4096
Generating public/private rsa key pair.
Enter file in which to save the key (/Users/kurtostfeld/.ssh/id_rsa): rsa_key
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in rsa_key.
Your public key has been saved in rsa_key.pub.
The key fingerprint is: <snip>

If I use an empty passphrase, I can successfully parse the private key file like this:

~ openssl asn1parse -in rsa_key

If I use a non-empty passphrase. This doesn't work. How can I parse an RSA private key with a passphrase. What format is that?

Also I can't parse the public key at all. This doesn't work with or without a passphrase:

~ openssl asn1parse -in rsa_key.pub
Error: offset too large

How can I parse the RSA public key?

The private key is like a PKCS#8 encrypted private key. However, it misses the wrapper that indicates the type of encryption used. Instead, this information is present in the PEM header.

-----BEGIN RSA PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: AES-128-CBC,12FF93A74CD3E34DFEF8B1CF04FFEFA6

bsUb0TiyTU9RML8PteBhjd1vwdDv/MB8kR6+J1506dkS3+t1b6mEYNKDkZeQYPPt
...
mnLNzPODtVFrEeinQcfzQCCIS+VOrtTE3dJ3bklN8he3qQmnDC9+nyQsX2Q8EuUw
-----END RSA PRIVATE KEY-----

So the base 64 encoded contents of the PEM encoded private key is just the ciphertext that makes up the wrapped private key. As the ciphertext is indistinguishable from random you won't find much structure in there. To parse it you will first have to decrypt it.

As for the SSH public key, the key is in OpenSSH compatible format, which isn't specified using ASN.1 and doesn't use BER/DER encoding.

ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAACAQDTYu/U8i2a+AVe0GnZJbpJCRFwPa4yN0S77x0ZTKUudzx9OXf20reuiaDarH6x+r1XMvh/9EwarRw3CquXAdEIZ4O2AZHmgvkQCJK1Q7ZRN3rpfIrMMPqjf7NLAEmUNoI/oS977jSynRtBK001NGD4YqY9uuFLyMHPqEwR9Ii
...
/yE8pvaO6qJIIzNbTQ== maartenb@Lenovo-PC

So trying to parse it using the asn1parse will obviously not work. You would need to use SSH itself for that. One way of doing that (the long way) can be found here.


Implementing the Pohlig-Hellman cipher I need to use Pohlig-Hellman exponentiation cipher for reasons explained here. However, I can't seem to find an implementation of this cipher anywhere. It doesn't seem to be too difficult to implement from scratch - so, I want to try.

I do have the following questions:

How do I go about choosing primes? According to this, I should choose a large random prime such that (p−1)/2 is prime. But what algorithm should I use to do that? Also, is 2048 bits enough for my purposes (some context below)?
How do I go about choosing keys? I think these should be large random numbers, but how large? I would like to make the encryption as secure as with other more commonly used ciphers.

To give a bit more context: I would be encrypting relatively small messages. Vast majority of my messages will be under 32 bytes, and no message will be larger than 64 bytes. I will be padding and scrambling messages using salts before encrypting them to avoid deterministic output.

Choice of public modulus $p$

Using for $p$ a large safe prime (that is, a prime $p=2q+1$ with $q$ also prime) is the way to go for the Pohlig-Hellman cipher, because that

simplifies the choice of encryption key $k$: a random odd $k$ in range $[1,q-2]$ will do, because that ensures that $\gcd(k,p-1)=1$ (the condition for validity of an exponent in the Pohlig-Hellman cipher);
makes recovering $k$ from sample plaintext/ciphertext pairs $(m,c=m^k\bmod p)$ conjecturally hard, and in particular avoids the case where $p-1$ would be smooth, allowing to find $k$ quickly by the Pohlig-Hellman Discrete Logarithm algorithm.

To guard against the Discrete Logarithm variant of the SNFS algorithm, it is also recommendable that $p$ is not of the special form $r^e\pm s$ for small $r,s$.

Provided this, there is consensus that, baring apparition of Quantum Computers usable for cryptanalysis or spectacular algorithmic progress, a 3072-bit $p$ is most likely fine for some decades (say, comfortable 128-bit security), and 2048-bit likely fine .

Because the requirements for $p$ are the same as for Diffie-Hellman key exchange, there are ready-made, unobjectionable $p$. The $p=2^{3072}-2^{3008}-1+2^{64}\cdot(\lfloor2^{2942}\pi\rfloor+1690314)$ of the 3072-bit MODP Group of RFC 3526 is suitable (hex value below)

FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA051015728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6BF12FFA06D98A0864D87602733EC86A64521F2B18177B200CBBE117577A615D6C770988C0BAD946E208E24FA074E5AB3143DB5BFCE0FD108E4B82D120A93AD2CAFFFFFFFFFFFFFFFF

Intentionally, for this $p$ and its 1536 to 8192-bit analogs:

leftmost 66 bits are ones, which simplifies quotient estimation in classical modular reduction;
rightmost 64 bits are ones, which similarly eases Montgomery arithmetic;
most center bits are borrowed from $\pi$, and the few-digits constant is minimal to reach a safe prime, so these are nothing-up-my-sleeves numbers.

Choice of encryption key $k$ and decryption key $k'$

The requirement is that $k$ is a secret coprime with $p-1$; that is, with our choice of $p=2q+1$ with $q$ prime, that $k$ is odd and not a multiple of $q$. This ensures there exists a matching decryption key $k'$ with $k\cdot k'\equiv1\pmod{p-1}$, which in turn insures (by a straightforward application  of Fermat's little theorem) that for any message representative $m$ with $0\le m<p$, ${(p^k\bmod p)}^{k'}\bmod p=m$ ; that is, encryption of $m$ with $k$ followed by decryption with $k'$ will get back to $m$.

It is enough to choose $k$ as a truly random odd integer in range $[1,(p-3)/2]$, or some sub-range of that (with a bare minimum of about $2^{2b}$ possible values for $b$-bit security, with no constructive proof that's enough). For example, if $p$ is $n$-bit, it is fine to draw $n-4$ random bits, append a one bit on the left and on the right to form an $(n-2)$-bit odd integer (that works regardless of endianness). What's critical is that the generator uses some unguessable entropy, and that the key $k$ (and matching $k'$ ) are kept secret, including during use. Protection against side channels is going to be a serious issue.

The decryption key $k'=k^{-1}\bmod(p-1)$ can be computed with the (half) extended Euclidean algorithm. Another method giving $k'$ is computing $k^{q-2}\bmod q$ and adding $q$ when the result is even.

Note: as stated in the question, constructing the message representative $m$ from the actual data to transmit should be done with care. A safe option would be to reuse the OAEP construction of RSA.


Combine signature with encryption I have some embedded device for which I want to sign and encrypt firmware files. Firmware updates are generated by me and may be installed by the customer. The encryption is supposed to protect the intellectual property contained in the firmware and the signature prevents unauthorized modifications.

For the signature there are tons of resources, but I’m having problems with the encryption part. The simplest solution would be a shared symmetric encryption key. In case the encryption key gets extracted from the device one could not only decrypt the firmware, but also create your own encrypted firmware (without a valid signature). Are there a better alternatives using asymmetric encryption, so that less information is available when the device keys are extracted?

No, asymmetric encryption or other known purely cryptographic techniques do not solve the problem stated in the question. When device keys are extracted, any (future, see below) firmware update for that device can be deciphered.
The best we can do in this direction without some trusted hardware:

After deciphering and installing a certain version of a firmware, the device can forget the key used to decipher it, and use a new key (e.g. embedded in the firmware just downloaded, or derived from the earlier key with a ratchet mechanism). This limits exposure of past firmware, with the side effect that firmware downgrade is not possible. Things can be arranged so that some firmware upgrades can be skipped.
We can use security by obscurity, including white box crypto, which aims at making key extraction impossible (in other words making simulation of the actual decryption the best way to decipher). That theoretically fails, but practicaly succeeds to some degree.
Deciphering keys can be device-unique, but then the encrypted/signed firmware is also device-unique.
By making the encryption process dynamic (which makes sense if the update process is online), the key protecting the firmware's confidentiality can be an ephemeral session key, so that extracting the device's long-term key is not enough to decipher the firmware from a line intercept. However such extraction is theoretically enough to impersonate the device, connect to the update server, and get the firmware enciphered under a known session key, thus this is security by obscurity.

Update: the last two bullets do not apply given new comment to the question that all devices are the same and share the same cryptographic keys. Also, it’s not an online protocol.
Update per comment to this answer: indeed, signature works to prevent the creation of valid firmware that installs on genuine devices. That's a strong mechanism, resisting extraction (but not replacement) of device keys, provided no exploitable bug in any firmware allows to take full control of the device and circumvent that signature mechanism. Firmware signature is Independent of firmware encryption, which the rest of this answer is about.
Update: As noted in another comment, asymmetric encryption does not bring value in the situation, thus we want to use symmetric cryptography for the encryption part.


Changing the IV of the AES key wrap algorithm The first 64-bit block to be encrypted is defined by the spec to be

A6A6A6A6A6A6A6A6

Is their any merit in changing this to another value eg. B0B0B0B0B0B0B0B0?

You retain the strong integrity check although maybe at the cost of interoperability, but does changing the value make the wrapping more secure as potential attackers will not have the knowledge of the unencrypted value of the first block?

No, not really.

If you change the IV to a secret value, you prevent the attacker from checking that the key is correct by comparing to the IV, but they can still check by actually using the key. And if you make it a secret value, you need to pass it to the decryptor somehow, so it can be checked by the legitimate user.

If you choose another constant, Kerckhoffs' principle would suggest assuming the attacker knows it. E.g. if you used it in some server software and the attacker got access to your server they would see it.

There is no convincing security advantage to changing it at all. Its precise value does not affect the security of the key-wrap algorithm. The only reasons you would change it are those mentioned by NIST (pdf, 2.2.3.2), like to accommodate key-lengths that are not multiples of 64 bits (e.g. unpadded 3DES keys).


A method for creating distributed public key for ECDSA, what are the risk factors? There is quite a bit of literature on distributed ECC signing without a trusted dealer. Published works are mostly overly complicated, so I am proposing this simple technique which I am sure if it is valid is already published (but I couldn't find it):

Problem: "t" actors need to create an ECC private key and public key without a trusted dealer. Assuming some standard ECC parameters, and generator $G$.

Solution:
Each actor $a_i$ creates a private key $p_i$. Final private key is $\sum_{i}{p_i}$ that will never be published.

Actors publish the public key by publishing their part $p_i.G$. Final public key can be created by $\sum_{i}{p_i.G}$

Question Is this too simple to be true? What are the risk factors here that I am not anticipating? Note that in elliptic curve fields $(a+b).P=a.P+b.P$

Please note that for simplicity we assume at the time of signing we can trust the signer and she can collect the private key parts from the actors. Hence, the question is only in regards to creating a public key without a trusted dealer.

Suppose Bob watches Alice publish $A = [a]G$.  Bob then picks $b$ and publishes $B = [b]G - A$ as his share of the public key.  Now the combined public key is $A + B = A + [b]G - A = [b]G$, so Bob can unilaterally sign messages without Alice's consent.


Can I verify that digital object exists before a given date? It is possible to hash public info (e.g. new york times headline) into an object to verify that it existed after a given date. Is it possible to do the obverse, namely verify that an object must have existed before a given date?

You can do all sorts of verification with a time stamped hash and signed hash, but it can't be a NYT headline. Just as MD5 hashing is now considered insecure and ineffective, the block width of a NYT headline is insufficient. Actually, the input entropy of the textual headline is only a few tens of bits.  "Trump Convicted" does not hold a lot of entropy, which means that another headline at another time might hash to exactly the same value.

You also can't do what all good kidnapper's do and take a photo of the paper's front page alongside your object. This isn't just for the obvious reason that it's digital, but noise and the avalanche effect will ensure that you'll never manage to exactly replicate the image for future verification.

The thing to do is to hash sufficient cohesive public data. Something like the FTSE 250 list of share prices (at the time of hashing and signing) contains enough entropy to make collisions impossible. There's over 8000 bits of pure entropy available there by my calculation. That's sufficient for any possible cryptographic use.  The Million Dollar elliptic curve purports to use public lottery results but that must be  very cumbersome to collate. The music industry uses almost imperceptible fluctuations in the mains frequency to watermark tracks. A frequency vs. time curve could be hashed and keyed alongside the object. Object dating could be achieved for the timespan of available records.

So for example, to check if your object existed at any particular time you'd simply hash and key against all the records you have available. A hash match at a particular time would prove the existence of that object at that time.  You might be able to check with a 15 minute granularity for FTSE250 share prices. Again the most important thing is to hash against sufficient entropy to preclude manufactured collisions. Clearly you can't use this technique if you don't have reliable digital entropy for the time period under consideration.


WEP - shared symmetric keys I know that WEP uses stream cipher encryption. The key stream = RC4(IV, K).

My question is:
The shared symmetric key is the same for all users? Or each user has it's own symmetric key.
Also, how can a user get this key?

The shared symmetric key is the same for all users?

The shared key is exactly the same for each user, assuming they are connected to the same WEP access point. Because the nonce is concatenated with the key and fed directly into RC4, each wireless frame is technically using a different key (at least until the small 24-bit nonce repeats).

This is unlike 802.11i (WPA2), where a symmetric key called the PTK is derived in the 4WHS (4-way handshake) that is specific to that user and their current session, although this does not prevent a user who knows the PSK (via the passphrase) and has captured the 4WHS from deriving the PTK. Each user does, however, share a secret key called the PSK, though it is not directly used for encryption.

  Also, how can a user get this key?

The user can obtain the key either by asking the AP owner for it, or by exploiting one of any numerous weaknesses in the WEP protocol to crack the key and use it for authentication or to decrypt/inject data.