Can you derive ed25519 keys from secp256k1? Alice has a secp256k1 key pair that she used some time ago when she communicated with Bob. Bob can no longer user secp256k1 but he only uses ed25519 instead.

Is there a secure algorithm that Bob can use to derive an ed25519 pubkey from original Alice's secp256k1 pub key and also Alice can derive the matching ed25519 private key from her original secp256k1 private key such that they can communicate securely via ed25519 encrypted messages?

Thanks!

No. They use different curves.

For each system the public and private keys of the same key pair are not independent. You choose a private key and that determines what your public key will be.

(Good thing it doesn't work in reverse. If you could derive someone's private key from their public key, then we wouldn't have an asymmetric algorithm.)

You can derive a private key from an old public key. (Wrong!) Or a private key from an old private key. But you cannot derive a public key directly from anything other than its corresponding private key.

Alternatively Alice can sign, using her old private key, a messages that informs others of her new public keys. When Bob wants to communicate with her, he can check the authenticity of that message using Alice's old public key. (Assuming the old private key has not been compromised.)

(Note that you should be using separate keys for signing and encrypting.)

As for Alice's private key, I recommend generating new (random) private keys. If her old private key were compromised then it would mean all new deterministically derived private keys would automatically be compromised as well.


JOSE: JWE CEK Initialization Vector Position or Reuse So I am attempting to generate a JWE using an X25519 to encrypt the for the Content Encryption Key (CEK) and AES-256-GCM for the content.

My issue however is that NaCl needs an IV (nonce in NaCl) for both the asymmetric encryption of the key and the symmetric encryption of the content.

Looking at other examples such as the ietf-jose cookbook, (X25519, A128GCM), they only have the one "top level" IV.

Is it ok to use the same IV for both the x25519 and the A256GCM?

If not, where does the IV for the x25519 get placed in the JWE?

Or is there something else I am missing entirely?

{
  header: {
    enc: "A256GCM",
    alg: "ECDH-ES",
    epk: {
      crv: "X25519",
      kty: "OKP",
      x: ephemPublicKey
      iv: "Perhaps we stuff the X25519 iv here?",
    },
    iv: "Perhaps we stuff the X25519 iv here?",
    encrypted_key,
  },
  ciphertext,
  tag,
  iv: "iv for the A256GCM only or both?",
}

So the answer thanks to @kelalaka's comments is that X25519 doesn't need an iv. I was not using just X25519, but instead x25519-xsalsa20-poly1305 via TweetNaCl.js.
There isn't really a need to use x25519-xsalsa20-poly1305 to wrap the AES-256-GCM key, as the "xsalsa20 is a stream cipher and poly1305 is for mutual authentication".
Regarding JWE, there isn't a way to use x25519-xsalsa20-poly1305 with a JWE because JWE requires Authenticated Encryption Additional Data (AEAD) and salsa only has Authenticated Encryption (AE).
So my options with a JWE are to switch to just using x25519 + AES-256-GCM OR use just x25519-xsalsa20-poly1305 without using a JWE (or at least not a standards compliant one).


Role of session identifier in Otway-Rees protocol According to Wikipedia, Otway-Ress protocol is as follow:

  The protocol can be specified as follows in security protocol notation, where Alice is authenticating herself to Bob using a server $S$ ($M$ is a session-identifier, $N_A$ and $N_B$ are nonces):

\begin{align}
 A & \rightarrow B : M,A,B, \{N_A,M,A,B\}_{K_{AS}}\\
 B & \rightarrow S : M,A,B, \{N_A,M,A,B\}_{K_{AS}},\{N_B,M,A,B\}_{K_{BS}}\\
 S & \rightarrow B : M, \{N_A,K_{AB}\}_{K_{AS}},\{N_B,K_{AB}\}_{K_{BS}}\\
 B & \rightarrow A : M, \{N_A,K_{AB}\}_{K_{AS}}
\end{align}

What is the role of $M$, the session identifier, in the security of protocol?

What will happen if we remove all $M$ in the protocol? (I think there will be no flow, I don't understand the role of $M$)

The $M$ in  Otway-Ress protocol (It is $C$ as the Challenge in the article);

  In mutual authentication, both parties are suspicious of each other and of the freshness of the authentication messages; therefore each must generate independent challenges in order to assure themselves of the
  timeliness of the interaction.
  Its important property is that it has not previously been used to authenticate the two parties concerned.
  This property can be guaranteed either by storing all previously used challenges, by using numbers from a monotonically increasing sequence (e.g. time) or probabilistically by generating a sufficiently large number randomly.

$M$ is used to prevent replay attacks.


Is there a flaw in this ECC blind signature scheme? Recently I've found the following work on the internet: An ECC-Based Blind Signature Scheme

The paper claims to be an ECDSA blind signature however it seems that their scheme has a flaw in it.

The process they describe is pretty standard:

Requester blinds a message using his key and sends blinded message to signer
The signer signs the message resulting with pair $(r,s)$ which is sent to requester
BUT then the requester unblinds ONLY $s$ component and $r$ component is published unchanged

It seems logical that after publishing $r$ the way it came from signer would allow

the signer to track transactions by keeping a database of all issued $(r,s)$ tokens?

Or am I missing something?

This paper—if I have guessed correctly through the broken link—is bogus.  It fails to distinguish points on the curve from elements of the coordinate field and doesn't prove anything and even if you fix that by pretending any of it makes sense the whole thing is trivially breakable.  Throw it away and forget the whole ordeal—except don't forget that the ‘Journal of Networks’ is a bullshit-publishing paper mill.


Binary representation of the inverse of a big number In one of the first FHE schemes by Gentry, the KeyGen algorithm is defined as follow:

For a security parameter $\lambda$, set $N = \lambda ^ 2, P = \lambda ^ 2, Q = \lambda ^ 5$.

KeyGen$(\lambda)$: Generate a random $P$-bit odd integer, $p$. A set $\vec{y} = \{ y_1, y_2, \ldots, y_\beta\}$ is generated with $y_i$ bits. There must exist a sparse subset $S \subset \vec{y}$ of $\alpha$ elements such that $\sum\limits_{y_j \in S} (y_j) = \frac{1}{p} \mod 2$.

Set $sk$ to be a binary encoding of the subset $S$, where $s = (0,1)^\beta$.
Set $pk \leftarrow (p, \vec{y})$.

My problem here is with the subset S. Especially, for a large enough security parameter, the random integer $p$ is so large that I don't see how to print its inverse on my terminal. Are there some specific libraries in Python or C to handle this kind of inverse? I have tried to shift it by the size of p in base 10 but the problem remains as I can't convert p to float/double before dividing.

This may not be the most accurate forum for this question, and I apologize in advance if it is not.

The first $k$ digits on the right of the decimal point of the representation of $1/p$ in base $b$ also are the representation in base $b$ of $\left\lfloor b^k/p\right\rfloor$ left-padded to $k$ digits with zeroes.

If we want to perform computations to $k$ places after the decimal point for quantity $x\in\Bbb R$, we can use the integer quantity $\left\lfloor b^k\,x\right\rfloor$, or better $\left\lfloor b^k\,x+\frac12\right\rfloor$.

Any language (e.g. python) or library (e.g. GMP) capable of handling arbitrary precision integers let you make the necessary computations.

E.g. in python 3,

p = 3**161
print("{0:b}".format(2**700//p))

yields a 445-bit bitstring which, padded with 255 0 on the left, and then 0. on the left, is $1/p$ in binary to 700 binary places.


Is there a standard notation for a message concatenated with its signature? I'm wondering what's the standard (or canonical) notation for "a message along with its signature", i.e.

$$
\mathit{Message}~\Vert~\sigma_k(\mathit{Message})
\text.
$$

Here the duplicated $\mathit{Message}$ is tedious. Is there a way to put it more elegantly?

In formal papers, the standard way would be to either cleverly shorten it or to omit arguments.

For example you could write something like $M:=...$ (but please replace the dots with the actual message composition) at the end of your algorithm:
$$\operatorname{Output} (M||\sigma_K(M))$$

The alternative to this (a shortened version of your approach) would be to say that $\sigma$ is the signature in the text or define $\sigma$ somewhere and then use it as a simple variable. (outputting $(M||\sigma)$).

If you want to write a formal specification there are also ways to express a signed construct such as TLS' digitally-signed.


Do you use a salt when encrypting a password or just when hashing a password? A password is used to connect to a database.
This password is kept in a file.
This password (therefore) needs to be encrypted.
A program to access the aforementioned database needs (of course) the password.
Currently the program decrypts the password, uses the password to connect to the aforementioned database.
Is it recommended to use a salt value when encrypting this password?  Or is salting only related to hashing?  Or is salting something that is used with both encryption and hashing.  My understanding is that using a salt in 'one-way' and related to hashing.

Salt ( a.k.a $CaCl_2$) is added before hashing to prevent rainbow attacks. So each password will be appended to a unique salt before hashing and if the server is hacked and the hashes are leaked, a hacker will have hard time un-hashing with rainbow tables.
Salting has no use in encryption/decryption because it serves no purpose.


is accessing elements of an array in secret order vulnerable to timing attack? Suppose there is an array containing bytes 0...255. Suppose this array is shuffled using a key for random data.

Since this is indexing the elements of a table using secret data, is it vulnerable to timing attack?

If so, Suppose the array is shuffled again. Since the state at the beginning of the second shuffle is a secret, random permutation of bytes 0...255, is this second shuffle vulnerable to timing attack as well?

Basically, is the core of the problem accessing an index of an array based on secret data? Is knowing the contents of the array/table in question a prerequisite for this type of attack? Or is there something else to this altogether?

Background

More specifically, I am curious about the vulnerability of following construction to timing attack:

shuffle(Z256, key) # this randomizes key too
output = Z256[Z256[index]] for index 0...255
repeat

The problems that I see are the indexing based on secret data, both during the shuffle and output stage. However, since the set is shuffled every time, the key randomized, and the set iterated through completely, I think it should be resistant? My reasoning is that since the set is iterated through completely, the sum of the time spent accessing it should be more or less the same regardless of the order the accesses happen in. But I'm not sure exactly what causes the vulnerability to begin with.

Being vulnerable to specific timing attack isn't property of construction, but of it's implementation. It isn't hard to imagine a microprocesor that always takes X time to access a byte of memory. Such implementation likely won't be vulnerable to timing attack (but probably will to variety of other, like power analysis). But also some high-level languages can reorganize your data in way which will make analysis far easier, even when you shuffle.

So from now on let's assume modern PC class CPU and a compiler that compiles to native code (assembly). In such case, compilers will very likely make data appear in memory how we see it in table (for optimization purposes).

Modern CPUs cache access to ram on more than one level. Usually cache line has 64bytes. Since all of your data likely won't fit into single cache line, it will likely take different amount of time to access depending where that data is. So it will leak some data about index. It doesn't change anything if you do a double-dereference - it will still leak information about index.

But it doesn't automatically mean that it has to be vulnerable. Some RSA libraries (like OpenSSL) won't have this trouble, because they interleave their data, so that each piece of secret lies on next cache line. This way CPU will always access same cache lines, without timing dependency on index. This of course will also result in performance decrease and isn't likely to be done by compiler.

So having that out of the way, assuming normal memory organization (for speed, not for resistance), your scheme probably is still vulnerable, but shuffling will likely prevent most attacks. Your key will leak because of shuffling, and with enough patience it will be possible to retrieve key and then learn index. Such attack is unlikely to happen, but the cost of shuffling data is very big. So best idea is to follow established protocol for such problems (RSA is well known for having this problem so I suggest looking in that direction).


PK systems using groups in practice The four  Public-key cryptosystems: RSA, ElGamel, DH, and Rabin (all with others) all require some group operations in an  integer field or multiplication group of some residue classes. When it comes to encrypting blocks of bits in binary how are these public key cryptosystems performed ? Are byte blocks just converted to base 10 and the encryption is perform on each byte? However results of RSA are much longer than a byte each.

They are used to encrypt symmetric keys.  No.


Any good links to learn the maths behind AES? I'm creating an academic poster for my EPQ on the mathematics of cryptography.  I would like to do a section on AES, however, I am struggling to find good resources to understand the maths.  I have watched the computerphile video on AES but it doesn't explain that much of the maths.  Is there any good resources out there that is able to explain the maths behind it in a not too complicated way so I am able to simplify the maths down so a sixth-former can understand it.

I think Lenstra's short document Rijndael for Algebraists is fantastic to get started on the maths behind AES:

https://math.berkeley.edu/~hwl/papers/rijndael0.pdf

You can find some information on finite fields on Wikipedia have a look at the example of $GF(4)$.

For a detailed overview of the cipher see the book  The Design of Rijndael:The AES Standard by its designers.

There is also The Stick Figure Guide to AES, at a more informal and descriptive level.


What are the implications of limiting the private key space with elliptic curve Schnorr signatures? Given a curve, I am trying to limit the private key space to ultimately cut down the Schnorr signature size as follows:

Assume an elliptic curve $E$ over a field $F$ with generator point $G$ and the main subgroup's order being $\ell$. Field $F$ can be assumed to be secure. (For the sake of an example, it may be assumed that the parameters are those for Curve25519, but I am looking for a generic, canonical answer.)

I am looking at Schnorr signatures in particular, but the answer to my question will likely extend to EdDSA and its variants as well. Summarizing the signing process for private key $k$ (scalar) and message $M$ (sequence of bytes)

Randomly select a scalar value $r$ (nonce) as ephemeral random scalar in the range $0 < r < \ell$.
Generate the ephemeral curve point $R = [r]G$.
Generate the hash value $c = H(\underline{R} || M)$, where $H$ is a cryptographic hash function, $\underline{R}$ denotes the serialized form of the point $R$ as a sequence of bytes and $||$ denotes concatenation. Interpret the sequence of bytes $c$ as a scalar integer.
Compute the scalar value $S = r + ck \mod \ell$.
The signature is now the tuple $(c, S)$.

Note how $S$ is the result of an addition and a multiplication taken modulo $\ell$. By limiting the private key space (i.e. the artificially reducing the possible range of $k$), it is therefore also possible to limit the size of the resulting $S$.

Assume now that the upper limit for $k$ is reduced from $\ell$ to $2^n$; within this reduced space, $k$ is still picked uniformly at random. The nonce value $r$ is picked in the normal space $0 < r < \ell$ in any case.

Given this background, my questions are:

How does reducing the upper limit for $k$ improve an attacker's chances to learn $k$ other than the obvious reduction in brute force search space for any given $n \le \log_2 \ell$?
How does reducing the upper limit for $k$ from $\ell$ to $2^n$ interact with short Schnorr signatures? I take “short Schnorr signatures” to mean trimming the hash value $c$ is trimmed to $b$, where $b$ is the strength of an elliptic curve in bits (e.g. for Curve25519, that would mean using a 128-bit hash value for $c$; see also Schnorr's original paper on p. 242 in particular as well as the subsequent analysis by Gregory Neven, Nigel P. Smart, Bogdan Warinschi. Hash Function Requirements for Schnorr Signatures, Journal of Mathematical Cryptology 3(1), 2009, pp. 69–87, which ends with an uncomfortably loose security reduction, but should be assumed safe for the purpose of this question).
Assuming a curve over a prime field $F_q$, where $q$ is a 256-bit number, how much could the space for $k$ be reduced and still meet a target security level of 80-bit symmetric equivalent strength?

This is interesting for efficiency reasons: If the space for $k$ can be lowered significantly, the final computation $\mod \ell$ can be either skipped entirely or at least simplified, yielding speed increases at signing time.

I am aware that BLS signatures exist and yield short signatures (e.g. BLS12-381 gives 48-byte signatures), but they are significantly more complex to implement and compute. Similarly, I am aware that some multivariate cryptography schemes yield very short signatures (Gui comes to mind, though patented). If I just wanted very short signatures, I would look into schemes that are not Schnorr signatures.

A similar question has been posted before; “64 bit Elliptic Curve Key”. However, the answers there generally assumed either creation of a new curve over a 64-bit field or truncating the public key, neither of which apply here, as I am reducing the range for the private key, leaving the public key and the field as-is.

How does reducing the upper limit for $k$ (to $2^n$) improve an attacker's chances to learn $k$

Security becomes at most $n/2$-bit. Baby step - giant step finds $k$ given the public key $\underline{[k]G}$ with computational cost $\mathcal O(2^{n/2})$. Pollard's Rho can be adapted to the same asymptotic cost, with feasibly little memory and efficient parallelisation. In order to keep the security level $\mathcal O(\sqrt\ell)$ of normal EC-Schnorr, we can't have $n$ sizably below $\log_2\ell$.

  How does reducing the upper limit for $k$ from $\ell$ to $2^n$ interact with short Schnorr signatures?

For the reason above, it reduces security.

Also, I fail to see how it reduces signature size in the signature scheme of the question if we keep $r$ random in $[0,\ell)$ with $\ell$ unchanged, because then $S$ also is random in $[0,\ell)$, thus we need to transmit $\left\lceil\log_2\ell\right\rceil$ bit for $S$.

For $n$-bit symmetric security (80-bit in the question), and as small a Schnorr signature as possible, we can

Use an Elliptic Curve group of reduced size $\ell\approx 2^{2n}$. That's precisely why we have secp192r1 and secp192k1 in sec2-v2, which are expected to give 96-bit security. However these use a base field $\Bbb F_q$ of roughly the same size as $\ell$, and I do not know if, much less how, we could construct a secure Elliptic Curve group based on $\Bbb F_q$ of much larger size (e.g. $\log_2 q\approx256$ as asked).
Reduce the hash width from the usual/modern $2n$ to the original $n$, for a $3n$-bit signature when combined with 1. The original Schnorr signature scheme works that way, with heuristic arguments of security that withstood at least the test of time.
As an alternative to 2., and when signing messages of bit size $m\ge n$, use a variant of Schnorr's scheme giving signature scheme with message recovery (see list there), which can embed $n$ bits of message into a $4n$-bit signature, thus achieve an effective $3n$-bit overhead just like the original Schnorr signature scheme in applications where the message is sent along the signature and is at least $n$-bit. The main advantage is a slightly more positive argument of security. The drawbacks are that the signature is no longer separate from the message, that some of the best schemes are patent-encumbered, and that (therefore) this is seldom used.

Note: if only signature size (but not public key size nor performance) is an issue, there is no reason to use an Elliptic Curve group. The original Schnorr signature scheme uses Schnoor groups over a subgroup of prime order $\ell$ constructed as a subgroup of $\Bbb Z_p^*$ for prime $p=2\,r\,\ell+1$, and the signature size is not impacted by the large $p$ (which needs to be in the thousands bits for modern security).

If one is (like me) prudently cautious about the heuristic security arguments (and complex modern proofs in some limited models) of the original Schnoor signature scheme, one can venture into improvements:

De-randomize the choice of $r$ by making it a deterministic PRF, keyed by the $2n$-bit private key, of a (wide, secure) primary hash of the message: $r=\operatorname{PRF}_k(H_\text{wide}(M))$. It removes the requirement for an unpredictable RNG (which is notoriously hard to get), and could only harm thru a side channel. That's used by EdDSA.
Construct the $n$-bit (thus uncomfortably narrow) hash $c$ part of the signature using a purposely-slow hash (like Argon2) in order to increase it's second-preimage resistance, which is one of (and arguably, the main) limiting factor of security in Schnorr signature. It can not harm. Even with parametrization yielding negligible impact on overall performance, it can increase resistance to that particular attack by at least 8 bits, which is nice to have.
Make the public key part of the input of said $n$-bit hash $c$. This is a belt-and-suspenders approach against multi-target attacks. It has negligible cost, and can not harm. Combined with the above, that makes the $c$ part of the signature $c=H_{n\text{-bit, slow}}(\underline{R}\mathbin\|H_\text{wide}(M)\mathbin\|K_\text{pub})$
[my personal fad] Rather than directly using the $n$-bit $c$ part of the signature $(c,S)$ in the computation of $S=r+c\,k\bmod\ell$, we can beef it back to the full $2n$-bit of $\ell$ (as used in modern variants of Schnorr signature having the strongest security arguments) by using a public transformation, e.g. a hash. With maximum belts-and-suspenders, that's $S=r+c'\,k\bmod\ell$ with $c'=H_{2n\text{-bit, slow}}(c\mathbin\|H_\text{wide}(M)\mathbin\|K_\text{pub})$. Arguably, it can't harm, and adds hurdles to various conceivable attacks.

The above leaves the signature size at $3n$-bit, needs only trivial adaptations to signature verification, and marginally slows down signature generation or verification. For large messages, $H_\text{wide}$ is the limiting speed factor, and we can use e.g. SHA-512 for that. Parametrization of the slow hash can be set for cost lower than one scalar multiplication, with perhaps 3/4 of that in the slow hash that builds $c$, and the rest for $c'$.


variant of Diffie–Hellman key exchange protocol Motivation

Consider the following variant of Diffie-Hellman key exchange protocol for two parties:

Assume Alice and Bob share $\mathbb{G}$ of order $q$ generated by $g$
Alice samples $a$ uniformly from $\mathbb{Z}^q$, and sends $h := g^a$ to Bob
Bob samples $b$ uniformly from $\mathbb{Z}^q$, and sends $h^b = g^{ab}$ to Alice
The shared key is $g^b$

Alice can calculate $g^b$ by raising $h^b$ that he received from Bob by $a^{-1}$ so he will get: $(h^b)^{a^{-1}} = (g^{ab})^{a^{-1}} = g^b$

My question is how to prove that the above protocol is secure (assuming DDH assumption holds?

I tried to prove it by reduction:

upon receiving $(\mathbb{G},q,g,g_1=g^x,g_2=g^y,g_3)$
run the above protocol s.t. Alex sends $g_1$ to Bob, then Bob returns $g_3$, and both will agree on key $g_2$. i.e. we simulate the case where: $a=x$ and $b=y$.

In case $g_3=g^{xy}$, then $(Transcript, Key) = (g^x,g^{xy},g^y)$

In case $g_3=g^z$ for $z$ sampled uniformly from $\mathbb{Z}^q$, then: $(Transcript, Key) = (g^x,g^z,g^y)$

The problem with my solution is that the difference between the two cases is in the distribution of $Transcript$ while $Key$ is the same, and this is different from what required in the definition.

In another try, I simulated the protocol s.t. Alice sends $g_1$, Bob sends $g_2$ and they agree on $g_3$, i.e. simulate the case: $a=x$ and $b=x^{-1}y$, but this will not work because the key the agree on will be $g^y\neq g^b=g^{x^{-1}y}$

Edit: General case

We have $A_1,...,A_T$ parties (where $T$ is polynomial) and $B$. the protocol is:

each $A_i$ sample some $a_i$ uniformly and send $h_i := g^{a_i}$ to $B$
upon receiving $h_1,...,h_T$, $B$ samples $b$ uniformly and sends $h_i^b$ to $A_i$
The key is $g^b$.

Any idea of how to prove the general protocol's security?

To show that the protocol is secure under DDH, we need a reduction $R$  that takes a triple as input and outputs a transcript and key such that

if the triple is a DDH triple, then the transcript and key are distributed identically to a real execution of the protocol
if the triple is random, then the transcript and key are distributed as if you ran a real protocol execution to get the transcript, but the key is random (and independent of the transcript)

The reduction $R$ takes a triple $(A,B,C)$ and sets Transcript=$(A,C)$ and Key=$B$.

If the triple is a DDH triple then there are values $x,y$ such that $(A,B,C)=(g^x,g^y,g^{xy})$. So $(A,C)$ is distributed uniformly in $G \times G$, which is exactly how a transcript of a protocol execution is distributed too. The key in a real execution is the unique value $k$ satisfying $k \otimes \alpha = \beta$ where $\alpha$ is Alice's message, $\beta$ is Bob's and $g^x \otimes g^y := g^{xy}$ (this is well-defined if you think about it). The reduction's key satisfies this property too since $C = A \otimes B$ is the definition of a DDH triple. So the reduction's transcript and key are identically distributed to real ones in this case.

If the triple is a random triple, then $(A, B, C)$ is uniform in $G^3$, i.e. each element is uniform in $G$ and independent of the other two. If you create a transcript together with a random key, then the transcript and key are distributed uniformly in $G^3$ too, so the reduction produces the correct distribution in this case too. Q.E.D.

Informally, think of the proof as follows: a DDH triple has two degrees of freedom, a random tuple has 3. A real transcript/key also has 2 degrees, a fake one 3. In both cases, the restriction that loses the third degree is that one element is a DH product $(\otimes)$ of the other two. So all your reduction has to do is match things up.

EDIT: General case

A transcript of a protocol looks like this (order may vary):

A1 to B: g^{a_1}
...
An to B: g^{a_n}
B to A1: g^{a_1.b}
...
B to An: g^{a_n.b}
shared key: g^b

A fake transcript (that is indistinguishable from a real one if it's secure) is the same except that the key at the end is $g^r$ for independent $r$. Note that even in a fake transcript, the same exponent $b$ is used for all messages from $B$.

Reduction $R$ takes a tuple $(A, B, C)$ and makes $n$ tuples by picking $u_i$ for $i$ from 1 to $n$ and sets $(A_i, B_i, C_i) = (A^{u_i}, B, C^{u_i})$.
It then outputs the transcript $A_1, \ldots, A_n, C_1, \ldots, C_n, B$.
If the orignal tuple was DDH, so are all these ones - so it is identical to a real transcript (in the real transcript, each $a_i$ introduces a degree of freedom; in the reduction, the $u_i$ do). And $B$ matches up too.

If the original tuple was random, $B$ is independent of everything else but the $A_i/C_i$ relations still hold so it's all distributed correctly.


WebcryptoAPI - secure or not This is about the new W3 WebcryptoAPI draft standard.

Here is a post by one of it's authors

https://plus.google.com/u/0/105761279104103278252/posts/CSwVZ1RUijo

It says its in part trying to change the "Javascript Cryptography Considered Hamrful" problem. However if you look at the "Javascript Cryptography Considered Hamrful" article -  http://www.matasano.com/articles/javascript-cryptography/ - it seems as if most of the problems still remain unsolved. The only problem solved is that you won't have hand coded cryptographic functions in javascript - these will be provided by the browser. However, the remaining problems still remain.

Your thoughts?

(I originally asked this at stackoverflow but did not receive any useful response.)

Personally I believe that it could be done properly and address all (or at least some) of the concerns.

Remember what the WebCryptoAPI is:

  This specification describes a JavaScript API for performing basic cryptographic operations in web applications, such as hashing, signature generation and verification, and encryption and decryption. Additionally, it describes an API for applications to generate and/or manage the keying material necessary to perform these operations. Key storage is provided for both temporary and permanent keys. Access to keying material is contingent on the same origin policy. Uses for this API range from user or service authentication, document or code signing, and the confidentiality and integrity of communications.

A lot of the concerns are related to how the code is distributed, hijacking the javascript/security of javascript engine, etc.

Well, for this particular standard, the code is distributed with the browser, not over the http socket. So at least the crypto algorithms should be safe. Furthermore, that would make it difficult for someone to say override the crypto code with attacker supplied code as browser checks can be added.

Hijacking of the content delivered by the HTTP server (say through XSS) to disable crypto or steal crypto keys is a concern. But, it is just a symptom of a larger problem.

It definitely attempts to solve some of the other problems such as key generation, key storage, etc.

A lot of this will depend on actual implementations, however.


Is the same message with repeated AES-GCM leaking plain text over time? The same message results in different cipher text every time AES-GCM is applied. If an attacker collects repeated messages over time, will he be able to extract the plain text if enough cipher text is collected?

If GCM is correctly applied then no, this is not the case.

Ciphertext output is supposed to be indistinguishable from random, so any secure mode of operation behaves in this way. If this was not the case then you could distinguish messages with the same value. That would not be considered secure.

GCM is not secure when (larger) parts of the message are identical. That would point to repetition of the IV / nonce. And as GCM uses CTR underneath it could almost instantly compromise the plaintext.

You would expect about half of the bits to change when comparing larger messages of identical size, as the Hamming distance is about half the message size for randomized messages.


How can we say there is absolute collision in Baby-Step Giant-Step attack for RSA? According to this paper, there is a Baby-Step Giant-Step attack for RSA encryption.
Consider the following Baby Step, Giant Step attack on RSA, with
public modulus $n$. Eve knows a plaintext $m$ and $a$ ciphertext $c$. She chooses $N^2 ≥ n$ and
makes two lists:
The first list is $c^j$
(mod n) for 0 ≤ j < N.
The second list is $m.c^{−Nk}$ (mod n) for $ 0 ≤ k < N $.
The mentioned paper solves this problem by the collision of these two lists.
But how can we say there's a absolute collision in these two lists?

But how can we say there's a absolute collision in these two lists?

Well, we know that $c^d \equiv m$ for some value $d < n$, because of this, we have $d = Nk + j$ for some pair of integers $0 \le j < N$ and $0 \le k < N$.  We see that $c^j$ will appear somewhere in the first list, and $m \cdot c^{-Nk}$ will appear somewhere in the second list.
Since $c^{Nk + j} = m$, rearranging terms, we have $c^j = m \cdot c^{-Nk}$, and so those two terms will be the same.
That said, this is not a practical attack against RSA (and Coron et al never claimed it was).  The attack takes $O(\sqrt n)$ time, making it no more efficient than brute force factoring (and there are plenty of more efficient ways to break RSA than that).


Zero-Knowledge Challenge-Responce Protocol Good day to everyone.

I am trying to implement an e voting system (just for reference -it is not important though-it is described at the Internet Voting Protocol Based on Improved Implicit Security by Abhishek Parakh & Subhash Kak Version of record first published: 29 Jun 2010. ).

The protocol I am trying to implement mentions that "The Polling Station verifies the validity of Voter-id by conducting a zero-knowledge challenge-response protocol with the Registry Authority to validate the signature of voter-id."

I have searched at Google, and at Wikipedia about this protocol, but I didn't get much information. It is very important for me, to learn about what is this protocol, and what Polling station has to sent to Registry Authority, and what Registry Authority has to send back. Basically, I need to know how I can achieve to validate the voter-id.

Thank you very much for your time.

Ps. I just created account at this forum. If you need to provide you with any further information please ask it, and I will answer.

Reading the original paper, I figure out the question.
This voting scheme employed the well-known undeniable signature scheme, proposed by Chaum and Van Antwerpen in 1989 (or Chaum 1990 or Chaum and Van Antwerpen 1991).

KeyGen: The RA is a signer and has a public key $X = g^x$ and a secret key $x$
Sign: For a message $m \in \mathbb{G} = \mathbb{Z}_p$, the signature is $\sigma = m^x \in \mathbb{G}$. (In your case, $m = r_{id}$.)
Cofirmation: The verifier (the polling station) and the signer (the RA) interacts to verify a token $(r_{id},\sigma)$ from a voter is correct or not.

In confirmation, the RA proves that $\log_g(X) = \log_{r_{id}}(\sigma)$. You can find the standard $\Sigma$ protocol for this confirmation, say, the $\Sigma$ protocol for the DDH language.

You can find the $\Sigma$ protocol for the DDH language in the lecture notes available at the web.

Section 5 of Berry Schoenmakers: Lecture Notes - Cryptographic Protocols
Lindell: Sigma protocols and Zero Knowledge (Session 5 of Winter School on Secure Computation and Efficiency)


How to encrypt a short string and keep the length secret I need to encrypt relatively short strings (generally less than 100 characters). If possible, I want to avoid leaking the length of these strings. How can I do that?

The thing that came to my mind is to pad the text to 1 KiB with random data, separating the content from the padding with a 0x00 byte. Is this a good idea?

Instead of saving the padding length as rossum explained, you can also put a length encoding in front of your plain text. A standardized way to do this would be DER encoding (which uses a dynamic number of length bytes), but in your case you could also use a 2 byte short. Then just add 00h bytes padding up to X times the block size, and encrypt using a cipher without padding.

The advantage is that during decryption you can simply discard the bytes, and you don't need no unpadding mechanism, just discard any bytes behind the plain text.

This method is used e.g. in the PKCS#11 standard (for hardware tokens).


How to calculate a private key from public key on elliptic curve? Provided, that you have to multiply a well known G by the private key to obtain the public key, why not keep adding G to itself until you reach the public key. The private key should be the number of times you've added the G to itself. Is it correct? And if so - why isn't it feasible?

Yes your method is mathematically correct but it isn't feasible because of the size of the secret key $k$ that is used in practice.

Typically you are using curves over $\mathbb{F}_q$ where $\log_2 q \approx 256$. This means that there are $2^{256}$ possibilities for $k$ and, on average, it will take a very, very, very long time to find the correct one.

As a comparison, the Universe itself is estimated to be "only" $2^{58.5}$ seconds old. This means that even if you could try $1,000,000 \approx 2^{20}$ values of $k$ every second, it would take you $2^{255-20} = 2^{235}$ seconds to try half of the possible values. This amount of time is $2^{235-58.5} = 2^{176.5}$ times greater than the age of the Universe.


Why do cryptographers need loads of true random numbers? I've just read an answer to fastest-random-number-generator.  The answer is a couple of years old, but mentions a true random number generator capable of running at 300 gigabits per second.  It is re-linked here.  They might go even faster now. .

One time pads are out of favour.  There's no point storing these numbers for reruns as you might as well use a psuedo random number generator.  Most pundits on this forum suggest a maximum of 128 bits of true entropy for seeding.  So why would cryptographers need so many true random numbers? Or is it just a *issing contest between researchers?

Mostly, you do not actually need a lot of true randomness, as you observed. However there are at least some niche cases where you might want a fast TRNG.

Stateless implementations cannot use a typical CSPRNG. Something like a hardware token without writable storage, maybe. The intersection with applications that require a lot of speed is pretty small.
Long term key generation. People tend to want true random numbers when generating long term keys. That is not usually a frequent event, but perhaps something like a federated key store would need to do it often enough.
Latency. Even if you do not need gigabytes of entropy every second, getting e.g. 256 bits quickly can be important. Although again it is probably rare to need it and not be able to use a cache.

There are probably also use cases where the random numbers are used for non-cryptographic algorithms, but need to be both strong and non-deterministic. Maybe in gambling.


Multi Authority Attribute Based Encryption Library Anyone aware of a library that has MA-ABE implemented in any language preferably python?

P/S - I hope this is the right place to ask this. Apologies if not, then a redirect will be appreciated

Charm crypto, a Python framework, contains three multi-authority schemes. Two of them were contributed by me: 1 & 2 and another one was already included.

Yannis Rouselakis also has a MA-ABE implementation in Charm on his site.


Diffie Hellman: Why is $(\mathbb{Z}_{8191}^*, \times)$ an insecure group? I noticed that all the binary bits of $8191$ are $1$'s. Could this have something to do with it?

Besides 8191 being too small for real world use, the factorization of 8190 ($p-1$) has all small values. It's factorization is $2\cdot 3^2\cdot 5 \cdot 7\cdot 13$. Having a group whose order is smooth makes it vulnerable to an attack using the Pohlig-Hellman.


Will an algorithm that constantly changes the order of 10 hash functions be protected from an ASIC? Let's imagine one hash function that is based on 10 hash functions. For every input, it changes the order of the 10 hash functions. So, for example:
Hello, World! -> md5 -> sha256 -> sha512 -> sha3_256 ... -> resulted hash -> sha256 (additionally)
Hello, World? -> shake_256 -> md5 -> sha256 -> sha3_256 ... -> resulted hash -> sha256 (additionally)
Will it be impossible to create an ASIC for such an algorithm? And if yes, what would be effective for brute force?

Will it be impossible to create ASIC for such algorithm?

No, actually it is quite easy.
The way you'd design a single brute-force core then is that you take a hashing engine for each hash function used, an input generator, a hash validator and a smart interconnect.
Then when you want to brute-force an invocation of ordering 1, the input generator outputs the guess along with routing / ordering information for the interconnect which then sends it to the appropriate engines in the appropriate order. As you are only targeting one ordering at a time, you could possibly even make this a state register of the interconnect. Then, once the first engine has processed the first piece of data, the interconnect receives it back, checks its ordering register and sends it to the next engine, while accepting the next guess for that ordering from the input generator which is promptly sent to the first engine.

Will it be impossible to create ASIC for such algorithm?

As you have seen exemplified above, there is no algorithm which is really hard to brute-force for an ASIC. The best one could hope for is that the optimal ASIC configuration would be (close) that of a modern CPU, but even then, chances are that the algorithm will not use specific parts of the CPU, e.g. FP cores, which a dedicated ASIC can drop.


Need an XL Algorithm example could anyone give me a small example with actual numbers and variables over a finite field of how the XL algorithm is used to solve overdetermined systems? And the steps involved. I understand the algorithm but a simple example would make my life a lot easier. Also are there any implementations of the XL algorithm available?

Thanks.

I recommend to read book "Algebraic Cryptanalysis Book by Gregory Bard". it has a simple example of XL algorithm chapter 12 page 213 (12.4 The XL Algorithm).

after that you can develop sage/magma code for capturing the concept very well.


Emulate multisignature wallet I have a blockchain wallet with a single signature wallet, is there a way of making this wallet "multi-signature"? F.e can we use some secret sharing scheme to distribute the single private key among custodians? What I need in the end is to make several users control access to a single wallet.

(Responding to Squeamish Ossifrage) Threshold signatures do not require any single member to reconstruct the whole secret. Ideally each party produces a partial signature and only when they are all combined is the signature valid.

Douglas R. Stinson, Reto Strobl - Provably Secure Distributed Schnorr Signatures and a (t, n) Threshold Scheme for Implicit Certificates

This enables a pre-determined group to share a single schnorr identity without changing the verification side of the protocol. Any subset of $k$ members may collaborate to sign a common message. The secret sharing is verified and the dealer cannot cheat. The co-signers cannot be tricked by their peers.

MuSig: n-of-n threshold schnorr via aggregation

MuSig also doesn't change the verification side. A group is derived from the list of all public keys required to sign the common message. With only two-rounds of communication, the group produces the signature.

Crypto conditions: off-chain contracts resolving to minimal proofs of execution

Crypto-conditions are a form of multi-sig contract that doesn't attempt to aggregate any identities. Instead it uses hash commitments to commit to some boolean circuit. I.e. A contract may require "either Alice, or both Bob and Carol", or any arbitrary logic. The contract is a single hash. The proof of execution reveals only the relevant branches. The contract is valid if all leaves are valid and all intermediate steps have appropriate thresholds.

ANY-k is implemented as k-of-n. OR/ANY as 1-of-n. AND/ALL as n-of-n. A fullfillment may be either a hash-lock that is just a revealed symmetric secret key, or a signing public key whose corresponding secret signs the transaction that it approves.

Any irrelevant (or dead/unresolved) branches are truncated to a single hash commitment; enabling an arbitrarily large contract to resolve to a minimal proof.

Conclusion

I believe it would be worth implementing all of these. Notably $(t,n)$ enables a group to divide their signing right such that no single, or fewer-than-t subset may impersonate the group. N-of-N MuSig enables opportunistic groups to compress the crypto-condition contracts, which can describe any boolean circuits - not just subsets or all.

bonus: BLS is signature scheme that supports aggregation of many distinct-signatures. But this is not schnorr-friendly and does not work with any curves not explicitly designed to be pairing-friendly.


What's a good P to use in ElGamal key generation? I need to generate a 1024 bit ElGamal key on Android, and key generation takes forever (~10 minutes on a Galaxy Nexus), I suspect because it take so long to generate a safe prime.

Is it dangerous for me to use the same safe prime p for all devices using my app?

Where can I find a list of 1024 bit and 2048 bit safe prime numbers?

I'm using it for encryption, and I'm wary about hard-coding a P/G because of the this attack. I know it says only for signatures, but I'm still wary of introducing weakness because I am by no means an experienced cryptographer. The IETF has a list of good Ps to use, but they advocate using G=2, as seen here.

With most finite field crypto using a standard group is no problem. I think ElGamal encryption doesn't have any specific requirements for group or generator that plain Diffie-Hellman doesn't have.

So you could look into RFC 2409  Internet Key Exchange or RFC 5114  Additional Diffie-Hellman Groups for Use with IETF Standards for groups.

AFAIK ElGamal signatures have some additional requirements for the generator, so the above groups are probably a bad idea. But I wouldn't use ElGamal signatures in the first place, preferring DSA or Schnorr.


Get the parameters of an elliptic curve's equation I have a binary signed with ECDSA384 and I need to verify it using a particular cryptography library.
The first thing that needs to be done is to initialize the EC public key, which involves setting several parameters 'manually'. These parameters are the ones that make the following EC equation:
Elliptic Curve equation over $\operatorname{GF}(p): y^2=x^3+ax+b \pmod{p}.$
I need the parameters $a$, $b$, $p$ and $n$. (no idea what $n$ is)
The key I'm using is in PEM format. I'm aware that the EC parameters can be extracted by doing:
openssl ec -in ec384.pem -noout -text

and I get
read EC key
Private-Key: (384 bit)
priv:
    5d:b1:ef:88:fe:7b:f2:af:d8:cc:3a:04:89:09:34:
    15:c4:17:7b:41:72:ee:32:7b:54:9a:e2:aa:fa:1d:
    d1:47:1a:ef:fe:dc:d3:6b:51:fa:bd:c2:5e:66:c4:
    42:d0:16
pub:
    04:5e:ff:47:19:80:be:93:5f:8f:51:14:45:d5:40:
    41:79:ca:48:be:85:97:bd:e2:0f:2b:a0:b2:7d:6c:
    37:74:39:44:ff:50:67:74:30:a8:10:ac:89:a6:6a:
    80:5a:1a:c9:82:ff:2a:51:84:38:c8:f6:af:e0:46:
    e7:9f:d5:66:1b:20:75:7f:87:42:46:d9:6e:12:4f:
    74:38:4d:f4:9f:b1:13:27:9a:10:a8:0c:6b:4b:1f:
    f6:6c:bf:32:ee:a3:10
ASN1 OID: secp384r1
NIST CURVE: P-384

Still, I don't get the parameters I need from that output. It's not very clear to me if these parameters change from key to key or they are inherent to the curve being used, in my case, P-384.
How can I get the parameters I need?
EDIT - might help
Apart from the fantastic answers, I have found this that might help:
The python library ecpy contains this information, e.g:
pip3 install ecpy
python3
>>> import ecpy.curves as ec
>>> ec.Curve.get_curve_names()
['stark256', 'frp256v1', 'secp521r1', 'secp384r1', ...]
>>> p384 = ec.Curve.get_curve('secp384r1')
>>> hex(p384.a)
'0xffff...ffc'
>>> hex(p384.b)
'0xb3312f...3ec2aef'
>>> hex(p384.order)
'0xfffffff...cc52973'
>>> hex(p384.field)  # This is the modulus
'0xfffffff...00ffffffff'

04 indicates the uncompressed form of the public key.
The first half is the $x$-coordinate and the second half is the $y$-coordinate of the public key.
x= 5e:ff:47:19:80:be:93:5f:8f:51:14:45:d5:
   40:41:79:ca:48:be:85:97:bd:e2:0f:2b:a0:
   b2:7d:6c:37:74:39:44:ff:50:67:74:30:a8:
   10:ac:89:a6:6a:80:5a:1a:c9:

y =82:ff:2a:51:84:38:c8:f6:af:e0:46:e7:9f:
   d5:66:1b:20:75:7f:87:42:46:d9:6e:12:4f:
   74:38:4d:f4:9f:b1:13:27:9a:10:a8:0c:6b:
   4b:1f:f6:6c:bf:32:ee:a3:10

The parameters you are looking for are defined in the last part.
ASN1 OID: secp384r1
NIST CURVE: P-384

The parameters can be found in FIPS PUB 186-4 or SEC 2: Recommended Elliptic Curve Domain Parameters as sextuple
$$T = (p, a, b, G, n, h)$$
p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF
    FFFFFFFF FFFFFFFE FFFFFFFF 00000000 00000000 FFFFFFFF

$$ p = 2^{384} − 2^{128} − 2^{96} + 2^{32} − 1$$
The curve $E: y^2 = x^3 + ax + b$ over $F_p$ is defined $b$;
a = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF
    FFFFFFFF FFFFFFFE FFFFFFFF 00000000 00000000 FFFFFFFC

b = B3312FA7 E23EE7E4 988E056B E3F82D19 181D9C6E FE814112
    0314088F 5013875A C656398D 8A2ED19D 2A85C8ED D3EC2AEF

The basepoint $G$ in compressed form (03) indicates
G = 03 AA87CA22 BE8B0537 8EB1C71E F320AD74 6E1D3B62 8BA79B98
       59F741E0 82542A38 5502F25D BF55296C 3A545E38 72760AB7

The basepoint $G$ in uncompressed form (04) indicates
G = 04 AA87CA22 BE8B0537 8EB1C71E F320AD74 6E1D3B62 8BA79B98
       59F741E0 82542A38 5502F25D BF55296C 3A545E38 72760AB7
       3617DE4A 96262C6F 5D9E98BF 9292DC29 F8F41DBD 289A147C
       E9DA3113 B5F0B8C0 0A60B1CE 1D7E819D 7A431D7C 90EA0E5F

$n$ is the order of the basepoint $G$
n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF
    C7634D81 F4372DDF 581A0DB2 48B0A77A ECEC196A CCC52973

and the cofactor $h$ is:
h = 01

The cofactor is caluclated by $$h = \frac{|E(\mathbb{F_p})|}{n}$$

Printing via OpenSSL
Using OpenSSL Command-Line Elliptic Curve Operations it is possible to print the values, too
openssl ecparam -name secp384r1 -out secp384r1.pem
openssl ecparam -in secp384r1.pem -text -param_enc explicit -noout

The compression
The 0x02 or 0x03 indicates the distinction of $Y$ or $-Y$. Since in the elliptic curve $$Y^2 = X^3 + aX + b$$ if $(X,Y)$ is a point then $(X,-Y)$ is also a point on the curve. This is due to the square of $Y$ in the elliptic curve equation.
The distinction designed by the least significant bit of $Y$, 0x02 for 0, and 0x03 for 1.


Nonce reuse resistance I read this article and I think the approach outlined there is very interesting for one of our use case.

We use ChaCha20 Poly1305 (via Sodium crypto_aead_chacha20poly1305_encrypt_detached) to encrypt the data, which is typically 8 kb in size. We use this because this way the mac + nonce can fit in the available space we have in the page header, using XChaCha20 (and random nonce) is not possible because of the amount of space they would take.

The data is pages in database, and each page may be modified multiple times over the lifetime of the database.

I'm trying to figure out what the best way to handle nonce / key management in this case.

Currently we generate a random nonce per page and then increment the nonce every time the page is modified. To avoid the case where a random nonce / increment is reused, we also derive a new key for each page (via crypto_kdf_derive_from_key, where the subkeyid is actually the page number).

This seems fine, but it require us to do quite a bit of work every single time.

Note that we use

The article above seems to indicate that using the hash of the data that we encrypt as the nonce will help avoid the problem with nonce reuse, since if that happens, it will be identical data & nonce, so you can't XOR them together to find anything meaningful (but can find if they are repeating).

If this is a valid option, that would give us the option of having a single key for all the pages, and a nonce based on the hash of the data and avoid the need to carefully manage the nonces.

Assuming this is the case, can we use any hashing algorithm (we already do checksum with XXHash64, or do we need a cryptographic hash to use)?

The scheme you propose certainly leaks plaintext repetitions to an attacker since the same plaintext is always encrypted to the same ciphertext. You typically don't want this and it can be disastrous if the attacker knows some of the messages.

If you are absolutely sure that leaking repetitions is no problem in your case, you can use an authenticated encryption scheme with nonce-misuse resistance. Note that not all authenticated encryption schemes have this property. If you use a scheme with nonce-misuse resistance, you can even use the same nonce (say $0...0$) for all messages, so you don't need the hashing trick. If it is not, a hash function that is not collision resistant does not make it secure because an attacker can find different messages that hash to the same value, so you will end up using the same nonce for different messages. I don't know whether ChaCha20 Poly1305 together with a cryptographic hash function provides nonce-misuse resistance, but unless this is proven somewhere (or at least some other evidence is provided), you should not assume it.


Security of deterministic encryption that uses CBC mode and plaintext as iv As title, is this a safe deterministic encryption to use the second block of plaintext as IV, and encrypt with CBC mode?

I am sure that the second block used as IV is different than the first block for each record, so there won't be an "all zeros" problem.

No, you should not do that. Any time you encrypt a message with CBC you should use a new, random IV and send it together with the ciphertext. Don't encrypt the IV after usage.

The IV for CBC mode has to be unpredictable. That means you can't reuse an IV and you should not take any already used value from elsewhere. That was the problem of TLS with the BEAST attack, you maybe have heard of it. As soon as an attacker can make any statements about the IV there could be a serious security problem with your scheme.

IVs are also used to make the encryption more random - with your scheme, your IV only depends on your message, so the ciphertext is always the same when the message is the same. We mostly don't want that because it would show an attacker that we are sending the same message again.


Calculating XOR Key Sizes I've been playing around with the Matasano crypto challenges (cryptopals.com). I had a couple false-starts on the challenge that has you creating a program to calculate the key size of a XOR encrypted file using Hamming Distance of the bits (Index of Coincidence). After some head banging and pen and paper work on graph paper, I arrived at a working solution.

I've been playing around with my new toy script with different ciphertexts and key lengths and I noticed that for key sizes greater than 12 bytes, it works well (in my limited testing) and will accurately return the correct key size. For shorter key sizes, the most probable key length returned is a multiple of the correct key size. In fact the first few most probable key sizes are multiples of the correct key size and then the correct key size will appear further down in the results but with a higher probability ranking (based on Hamming Distance), than smaller, incorrect values.

Here's some examples that demonstrate what I'm talking about:

key = "eatoin shrdlu"

key.length

13

Let's XOR encrypt our plaintext with the key and get cipherText:

cipherText = XOR-Encrypt -String data -key key

cipherText (line breaks added)
21041a01001d003501010c090745151503021d000401060c4c31040f54240803491d1b191d4c14
070e011b491a4816482421223a2841161a0e4200070017441a140914114f060800050100101914
0941190e0a06491d0d52011f160411111c454e571b1152011a1017181b010c4e57120606174c01
0a41190e020b00161e171615550714134f1d0645531f1d161f01450e1a0a49014653091e084c01
0c0c114f061c00191d01104c14450301010a06001c0e520c1505004115010d4e571b090644181d
004135190c0047161a014404141304541b064e441c48050d181d45170103070b52120a1b080501
1c4110061a0d4c1c1b0716095b

Let's run this through the XOR brute forcer to see what it says about the key
size:

XOR-Brutr -MaxKeySize 40 -String cipherText -Encoding base16 | Sort-Object AvgDist

KeySize          AvgDist
-------          -------
13               2.74660633484163
39               2.78461538461538
26               2.81730769230769
33               2.8989898989899
40               2.905
25               2.93
38               2.94210526315789
...

Beautiful! The result correctly calculates that the key size is 13 bytes, but
with smaller keys....

key = "eatoin shrdl"

key.length

12

cipherText = XOR-Encrypt -String data -key key

XOR-Brutr -MaxKeySize 40 -String cipherText -Encoding base16 | Sort-Object AvgDist

KeySize          AvgDist
-------          -------
24               2.58333333333333
36               2.66111111111111
38               2.85789473684211
40               2.915
19               2.95215311004785
29               2.97536945812808
22               3.00909090909091
16               3.02232142857143
23               3.03381642512077
18               3.03703703703704
37               3.03783783783784
14               3.05357142857143
30               3.05714285714286
32               3.0625
27               3.06481481481481
12               3.06578947368421
28               3.06632653061224
...

Our top result is not 12, though 12 is the greatest common denominator
of the top two results.

If we set the MaxKeySize to a higher value and use a 26 byte key:

key = "eatoin shrdluuldrhs niotae"

ciphertext = XOR-Encrypt -String data -key key

XOR-Brutr -MaxKeySize 104 -String CipherText -Encoding base16 | sort avgdist | select -First 10

KeySize          AvgDist
-------          -------
52               2.59615384615385
78               2.62179487179487
104              2.64423076923077
81               2.66666666666667
26               2.66826923076923
84               2.67857142857143
...

Again, a multiple of the actual key rises to the top.

Question: Why does this pattern emerge? Why does the Hamming
Distance favor multiples of the actual key size? Should my script
determine the gcd of the first few results and weight the gcd
more heavily and return it as the probable key?

First off, the values above that are showing as AvgDist are actually Normalized Average Hamming Distances, not Average Hamming Distances.

I wrote a quick script to do some testing around this issue. Details are here, http://trustedsignal.blogspot.com/2015/06/xord-play-normalized-hamming-distance.html, and I won't rehash it all. Multiples of the actual key size come out as more probable to be the actual key size because of the way normalization is done. When the average Hamming Distance is divided by the key size, that's what normalization is, that larger key size generally results in a smaller Normalized Average Hamming Distance -- see the blog post for an example.

For instance, if the Average Hamming Distance with a XOR key size of 3 is 7 and you divide 7 by 3, you get 2.333. If an Average Hamming Distance with a XOR key size of 9 is 19, when you divide by 9, you get 2.111.

In my testing across an admittedly limited sample set, I ended up using random text samples from 80 different English language texts from Project Gutenberg, the XOR key size with the smallest Normalized Average Hamming Distance was the correct key size in about 40% of the cases, where I calculated Normalized Average Hamming Distance for key sizes up to four times the size of the actual key size.

I also found a relatively simple way to improve the probability of returning the correct key size by calculating the frequency of occurrence of the greatest common denominator for the top n probable key sizes. So you take each of the top n key sizes, I was playing around with using the top five or six and you get the GCD for each pair in that list, if one value occurs more frequently than the others, isn't 1 or 2 and is in the list of the top 5 or 6 values, then that's likely to be the correct key size. Using this method, I was able to get the correct key size more than 90% of the time.

Again, I'm a relative noob when it comes to all things crypto, so it's entirely possible my results are bogus and the result of a flawed testing methodology, flawed programming logic, bad sample size, etc.

It would be great if smart folks would read the post and tell me where I went wrong.


What's the difference between trapdoor and encryption? Trapdoor is a function taking as input $x$ and givings us output $y$ where it is hard to convert $y\rightarrow x $ back without knowing a secret $s$.

I think that $y$ is an encryption of $x$ under a some certain key($s$ or its associated public key).

So is trapdoor encryption?

A trapdoor function doesn't have the security requirements of an encryption function. If you directly use a trapdoor for encryption you open yourself up to related key attacks, known plaintext attacks, malleability  attacks and a whole host of other attacks.

Trapdoor functions are used as a single piece of a larger encryption function that handles all these issues.


Security estimation of LWE using "On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL" I recently found this paper eprint which estimates security of LWE instantiations using an improved Dual attack.
However, I got confused looking at their example in this site.
For example, in the case of NewHope their example gives states that minimum operation (rop) using dual attack is $2^{371}$, whereas the minimum $\beta$ is $1168$. So following the NewHope paper the securty of NewHope should be $2^{.2075*1168}\ =\ 2^{242}$. Which indeed increases the security of the NewHope. I am wondering which should I take as the bit security?

Another question is definition of $\alpha$, in their paper they define $\alpha=\sigma*\sqrt{2\cdot \pi}/q$ whereas in the example they have taken $\alpha=\sigma^2/q$ (NewHope parameter).

I asked the question to the author directly.
To answer the first question, authors of NewHope estimate their security very conservatively, whereas the estimator takes many other things into account. Specifically, here is the answer I got from the author.

  Hi, Id' suggest to use their claimed security. To explain the differences:

  The estimate you quote is the paranoid estimate which differs in the leading constant in the exponent from BKZ.sieve
  New Hope conservatively assumes one SVP call suffices (we uses 8n which is less conservative)
  New Hope uses a different technique to amplify success of the dual attack. For the parameter sets considered here, their estimate means amplification is essentially free, whereas the estimator assumes amplification has a considerable costs.

For the second part, the clculation of $\alpha$ was wrong. It should be $\sigma\cdot\sqrt{2\cdot\pi}/q$


Why isn't this HMAC construction/check secure? A MAC is calculated the following way:

mac = sha1(secret || m)[0:8]

[0:8] denotes taking the first 8 characters from the resulting hash.

The length of the secret is unknown. Users (and potential attackers) can check the validity of a particular MAC and message pair online.

if(macInput == sha1(secret || m)[0:8]){
   // ok
}else{
   // access denied
}

Can this be attacked? I heard it can, but I don't see why and how.

OK, there are two issues with this:

First, the MAC length is at most 64 bit, that is an attacker could try to brute-force-find a valid MAC with "merely" $2^{64}$ submissions, which is border-line feasible for large companies today.
If it actually only is 8 hex character, then each hex character encodes at most 4 bits of information and thus you get $8\cdot 4=32$ bits for the MAC security meaning brute-force would take at most $2^{32}$ (around 4bn) tries to recover a valid MAC.

Second, much more severe is the naive verification of the MAC which will probably allow for a classic timing side-channel attack.
Chances are that this multi-byte equality verification is implemented as an "optimized" check, that is (in a python-ish way):

if len(lb)!=len(rb):
   return false
for (lb,rb) in zip(l_input,r_input):
   if lb != rb :
      return false
return true

Which checks the that the input lengths match and then pairs all the bytes at the same position in both inputs and outputs false as soon as a miss-match is detected and true if no missmatch is found.

Now what we can do is to measure the time it takes to verify our MAC. So we would start of with 7 0 characters and prepend each possible value (character) value to this string. We send all to verification. The one that takes longest has a match on the first character. Now we fix this first character that we just verified and continue with the second with the same method. We continue with this process until we have recovered the full MAC and get access in return.

If we get all-equal times for the first character, we take iterate over all possible choices for the first two characters (enlarge as needed). If we know the size of the information $b$ (in bits) encoded in the constant-time verification data structure (eg 8 for byte-wise, 32 for integer-wise, ...) and we know the mac information $l$ in bits, then we take at most the following amount of calls to the verification oracle to recover the valid MAC:

$$n=2^b\cdot(l/b)$$

If in your case 8 hex characters need to be verified this becomes $2^4\cdot 8=256$ calls to the verification oracle (because the effective information of the hash is 32 bits composed of 4 bit elements).


Calculation of time to crack a SHA-256 hash A problem is given: 1 million users are authenticated with 9-digit PIN codes (e.g. 343534643). The PIN values are stored as hash values in a database. The hash is SHA-256, and is computed as:

hash=SHA-256(password|username)

An attacker has a graphics card which can compute 500 million hashes in a second. How long does it take to crack at least 1 password from the 1 million in the database?

Could anyone please help with this problem?

The "million usernames" is a red herring, because the user name is used as "salt": the hash value is computed over the password and the user name. When the attacker tries a potential password, he must choose which user name he puts in the hash function; and if a match is found, then this will be for the hash value for this user name only.

In other words, the attacker cannot do any better than choosing one hashed password to crack, for a specific user name, and crack that. That there are one million of hash values does not give any advantage to the attacker.

Now, consider that the attacker tries to crack one password; he has the hash value and the user name. There are $10^9$ possible passwords. If we assume that the passwords have been chosen randomly and uniformly, then the best that the attacker can do is to try them all (in any order) and hope for a match. On average, the attacker will need to try about half the key space, i.e. 500 millions, of possible passwords until a match is found. Since the attacker's hardware can compute 500 millions of hash values per second, the average time to crack one password is one second.

Similarly, if the attacker wants to crack, say, 10 passwords for 10 distinct users, then it will take him 10 seconds on average.

User names, as salt values, are suboptimal. In the context of this question, user names work well: their role is to prevent parallel attacks, and since no two users have the same name, then parallel attacks are indeed prevented. To break $n$ passwords the attacker must pay $n$ times the cost of breaking one password.

However, in practice, user names are reused, in two ways (at least):

When a user changes his passwords, his name remains the same, so the old and the new passwords will be hashed with the same "salt". Attacking both simultaneously will be possible.
User names are unique on a given system. But software is reused. To put things bluntly, all systems will have an "admin" user with that name; this opens the road to parallel attacks, e.g. precomputation: the attacker could precompute hash values for a given user name (such as "admin") and the billion of possible passwords; thus, when the attacker actually gains access to the database, breaking the "admin" password will be a matter of a single lookup, which will take a microsecond or so (assuming the table is in RAM), not one second. Attackers could even collude and exchange tables, so that one attacker computes the table and his dozens of friends benefit from that one-time effort.

Thus, random strings are considered to be better salts, because they will ensure worldwide uniqueness with high probability, much better than user names (assuming that the random salts are large enough; UUID are good practical salts).

On the concept of password hashing, see this answer for a lengthy introduction.


Are there signatures that don't have subliminal channels? Are there signatures that don't have subliminal channels and also don't require commitments or zero-knowledge proofs?

DSA or Schnorr signatures need a nonce which can leak valuable information. There are derandomization schemes, but the verifier can't check that the signer used them without extra steps.

Is there a signature that avoids these problems?

According to this answer, RSA with the "usual" "padding scheme, described in PKCS#1 as the

'old-style, v1.5' padding," can be made to satisfy that; one would need to specify NULL or omission

and require that the public exponent's prime factors are all easily

findable and sufficiently bigger than the 4th root of the modulus.


From 2-round key-exchange protocol to a public-key encryption scheme CPA-secure I have to solve this exercise and I really could use some help:

Show that any 2-round key-exchange protocol (that is, where each party
sends a single message) satisfying $Definition$ $9.1$ can be converted into
a public-key encryption scheme that is CPA-secure.

$Definition$ $9.1$:
A key-exchange protocol II is secure in the presence of
an eavesdropper if for every probabilistic polynomial-time adversary $A$ there exists a negligible function negl such that

$Pr [KE^{eav}_{A,\pi} (n) = 1] \le \frac{1}{2}+ negl(n)$

The methods suggested in the comments are useful in practice, but they base on some specific key exchange protocols. It's useful to proove that a public key encryption scheme can be created from any such $KE^{eav}$-secure protocol.

Notation

Let $\langle s_A, m_A \rangle, \langle s_B, m_B \rangle$ denote the state and transmitted message from Alice and Bob within the protocol respectively.
Let $Prot_A(1^n) \rightarrow \langle s_A, m_A \rangle$ denote the process of Alice creating her secret state and the message to be transmitted to bob, $Prot_B(m_A) \rightarrow \langle s_B, m_B \rangle$ be the process of Bob sampling his random state and creating the message based on the random state and Alice's message. We then define the key to be $f(s_A, m_B) = k_A = k = k_B = f(s_B, m_A)$ for $f$ some predefined function.

Construction

Now, we create a public-key encryption scheme as follows:

\begin{align*}
    Gen&(1^n)  \\
    & \langle s_A, m_A \rangle \leftarrow Prot_A(1^n) \\
    & \langle s_k, p_k \rangle = \langle s_A, m_A \rangle \\
    & Output \space \langle s_k, p_k \rangle \\
    %
    %
    Enc_{p_k}&(m): \\
    & \langle s_b, m_b \rangle \leftarrow Prot_B(p_k) \\
    & Output \space \langle m_B, f(s_B, p_k) \oplus m \rangle \\
    %
    %
    Dec_{s_k}&(c): \\
    & \langle m_B, c' \rangle = c \\
    & k = f(s_k, m_B) \\
    & Output \space k \oplus c'
\end{align*}

Correctness

Since $f(s_k, m_B) = f(s_A, m_B) = f(s_B, m_A) = f(s_B, p_k)$ the correctness follows from the correctness of a one-time-pad.

Security

We can proceed to prove CPA-security by reduction. Assume there is an adversary $\mathcal{A'}$ which succeeds at breaking the CPA experiment for our public-key encryption scheme $\Pi'$. We construct an adversary $\mathcal{A}$ breaking the KE experiment as follows:

$\mathcal{A}$ receives $m_A, m_B, \hat{k}$ as input
$\mathcal{A}$ runs $\mathcal{A'}(1^n, m_A)$ and receives $m_0, m_1$
$\mathcal{A}$ samples $b \leftarrow \{0,1\}$ uniformly and computes $c = \langle m_B, m_b \oplus \hat{k} \rangle$
$\mathcal{A}$ runs $\mathcal{A}'(c)$ and receives $b'$
$\mathcal{A}$ outputs 0 iff $b = b'$

Now we have 2 cases to consider -- when $\mathcal{A}$ received the true key ($[K=\hat{k}]$) and when it received a uniformly random string ($K \neq \hat{k}]$). But in the first case, the result of the KE experiment will be 1 exactly when $\mathcal{A}'$ succeeds in the CPA experiment. In the other scenario, since $\mathcal{A}$ samples b uniformly, the result of the experiment will be 1 when $b = b'$ with probability $\frac{1}{2}$. Hence:

$Pr[KE^{eav}_{\mathcal{A}, \Pi}(1^n) = 1] = \frac{1}{2}Pr[KE^{eav}_{\mathcal{A}, \Pi}(1^n) = 1 | K = \hat{k}] + \frac{1}{2}Pr[KE^{eav}_{\mathcal{A}, \Pi}(1^n) = 1 | K \neq \hat{k}] =
\frac{1}{2}(Pr[Pubk^{CPA}_{\mathcal{A}', \Pi'}(1^n) = 1] + \frac{1}{2}) =
\frac{1}{2}(\frac{1}{2} + \frac{1}{p(n)} + \frac{1}{2}) = \frac{1}{2} + \frac{1}{2p(n)}$

This contradicts $\Pi$ being $KE^{eav}$-secure, hence $\mathcal{A}'$ cannot exist and $\Pi'$ is CPA-secure.


How can I verify certificate signature algorithm in TLS 1.3 using PSS? I've read this post but I'm still unable to understand some things.

I'm trying to verify that the signature algorithm used in the certificate matches the proposed list from the client. (As it's mandatory in TLS 1.3)

But I cannot understand the difference in verification when the client offers both signature schemes 'rsa_pss_rsae_' and 'rsa_pss_pss_'.

Both of them indicate that the signing can be in PSS, but from my understanding, the 'rsa_pss_rsae_' is specifying constraints on the public key? Is that correct?

Does it mean that when verifying the certificate signature algorithm, both will be signed with the OID RSASSA-PSS BUT the difference will be in the public key?

(as in RSA (rsaEncryption) or PSS only (RSASSA-PSS) key)

It depends on what publickey is. An X.509/PKIX cert contains a SubjectPublicKeyInfo structure which contains an AlgorithmIdentifier that specifies what type the key is and in some cases to some extent how it is used, plus the actual publickey value (wrapped in an OCTET STRING type).
See also the links to 3279 and 4055 (which is updated by 5756).
These TLS1.3 SignatureScheme codes (both the RSA_PSS_RSAE set and the RSA_PSS_PSS set) specify that in the cert that contains the publickey usable to verify the PSS signature (often imprecisely called the signing cert) the SPKI AlgorithmIdentifier use a particular OID; they do not constrain the actual publickey value. Is that a constraint on the publickey? You decide.

For the signature_algorithms_cert extension, yes for PSS-signed certificates the two AlgorithmIdentifier's for the signature algorithm in the child cert will use the OID id-RSASSA-PSS and applicable parameters, while the parent cert's SPKI is constrained as above. When the signature_algorithms extension applies to protocol signatures rather than cert signatures, the protocol signatures are not identified by any OID (see 4.4.4) and the leaf cert's SPKI is constrained as above; this is equally mandatory.


Finding strong primes Wikipedia lists the following conditions for a prime to be strong:

$p-1$ has large prime factors. That is, $p = a_1 q_1 + 1$ for some integer $a_1$ and large prime $q_1$.

$q_1-1$ has large prime factors. That is, $q_1 = a_2 q_2 + 1$ for some integer $a_2$ and large prime $q_2$.

$p+1$ has large prime factors. That is, $p = a_3 q_3 - 1$ for some integer $a_3$ and large prime $q_3$.

This seems pretty vague to me. What does "large prime" mean? How large should $p_1$ be compared to $p$?

And, most important, what is the standard way to generate large strong primes, or to check if a large prime is strong? Also, is using safe primes (of the form $p = 2*q + 1$, where $q$ is a prime) safe and/or efficient?

All the properties discussed in the question are for strong primes $p$ in the context of using $p$ as a secret factor of a large composite $n$ which factorization should be intractable; these properties are given in the landmark RSA paper (1978), without justification. Properties thought for (often public) primes used in other cryptosystems can be different.

The first property

  $p-1$ has large prime factors. That is, $p = a_1 q_1 + 1$ for some integer $a_1$ and large prime $q_1$.

is intended to make factorization of $n$ using Polard's p-1 algorithm hard; this is relevant to some degree because this algorithm has a component of its cost proportional to the highest factor of $p-1$, where $p$ is the factor of $n$ exhibited by the algorithm.

Similarly, the third property

  $p+1$ has large prime factors. That is, $p = a_3 q_3 - 1$ for some integer $a_3$ and large prime $q_3$.

is intended to make factorization of $n$ using Williams' p+1 algorithm hard; this is relevant to some degree because this algorithm has a component of its cost proportional to the highest factor of $p+1$, where $p$ is the factor of $n$ exhibited by the algorithm.

One standard that considers the above is FIPS 186-4 (appendix B.3), with $q_1$ and $q_3$ required to be larger than 100 bits when $p$ is 512 bits (and optionally: $q_1$ and $q_3$ larger than 140 or 170 bits when $p$ is 1024 or 1536 bits). It is hard to tell quantitatively when it makes actual sense taking precautions regarding such properties  (beyond conformance to standards): it is pointless when generating a few two-factors RSA keys of at least 1024 bits; it might be useful when extremely many RSA moduli with relatively small factors (e.g. in multi-prime RSA) are generated, and an adversary would benefit finding the factorization of any modulus (rather than of a particular modulus); see this question and its answers.

The second property

  $q_1-1$ has large prime factors. That is, $q_1 = a_2 q_2 + 1$ for some integer $a_2$ and large prime $q_2$.

has to do with reducing the odds that an RSA cycling attack succeeds; see this answer. I fail to find a quantitative assessment of how big $q_2$ should be, or any modern standard with this requirement. I accept the consensus that RSA cycling attacks have negligible success odds for practical key sizes (but would very much appreciate a quantitative argument!).

The standard ways to generate a large strong prime $p$ with the first and third properties (perhaps the second if required) is to choose the auxiliary primes $q_2$ (if required) then $q_1$, and $q_3$, then generate $p$; rather than choosing $p$, then trying to exhibit $q_1$ (then $q_2$ if required) and $q_3$. The later approach would be very computationally intensive: if $p$ is a random 512-bit prime, it requires the factorization of a $(p-1)/2$ and $(p+1)/2$, which are mostly random 511-bit integers, and that's typically a hard job. The former approach (used in practice) introduce significant complexity, but relatively little computational burden; several such methods are detailed in the aforementioned FIPS 186-4 appendix B.3.


Is it possible and safe to use SAKKE for signing/verification, rather than for encryption? Is it safe to use the Sakai–Kasahara key encryption algorithm (SAKKE) for signing/verification, rather than for encryption? (Example at bitbucket.org)

In particular, I want many Bobs to be able to get many public keys (for an offline identity Alice) which can later be used to verify the signing of some data by Alice, without anyone (apart from Alice) knowing that the public keys belong to Alice.

In general, encryption schemes are not suitable for signatures. The misconception may stem from the symmetricity of operations in RSA encryption and decryption, which allows the core scheme to be easily used for signing as well.

That being said, all identity-based encryption schemes (IBE) can be used as general signature schemes, see e.g. Boneh & Franklin's original paper (https://crypto.stanford.edu/~dabo/papers/bfibe.pdf), last para of Ch.6. You will lose the "identity-based" in that setting though, so there may be not much point in using an IBE-scheme as a general signature scheme. In this sense, it is safe to use SAKKE as signature scheme, but this is probably not what you are looking for.

What I gather from your problem description, the problem is to detach the personal identity from the signature identity. This is not necessarily a cryptographic problem, as one might as well obtain "usual" PKI certificates using a pseudonym instead of the real name, or generate and publish personal PGP certificates with pseudonyms.

In a more restricted setting, it may be desirable to be able to sign anonymously, but still as a part of certain group. This falls under the category of group- and ring signatures. In the former, the anonymity can be revoked in special cases and in the latter not.

In the identity-based setting the concept is called Identity-Based Signature (IBS, e.g. Hess IBS, implemented in the PBC-library). In IBS, the verification can be performed using system-wide parameters and the identity only. Even in this case, the anonymity needs to be based on using pseudonyms. The advantages over conventional PKI include:

The ability to announce a space of pseudonyms even before creating any private keys
Depending on the administration of the master key, simpler and faster production of pseudo-identities with a corresponding private key.

Most likely the first advantage might suite your needs, as Alice could simply announce a space of identities (e.g. 0xA11CE000...0xA11CEFFF, 0x12345678...0x1234FFFF) and then use them up as needed, without having to bother creating private keys until actually required.

There is, however, a catch: if the system parameters (including the master key) are managed by a third party, this party would likely be able to associate the identities with Alice. If Alice manages her own master key, obtaining and publishing this public key is comparable to the effort of publishing a PKI public key. This will diminish the value of choosing the identity-based paradigm anyway.


HKDF: Difference between salt and info I want to do generate individual AES keys for a number of smart cards, based on a random master key (key diversification) and the serial number of the card.

According to the answers to this question HKDF is the/one way to go.

HKDF has three inputs, ikm, salt and info. Feeding in the serial number as part of ikm seems to be incorrect usage (and maybe dangerous because it makes the IKM less random?). That leaves salt and info, which one should I use?

If all you're using HKDF for is deriving subkeys from a uniformly random master key, you don't really need the Extract part of HKDF.  So you can simply use your master key directly as the IKM input to HKDF-Expand, and the serial number (plus possibly other identifying information, if you e.g. may need to derive multiple keys per card) as the info input.


Is there a difference between asking for a signature and asking for a decryption in challenge-response authentication? Consider the following two authentication schemes. In both cases the server knows a public key of the client (for a signature system in the first and an encryption system in the second case).

Scheme A

Server presents a randomly generated plaintext to the client, and asks the client to sign the message. The server can verify the signature using the public key.

Scheme B

Server randomly generates a plaintext, encrypts the message using the client's public key, and asks the client to decrypt and send back the plaintext. The server can verify that the plaintext matches the one it generated.

The second scenario feels less secure than the first scenario, but I cannot quite put my finger on why.

Is there any effective difference between the two authentication schemes?

As long as properly implemented using secure algorithms, there is no real security difference. In both cases the protocol is secure as long as the underlying signature or encryption algorithm is.

However, one difference is the random number used:

In scheme A the numbers must be unique. If the server ever reuses a number, then an adversary could replay a previous signature they have observed.
In scheme B the numbers have to be unpredictable, or an adversary can authenticate just by guessing correctly, but as long as the encryption algorithm is semantically secure, repeats are not a problem.

You need larger random numbers in the first scheme than the second, due to the uniqueness requirement.

As mentioned in the other answers, this is not secure against man in the middle attacks. It could be run in a channel that prevents those. For example, in a typical TLS situation the client would have authenticated the server already, man-in-the-middle attacks would be ruled out, and the server could use either of these to authenticate the client.


Generating an IV for ESP 3DES-CBC I have an application written in C, running in Linux. It uses IPsec (ESP) (manually putting the IPSec packet together) to send certain packets. The algorithm used for encrypting the payload is 3DES-CBC (using Libgcrypt).

So my doubts are regarding the IV that I have to use. For this scheme to be secure:

Is it enough to generate a random IV?
If so, what random number generator source should I use for this? (e.g. /dev/random)

The other requirement that I noted while reading RFC 1851 is that the IV should be 64-bit long.

Update:

NIST Recommendations for Block Cipher Modes of Operations, Appendix C [PDF] states:

  There are two recommended methods for generating unpredictable IVs.
  The first method is to  apply the forward cipher function, under the
  same key that is used for the encryption of the  plaintext, to a
  nonce. The nonce must be a data block that is unique to each execution
  of the  encryption operation. For example, the nonce may be a counter,
  as described in Appendix B, or  a message number. The second method is
  to generate a random data block using a FIPS-approved random number
  generator.

Tried to find a list of all Linux random number generator implementations that are FIPS-approved but couldn't find much information on this.

To generate an IV securely for CBC mode, there are two obvious ways to do it (and both are cited by NIST):

For each packet, select a nonce (the IPSec sequence number, padded out to 64 bits, works fine), encrypt that in ECB mode, and then use resulting ciphertext block as the IV.  An equivalent way to do that is to take your 64 bit nonce, prepend that to the  byte plaintext, encrypt the plaintext (and the 64 bit nonce) with a fixed IV, and then transmit the first 64 bits of the ciphertext (not including the fixed IV you used) as the IV, and the rest of the ciphertext as the ciphertext body.  It turns out this is equivalent to the first method because of how CBC mode works internally.
For call a random number generator to select a 64 bit IV, and use that.  The text from NIST you cite says the rng has to be FIPS-approved; actually, unless you care about FIPS compliance, any unpredictable rng should work; I don't expect any problems /dev/random

Personally, I suspect you'll find the first option is easier.

The other thing you ought to consider is integrity; there's a surprising amount of mischief someone can cause by modifying the ciphertext, and then having someone attempt to decrypt it.  Now, IPSec has an answer to that (including a MAC along with the ciphertext; if someone modifies the ciphertext, the MAC will fail); are you including that?

BTW: the RFC you cite (RFC1851) is rather out-of-date, and won't interoperate with modern versions of IPSec; at the very least, modern versions will expect the padding to have a specific pattern.  That doesn't matter if you're implementing both sides of the protocol; however if the other side is a non-ancient IPSec implementation, look at RFC2406 and RFC2451


What's the downside of using X.509 in SSH instead of PKI ssh uses public keys for authentication and not signed X.509 certificates. Specify a drawback which would be the use of X.509 certificates instead of public keys.

I've tried to look up a lot of different things, but the certificate seems superior in every way.

The fundamental difference is in how (and wether) the clients and servers identity is validated.

In X.509, keys are authenticated by virtue of being issued by a trusted certificate authority. That makes it easy to use when the client starts out knowing nothing about the server's identity, and the server does not need to know anything about the client's identity. But can be a particular nightmare to manage when the client also needs to authenticate against the server.

In SSH, keys are self-generated (similar, although not the same, to self-signed X.509 certificates), and are authenticated by relying on a fingerprint, which has to be transmitted out-of-band. That makes it easier to use in scenarios where both ends are reasonably trusted. SSH also has built-in mutual authentication. The client verifies the server's identity by its host key (what a server X.509 does in TLS), and the server verifies the client's authority through the entry in the authorized_keys file (that's the equivalent of X.509 client certificates).

SSH is mostly used for internal communications within an organization, where both ends are, at least somewhat, trusted. The overhead of generating and distributing X.509 certificates would put a serious burden on many use cases (just think of spinning up test servers on a daily basis in a development environment!).

It is also designed to not rely on the destination name (so you can use the DNS name most of the time, and IP addresses if your DNS system fails for some reason).

That said, you can actually configure SSH to use X.509 certificates. As far as I understand it, though, it only uses the public and private keys, and ignores the rest of the certificate.

And you can also get most of the benefits of an X.509 certificate with SSH by adding an SSHFP record to your DNS (this is non-trivial as you first have to enable DNSSEC). With an SSHFP record, one could argue you are actually in better shape than with an X.509, because you get the benefit of an authenticated host key, without relying on the somewhat broken certificate-authority trust model.

Bottom line: The SSH mechanism and X.509 are designed for different scenarios. Both are reasonably secure in their respective niches.


Decryption in Goldwasser-Micali Scheme Referring to the following URL: http://cryptowiki.net/index.php?title=Goldwasser_Micali_cryptosystem

The decryption of the message is based on wether the bit is a QRn or not, but how do we know/verify (the mathematical operations) if it is a QRn or not.

Well, we know that the ciphertext $c$ is a Quadratic Residue, then both $c \bmod p$ is a QR (modulo $p$) and $c \bmod q$ is a QR (modulo $q$).  And, we know that (for valid ciphertexts) $c$ has a Jacobi of 1, and so if it is not a QR, then both $c \bmod p$ is a non-QR (modulo $p$) and $c \bmod q$ is a nonQR (modulo $q$).

And, we have the private key, and so we can have the value of $p$.  So, one simple way to decrypt $c$ is to first evaluate $c \bmod p$, and then check if it is a QR; for example, check the value of $(c \bmod p)^{(p-1)/2} \mod p$; if it evaluates to 1, then $c$ is a QR (and so the plaintext is 0); if it evaluates to $p-1$, then $c$ is not a QR (and so the plaintext is 1).


TLS - sharing 1792 bits of unidirectional keys I've just watched a video on the TLS protocol and learnt that it uses unidirectional keys (meaning keys for both sides, from browser to server and from server to browser).

Given that the server uses TLS_DHE_RSA_WITH_AES_256_CBC_SHA256 , how are all those keys shared? We need:

AES 256-bit key for the browser
AES 256-bit key for the server (CBC)
AES 128-bit IV for the browser
AES 128-bit IV for the server (CBC)
HMAC 512-bit key for the browser
HMAC 512-bit key for the server

So in total we need 1792 bits, if we use 2048 bit Diffie-Hellman we can at most share 256 bits securely, if we take the SHA512 of it we get 512 bits, but how are we gonna securely derive so much keys from it?

Indeed we could use PBKDF2 to derive keys, but that would be kind of expensive. Does anyone know how TLS does all this?

In TLS, the key exchange step results in a key called the master secret which is then derived into as much key material as needed with a custom key derivation function, called in TLS terminology the PRF. It is not slow -- contrary to PBKDF2, the "PRF" of TLS is not for handling password and thus has no need to be slow.


What is the most secure encryption algorithm to encrypt my password database? The password manager I use lets me choose an algorithm from the list below in order to encrypt my password database:

Microsoft Base Cryptographic Provider v1.0:

RC2-128
RC4-128
DES-56
3DES TWO KEY-112
3DES-168

Microsoft Enhanced Cryptographic Provider v1.0:

RC2-128
RC4-128
DES-56
3DES TWO KEY-112
3DES-168

Microsoft Enhanced RSA And AES Cryptographic Provider:

RC2-128
RC4-128
DES-56
3DES TWO KEY-112
3DES-168
AES-128
AES-192
AES-256

Microsoft RSA SChannel Cryptographic Provider:

AES-128
AES-256
RC2-128
RC4-128
DES-56
3DES TWO KEY-112
3DES-168

Microsoft Strong Cryptographic Provider:

RC2-128
RC4-128
DES-56
3DES TWO KEY-112
3DES-168

The default value is RC4 with the key length of 128 bits from Microsoft Strong Cryptographic Provider.

Now I have two questions:

Which algorithm is the most secure?
Does the algorithm provider matter?

Edit:

@mikeazo♦: I use Kaspersky Password Manager v5.(Unluckily, I don't have enough reputation to leave a comment!)

The number denotes the size of the key used - for a given algorithm, the larger the key, the more secure it is - hence AES-256 is better than AES-192 is better than AES-128.

The key size is measured in bits - so in terms of its protection against a brute force attack (attacker tries all possible keys) a 256 bit password is not twice as hard to break as a 128 bit password, it is 34000000000000000000000000000000000000 times as hard.

But there are other ways to attack encryption - exploiting mathemetical flaws/coincidences in the algorithm. Although 3DES uses 3 56 bit keys, the effective key size is only around 120 bits. But it is still considered better than RC2-128.

  Which algorithm is the most secure?

Of those you have listed, AES-256

  Does the algorithm provider matter?

No. In effect, it is just a list of available algorithms. But you do need to ensure the algorithm is available anywhere you want to decode the data.


What are the major differences between SET and SSL? SET and SSL are usually used as secure payment protocols. What are the major differences between them? Which one is better?

TLS

TLS (SSL) is a general, not payment-specific protocol. Most important in the context of this question, it is current best practice.

SET

SET was introduced around 1996 and declared dead around 2003.


Are this recommendations from Colin Percival correct? In this article: http://www.bsdcan.org/2010/schedule/attachments/135_crypto1hr.pdf

He has said:

AVOID: Poly1305. If your name is Daniel Bernstein, go ahead and use
this Otherwise, you’re never going to produce a secure and correct
implementation
DON’T: Use modes which provide both encryption and authentication
PROBABLY AVOID: Elliptic Curve signature schemes

First off, it sounds like you already have an opinion and should talk to Colin directly.

My take is, at least at the time, he was very much in favor of tried-and-true (and easy, relatively) encrypt-then-mac schemes.  Namely, he advocated CTR+HMAC.  This is easy and known to be secure.  You pay for it a little by deriving more key material than otherwise needed, by more expensive computations, and by more algorithms.  None of those things matter to most users in most settings.

In 2010 Poly1305, related AE schemes, and EdDSA were less well-known, less well standardized (which often serves as an implementation aid), and less widely implemented than good old AES-CTR and SHA2-256 (and RSA).  Again, these are me casting about to explain Colin P. when in fact you could just ask him if you so desire.


SIDH cryptosystem question I'm trying to understand the SIDH cryptosystem and got confused at this point:

Alice fixes base $\{P_A,Q_A\}$ so that it generates $E_0[l_A^{e_A}]$. Then she chooses secret parameters $m_A,n_A$ and computes the secret isogeny $\phi_A: E_0 \to E_A$  with kernel $\langle [m_A]P_A +[n_A]Q_A\rangle$. Further section 4 of the 2011 SIDH paper states that both $P_A$ and $Q_A$ have order $l_A^{e_A}$ and are independent of each other.

Doesn't that mean that $[m_A]P_A$ and $[n_A]Q_A$ also have order $l_A^{e_A}$ and therefore $ker(\phi_A) = E_0[l_A^{e_A}]$? That would mean that $\phi_A$ is not secret.

I invented SIDH. $E_0[\ell_A^{e_A}]$ has cardinality $(\ell_A^{e_A})^2$. Each of $P_A$, $Q_A$, and $R$ has order $\ell_A^{e_A}$ and they all generate different subgroups. This is possible because $E_0[\ell_A^{e_A}]$ is a non-cyclic group.


Requirements for the modulus in the Massey-Omura three pass protocol In the Massey-Omura three pass protocol:

How many bits long should the prime modulus $M$ be in order to be secure?
Should the $M$ be secret?
Should the $M$ be generated every time or it could be reused to generate new keys?

How many bits long should the prime modulus $M$ be in order to be
  secure?

The modulus $M$ should be long enough to prevent discrete logarithms from being computable.
As of 2015 this means 2048 bits length is fine, but for other (official) recommendations you should consult keylength.com

  Should the $M$ be secret?

You can make $M$ secret but making it public shouldn't affect security as long as it's large enough to prevent any discrete logarithm computations from succeeding.

  Should the M be generated every time or it could be reused to generate new keys?

Usually it is rather computationally intensive to generate such moduli. Again, you can generate a new modulus every time if you fear there may be unknown backdoors in public parameters or you want to dodge something like Logjam, but if the modulus is long enough you don't have to generate new moduli on every connection.