Is it possible to find two sets such that their hash xor summation is the same? Consider two sets $A=\{a_1,a_2,\cdots,a_n\}, B=\{b_1,b_2,\cdots,b_m\}$; $m,n$ can be different. we can calculate the xor summation of each element's hash value: $XOR(A)=(hash(a_1)\oplus hash(a_2) \oplus \cdots \oplus hash(a_n))$ and $XOR(B)=(hash(b_1) \oplus hash(b_2) \oplus \cdots \oplus hash(b_m))$. Is it possible that set $A$ does not equal set $B$, yet $XOR(A)=XOR(B)$?

As for the feasibility of finding such a colliding set, well, as long as the sets are allowed to be relatively long (e.g. at least as long as it bit values being xor'ed), then it is easy.

First off, we assume that the hash output is $n$ bits.  Then, we select $n+1$ distinct values $X_i$ and set $\delta_i = Hash(X_i)$.  Then, we use linear algebra to find a subset of the values $\{ \delta_1, \delta_2, ..., \delta_n \}$ that xor to $\delta_0$ (note, there is a probability that there won't be such a subset; that probability can be minimized by including a few extra values).

With such a subset $\{ \delta_{z_0}, \delta_{z_1}, ..., \delta_{z_k} \}$, we have $$Hash(X_0) = Hash(X_{z_0}) \oplus Hash(X_{z_1}) \oplus ... \oplus Hash(X_{z_k})$$

That is, the sets $\{ X_0 \}$ and $\{X_{z_0}, X_{z_1}, ..., X_{z_k} \}$ collide


MOV attack when $E(\mathbb{F}_q)$ is cyclic Suppose $P\in E(\mathbb{F}_q)$ and $R=dP$.

In the MOV attack, we compute $\alpha=e(P,T)$ and $\beta=e(R,T)$ and try to solve the discrete logarithm problem for $\alpha$ and $\beta$ in the finite field $\mathbb{F}_{q^k}$ where $k$ is the embedding degree.

But if $E(\mathbb{F}_q)$ is cyclic (which it can be even in the supersingular case), $\alpha,\beta$ are doomed to be $1$.

So what am I missing here?

For the purposes of the MOV attack you choose $T$ to be a point in $E(\mathbb{F}_{q^k})$.


Is there a way to make a black-box function side-channel attack resistant? If I have no knowledge of the inner workings of a function, (i.e. a black box function) is there a way to make it side-channel attack resistant? (For reference, I'm working with a JavaScript encryption library)

If I have no knowledge of the inner workings of a function, (i.e. a black box function) is there a way to make it side-channel attack resistant?

No, not really.  When we make a cryptographical function 'side-channel' resistant, we generally use one of the following strategies:

We modify the cryptographical implementation not to leak anything to that specific side-channel.  For example, for timing and cache side channels, we can make the algorithm run in constant time and constant memory accesses (or, at least, independent of any secret data).
We modify the cryptographical implementation to scatter the internal information so that getting information on only part of the cipher state does not divulge any information about what we're actually doing.  For example, in a "thresholding" implementation, we might convert each bit on the cipher state into three internal bits (where the state of the logical bit is the exclusive or of the three internal bits).  By doing this (and randomizing each individual internal bit), we ensure that the adversary needs to get side-channel information on all three bits simultaneously, rather than any one or two...
We can exploit the mathematical properties of the cryptographical operation, performing the operation on random data, and then converting that into the result we are interested on.  The canonical example of this is RSA ciphertext blocking; when we want to decrypt a ciphertext $C$, we select a random value $R$ and compute $R^eC \bmod N$ (where $e, N$ is the RSA public key); as $R$ is a random value uncorrelated to $C$, this is a random value.  We pass this value to the low-level RSA decryptor, which will return $RC^d \bmod N$.  We then multiply this by $R^{-1} \bmod N$, and that gives us the actual plaintext.

Unfortunately, none of the above actually works in your scenario.  The first two involves modifying the cryptographical implementation, which you can't do,  The last uses mathematical properties of the cryptographical algorithm, which a black box generally will not have.


co-DHP* in G2 for type 3 pairing In type 3 pairing ($e:G_1 \times G_2\rightarrow G_\tau$ where $G_1\ne G_2$ and no isomorphism from $G_2$ to $G_1$ is known) we have co-DHP* problem:

  Given $H, aP \in G_1$ and $aQ\in G_2$ calculate $aH$

It looks like there should be equivalent problem in $G_2$:

  Given $aP \in G_1$ and $H, aQ\in G_2$ calculate $aH$

yet I haven't found it anywhere in literature. Is such problem mentioned in any paper? Or maybe it's proven to be easy?

In fact both assumptions you state are often implicitly made in the literature (I am, however, not aware of any explicit use of the latter). For instance various variants of the bilinear Diffie-Hellman problem in Type-3 groups imply the hardness of the assumptions you state, e.g., $\sf BDH\text{-}3$ [1; Definition 2] which we will recall below.

For the following explanations, let $\sf BGGen$ be an algorithm which, on input of a security parameter $\kappa$, outputs a bilinear group description ${\sf BG} := (\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T, p, P, \hat P, e)$. Here $\mathbb{G}_1$, $\mathbb{G}_2$, and $\mathbb{G}_T$ are three groups of common prime order $p$, where $p$ is of bitlength $\kappa$. $P$ and $\hat P$ are generators of $\mathbb{G}_1$ and $\mathbb{G}_2$, respectively, and $e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ is a bilinear pairing. Finally, we let ${\bf g} := e(P, \hat P)$. The $\sf BDH\text{-}3$ assumption states that for every PPT adversary $\mathcal{A}$ there exists a negligible function $\varepsilon(\cdot)$ so that it holds that
$$
\Pr\left[{\sf BG} \gets {\sf BGGen}(1^\kappa),~ a,b,c \stackrel{R}{\gets} \mathbb{Z}_p,~ {\bf g}^{abc} \gets {\cal A}({\sf BG}, aP,bP,cP,b\hat P, c\hat P) \right] \leq \varepsilon(\kappa).
$$

Now, it is not hard to show that any solver for one of the assumptions you stated implies a solver for $\sf BDH\text{-}3$. We will present an explicit reduction ${\cal R}$ for the second assumption (the reduction to the first one is left as an exercise). Before we do so we restate the assumption in our notation (wich we henceforth call ${\sf A}_1$).

Assumption ${\sf A}_1$ states that for every PPT adversary $\cal A$ there exists a negligible function $\varepsilon(\cdot)$ such that
$$
\Pr\left[{\sf BG} \gets {\sf BGGen}(1^\kappa),~ a,b \stackrel{R}{\gets} \mathbb{Z}_p,~ ab\hat P \gets {\cal A}({\sf BG}, aP, a \hat P, b \hat P)\right] \leq \varepsilon(\kappa).
$$
It is easy to verify that ${\sf A}_1$ indeed resembles the second assumption from the question (let $\hat P := Q$ and $H := bQ$).

Reduction ${\cal R}$ is implemented as follows:

Firstly, it obtains a $\sf BDH\text{-}3$ instance $({\sf BG}, aP,bP,cP,b\hat P, c\hat P)$ from a $\sf BDH\text{-}3$ challenger.
Secondly, it starts the adversary against ${\sf A}_1$ on $({\sf BG}, bP, b\hat P, c\hat P)$ to obtain $bc \hat P$.
Finally, it outputs $e(aP, bc\hat P) = e(P, \hat P)^{abc}$ as a $\sf BDH\text{-}3$ solution.

To sum up, the existence of $\cal R$ and the assumed hardness of $\sf BDH\text{-}3$ contradict the existence of an efficient adversary against ${\sf A}_1$.

Sidenote 1: The assumptions you state are quite natural assumptions in the Type-3 bilinear group setting.

Sidenote 2: The plausibility of the assumptions can also easily be confirmed in the Uber assumption framework [2].

References:

[1] https://eprint.iacr.org/2009/480.pdf

[2] Xavier Boyen: The Uber-Assumption Family. Pairing 2008: 39-56


What makes adaptive memory attack difficult for the adversary? On page 11, definition 2 of "Simultaneous Hardcore Bits and
Cryptography Against Memory Attacks", the paper outlines the following steps

(PK,SK) public key and secret key are generated by defender using Gen($1^n$).
Adversary $A1$ generates $m_0$ and $m_1$ and a $state$ using PK.
Defender randomly selects $b$ and encrypts $m_b$ invoking $ENC_{PK}(m_b) = y$, and given to $A2$.
Using challenge $y$ and $state$ generated by $A1$, adversary $A2$ guesses if $m_0$ or $m_1$ was encrypted in step 3.
The adversaries win if the guess is right.

My question:

In step 2, the $A1$ generates the two messages $m_0$ $m_1$ using the public key PK, but doesn't this make the game trivial for the adversary to win after seeing the challenge ciphertext in step 3?  Couldn't the adversary just use PK to encrypt $m_0$ and $m_1$, and see which one matches the challenge ciphertext?
I feel like I'm a key point and would appreciate if someone could clarify what the paper is saying.

The game is not trivial for the adversary to win because the author is suppressing $ENC\hspace{.02 in}$'s randomness, which makes it so for most PKE systems it will be the case that $\; \operatorname{Prob}\left(ENC_{PK}(m) = ENC_{PK}(m)\right)$

is exponentially small, in which case the probability that either $ENC_{PK}(m_{\hspace{.02 in}0})$

or $ENC_{PK}(m_1)$ matches the challenge ciphertext is also exponentially small.

"state" is the contents of $A$'s memory locations during step 3,
when there's just an $A$ rather than an $A1$ and an $A2$.


Why Random Secret Necessary Almost in all digital Signature Algorithms I've read some introduction documents about digital signatures, and all they said is

Signer calculates a hash of data to be signed.
This hash is encrypted with the private key.
Verifier reads the document and calculates hash again and compares it the received hash which is decrypted with a public key of the signer.

Then I've read the implementations like El-Gamal, DSA, and Schnorr.
They all use an additional random secret variable (referred to as $r$ in three algorithms). What's the purpose of it?

ElGamal signature, Schnorr signature, DSA and ECDSA are all based on the same core principle. They all use a group where calculating discrete logarithm is infeasible with a generator $g$ (i.e. $k \mapsto g^k$ is a trapdoor function). A key is a group element: the secret key is an index $x$ and the public key is the corresponding group element $y = g^x$. To sign a message:

Choose an element of the group by its index $k$. $k$ must remain secret forever and must not be reused for another signature.
Calculate a value $r$ which is derived from the group element $g^k$. $k$ must remain secret but $r$ will be public.
Calculate a value $s$ that depends on both $r$ and $k$, as well as the secret key $x$ and the message to sign. (Actually Schnorr is structured differently and the message goes into $r$ instead of $s$, but it's still the same core principle.)
The signature is the pair $(r,s)$.

The verifier uses $r$, $s$ and the public key to calculate two group elements. If $s$ was derived from $r$ using the secret key and the secret index $k$ then the secrets cancel out and the two group elements are identical. Without knowledge of the secrets, it's infeasible to make the two calculations produce the same value.

The nonce $k$ must have two properties: it must not be reused for another signature in the same group, and it must remain secret. If the nonce for a signature is revealed, it's trivial to calculate the secret key from the nonce and the signature. If the same value $k$ is used for two signatures with the same key then their use cancels out and this again reveals the secret key. Even partial information about $k$, or reusing $k$ with different signatures, leaks information that can make it easier to find the secret key(s).

It is not necessary for $k$ to be random, however. It needs to be as hard to find as the secret key, and as unique as the secret key and the message. It's ok for $k$ to depend deterministically on the secret key and the message. For (EC)DSA this is standardized and commonly used. Deterministic (EC)DSA uses the secret key and the message to seed a pseudorandom generator which is used to generate $k$.

The other family of popular signature methods is based on RSA. There are two signature schemes based on RSA: PKCS#1v1.5 and PSS. Both use the RSA trapdoor permutation on an input that contains the message to sign. PKCS#1v1.5 is not randomized at all, and PSS is optionally randomized to generate the padding (the part of the input from the trapdoor function that isn't the message). The random padding in PSS is revealed as part of the signature. Using random padding gives a proof of security that relies on fewer assumptions than what you can get without random padding, but this doesn't translate to any known attack on signatures without random padding. PKCS#1v1.5 signature, which is always deterministic, has no known attacks if implemented correctly.

Encryption requires non-determinism so that, at a minimum, encrypting the same message twice doesn't produce same output. For asymmetric encryption, this is vital since anybody can use the public key to encrypt: if a public-key encryption scheme wasn't randomized then any ciphertext could be broken simply by guessing the plaintext and encrypting it. The non-determinism is equivalent to building in a secret part in every ciphertext (which needs to be done right!). In public-key encryption, the random nonce needs to remain secret as long as the message, but (at least with some schemes such as RSAES-PKCS1v1_5 and RSAES-OAEP) it can be revealed when the message is decrypted.

Signatures don't have the same requirements. They don't intrinsically require non-determinism. A popular type of signature scheme uses a secret nonce, but the important property of this nonce is that it's secret, not that it's non-deterministic.

Deterministic and randomized signature scheme each have their own benefits and weaknesses. Randomized versions make fewer assumptions on the cryptographic primitives, which makes them more robust in case of partial breakage. However they introduce a reliance on the system's random generator, which is often a weak point in practical design. This tends to make the deterministic variant of (EC)DSA preferable in practice. For RSA, the random nature padding of PSS is not critical for security, but its presence protects against bugs in verifiers: the main problem with PKCS#1v1.5 signatures is that some verifiers don't do a thorough job (Bleichenbacher attacks against PKCS#1v1.5 signature — not to be confused with his attacs against PKCS#1v1.5 encryption), and PSS is more robust against such errors.

Using a random value also introduces a potential covert channel (a black box that is supposed to do nothing but sign a message can get some information out to a third party). The deterministic variants of logarithm-based schemes don't solve this since it's impossible to tell how the nonce was generated. Covert channels are rarely a concern however.


How to analyse traces of a hardware AES implementation? I am trying to implement the correlation power analysis attack. I have a hardware AES for which I found a trigger which defines the start of the AES calculations. After that I performed an EM curves acquisition.

It is the first time that I have some traces so I have some questions about :

According to my trace, the x-axis is the time and the y-axis is the energy consumption. Is there any software that helps me to plot my trace more clearly and make them more comprehensive?
It is clear that I have some noise in my trace. So how to avoid that noise? which type of filter must do? Must I use a low pass filter or a high pass filter, I need to see my 10 rounds clearly to analyse? What are the steps that I must take?
Why there are an important  possibility to make our attack in the first and last round of the AES?
Some explanation about CPA:'We can use the Hamming Distance model in our CPA attacks. If we can find a point in the encryption algorithm where the victim changes a variable from x to y, then we can estimate that the power consumption is proportional to Hamming Distance(x, y)'
I really don't understand the relation between the CPA and the hamming distance. Can anybody explain?
Is there any software that helps me to make my CPA, given my curves?

Answer to the 1st and 5th question :

For the CHES 2016 (Cryptographic Hardware and Embedded Systems), a video has been made to explain how to perform a CPA. There is a wiki associated to the video and the code of the attack is available on it.

Answer to the 2nd question :

For a CPA, you don't need to use a filter : increase the number of measure (number of AES that you perform) should be enough to find the key.
Furthemore, you only need to see the round that you attack to find the key.

Answer to the 3rd question :

You can find the answer on the  topic of crypto stack exchange named "What is the difference between perfoming Correlation Power Analysis (CPA) in the first AES round and doing it in the last round?".

Answer to the 4th question :

The Hamming weight model is a basic power model which is based on the assumption that the amount of power consumed is proportional to the number of bits that are logic '1' during an operation. Typically, if you initialize a variable to the value of Sbox[x ^ y], the consumption used will be correlated to the number of bytes set to 1 in this value. For more information about it, see the .pdf available online : "Differential Power Analysis attacks on AES"
from Kevin Meritt.


Benchmark differences between SHA-512 and bcrypt So I recently made a benchmark SHA-512 vs bcrypt with hashcat CUDA.

Here are the results :

bcrypt : bruteforce : ~                              400 H/s
         Wordlist + dive.rule :  ~                   550 H/s

sha512 : bruteforce : ~          870 MH/s ->   870000000 H/s
         Wordlist + dive.rule :  ~ 640 MH/s -> 640000000 H/s

Factor sha512 -> bcrypt : 1:1589473

SHA-512 is a cryptographic hash function right? So why is it so fast?

For example VeraCrypt uses it as KDF .

I am still a beginner so please explain to me in which scenarios SHA-512 is used and in which bcrypt.

SHA-512 is a cryptographic hash while bcrypt is a password hash or PBKDF (password based key derivation function).

SHA-512 has been designed to be fast. You don't want any delays when validating a signature, for instance. There is no reason for generic cryptographic hashes to be slow.

bcrypt on the other hand is a password hash that performs key strengthening on the input. Basically it does this by slowing down the calculation so that attackers will have to spend more resources to find the input by brute forcing or dictionary attacks. The idea is that although the legit users - you in this case - will also be slowed down, they are only slowed down once per password. However the attackers are slowed down for each try. The legit user is of course much more likely to input the right password first.

Furthermore bcrypt also contains a salt as input, which can be used to avert rainbow table attacks.

SHA-512 officially is not a KDF in it's own right, but it is easy to construct one out of a hash function. PBKDF2 for instance is a password hash / password based KDF. It can use any hash function as underlaying primitive. The larger function takes again a salt and a work factor as input / configuration parameters.

However, if you don't need key strengthening - i.e. the input is random enough - then you can also (almost) directly use a hash to derive the symmetric key. This is called a KBKDF (key based key derivation function). The most well known one today is HKDF which is based on HMAC, which in turn is based on a cryptographic hash such as SHA-512.

There is also KDF1 and KDF2 which can simply consist of the input secret followed by a statically counter, which is then hashed. Although it has limitations with regards to the input and output sizes, it is a secure KDF to the current knowledge - assuming that the hash is pseudo random and collision free for small input.

In some scenarios even a direct hash over the input value may suffice (taking the leftmost bits if the hash generates too many). HMAC - as for instance used by TLS - should be preferred though.

From your source (Slashdot):

  For standard containers and other (i.e. non system) partitions, TrueCrypt uses at most 2,000 iterations. What Idrassi did was beef up the transformation process. VeraCrypt uses 327,661 iterations of the PBKDF2-RIPEMD160 algorithm for system partitions, and for standard containers and other partitions it uses 655,331 iterations of RIPEMD160 and 500,000 iterations of SHA-2.

So VeraCrypt - if we may believe the source - uses SHA-512 but only as configuration parameter for PBKDF2, which is a password hash just like bcrypt. So to create a fair test: compare your bcrypt with your current work factor (not present in your question, but important) and PBKDF2 with 500000 iterations. Only then compare the speed differences.


Number of different substitution alphabet ciphers possible with given conditions? If you consider a 26 letter alphabet, and a cipher where 24 of the letters are sent to themselves, and only 2 letters switch, how many different substitution alphabet ciphers are there, and what percentage are they of total possible?

I thought it would be there are $26\cdot25=650$ such possible ciphers, for a percentage of $$\frac{26\cdot25}{26!}\cdot100\approx1.61\cdot10^{-22}\%$$

But it seems there are only $325$ possible ciphers, when switching only two letters, and i dont understand why?

Iterate through the alphabet (using a smaller alphabet is always a good way to start). So you take letter A and you can combine it with letter B..Z. Now if you take B, then you can combine it with letter A and C..Z. But the combination (A,B) is equivalent to (B,A). So you only have C..Z to consider. Thus you would get (n - 1) + (n - 2) + ... pairs, leaving you with 26 * (25 / 2) = 325 combinations.


Simple way to extend AES to 256-bit block size What is the best way to use standard AES with a 128-bit block size to act as a 256-bit block cipher?  I am aware of CMC and EME which seem to serve this purpose, but they seem to be more complicated than necessary for the 256-bit block case.  (I would like to avoid relying on the uniqueness of a nonce.)

Is the following variant of CBC secure?

Let $(P_1, P_2)$ be the two 128-bit blocks of the 256-bit plaintext $P$, and $I$ be the 128-bit (public) IV (which might not be unique).  The secret AES key is $k$.

To encrypt, set $C_0 = E_k(I)$, $C_1 = E_k(P_1 \oplus C_0)$, $C_2 = E_k(P_2 \oplus C_1)$, $C_3 = E_k(P_1 \oplus C_2)$.  The result is $(C_2, C_3)$.

To decrypt, set $C_0 = E_k(I)$, $P_1 = D_k(C_3) \oplus C_2$, $C_1 = E_k(P_1 \oplus C_0)$, $P_2 = D_k(C_2) \oplus C_1$.

Both encryption and decryption require just 4 AES block encryptions/decryptions (just 3 if $I$ can be used as $C_0$ directly).

The key question is whether this is secure even if $I$ may not be unique.  If both $P$ and $P'$ are encrypted using the same value of $I$, an attacker should not be able to determine anything about $P$ and $P'$ other than whether they are equal (in their entirety).  For regular CBC mode, this is not the case, since if $P_1 = P_1'$, then $C_1 = C_1'$.

It turns out that this "mode" is distinguishable with two chosen messages; one in decrypt mode, and one in encrypt mode.

The first query is in decrypt mode, it is of the ciphertext $(C, 0)$ (where $C$ can be any nonzero value), and with an arbitrary IV.

Because of how decrypt works, $P_1$ of the resulting plaintext is $D_k(0) \oplus C$; this gives us the 128 bit value $Z = P_1 \oplus C$ with $E_k(Z) = 0$.

Our second query is in encrypt mode, it is of the plaintext $(Z, Z)$ with $IV=Z$.  If you go through how encryption works, we see that $C_0 = 0$, $C_1=0$, $C_2=0$, $C_3=0$, and so the resulting ciphertext is $(0,0)$.


ElGamal signature scheme: Why is r included in s In the ElGamal signature scheme we calculate a signature for a (hashed) message $m$ as

$r \equiv_p g^k$,

$s \equiv_{p-1} (m - xr) k^{-1}$

and verify it by checking

$g^m \equiv_p y^r r^s$.

Here $r$ is a group element which is in some cases used as an exponent. This is not a problem, as long as the group elements are just natural numbers, but using a different group, this causes complications (like in EC-DSA, where we have to use just one coordinate of $r$ when it ought to be an exponent).

Even though this is admittedly not a big problem, my question is: Why is it even necessary to include $r$ as an exponent in $s$? Would changing the calculation of $s$ to just

$s \equiv_{p-1} (m - x) k^{-1}$

and the verification condition to

$g^m \equiv_p y r^s$

be insecure in some way?
So far I couldn't find a way to forge a signature or extract $x$ or $k$ from this modified scheme.

With your proposed modification of the ElGamal signature scheme you can produce forgeries for arbitrary (hashed) messages $m$.

By looking at the verification equation $$g^m = yr^s$$ you just have to set $r$ to $r=(g^my^{-1})^{s^{-1}}$ (just by rearranging the verification equation) which you can do for any $s$ from $\mathbb{Z}_{p-1}^*$, i.e., every $s$ that has a multiplicative inverse in $\mathbb{Z}_{p-1}$.


Proving uniform output of CSPRNG I have a question concerning the paper by Blum, Blum, and Shub introducing the $x^2 \mod N$ Generator.  It is clear that the outputs of the generator pass statistical tests for randomness: the larger the $N$ value the more uniform the output looks with more iteration. But it is unclear to me how the authors proved the output of the generator is uniformly random.  That is, it is not obvious to me that proving difficulty of, say, determining previous states given a present state implies the output of the generator is uniformly random.

Would anyone be able to walk me through a sketch of the proof showing the output of the generator is uniformly random, and thus that the generator is provably secure?

If the primes $p$ and $q$ are:

appropriately chosen (see abstract of original paper here) and
large enough (use NFS factoring complexity to determine how large they should be)

then to distinguish non uniformity one basically has to factor $N=pq.$ However, as stated by @Maeher in the comments this holds only asymptotically.


Can homomorphic encryption be used to exchange keys? Fully Homomorphic Encryption (FHE) allows computations be done on ciphertexts. Can this technique be used to exchange keys?

For example, Alice and Bob need to agree on a 4-bit secret key. Alice sends Bob 4 different strings, which are ciphertexts for 0001, 0010, 0100, 1000, respectively. Now Bob chooses the secret key 0101. He performs bitwise-or computation on the ciphertexts corresponding to 0100 and 0001, and sends the result back to Alice. Alice deciphers the result and gets 0101.

Would this scheme be secure? (Aside from the fact that secret keys are usually much longer)

In short

It can be secure, but it will be very inefficient.

In detail

Those bit strings 0001, 0010, 0100, 1000, etc are just powers of two if you look them as integers (i.e., $2^0, 2^1, 2^2, 2^3$, etc) and applying logical bitwise or to some of them is equivalent to adding up some of the powers of two.

Therefore, what you have proposed is a scenario where Alice publishes several encryptions of powers of two, $c_i := Enc(2^i)$ and Bob combines them in some random way, that is, Bob chooses $b_i \in \{0,1\}$  and compute
$$c_B := \sum_{i=0}^{n-1} b_i\cdot c_i = Enc\left(\sum_{i=0}^{n-1} b_i\cdot 2^i\right).$$

It is easy to see that if each $b_i$ is chosen uniformly, then the distribution of the value encrypted by $c_B$ is uniform on $\{0, 1, ..., 2^n-1\}$, which is a perfect scenario (the exchanged key is uniform, then, hard to guess).

However, the problem with this approach is that an attacker could look at $c_B$ and all the $c_i$'s and try to figure out the values of $b_i$'s. Notice that if we manage to discover at least one $b_i$, then we know what is the $i$-th bit of the exchanged key. So, we must rule out that possibility.

A standard way of doing it is to use the Leftover Hash Lemma to guarantee that the distribution of $c_B$ is statistically close to the uniform on the set of ciphertexts $\mathcal C$, but it would require $n$ much bigger than the security parameters $\lambda$. It means that Alice would need to publish much more than $\lambda$ ciphertexts, each one having more than $\lambda$ bits, which means publishing much more than $\lambda^2$ bits (likely to be more than $\lambda^3$). And we still have to take into account the time required to encrypt and combine all those values...

Moreover, I don't think that there is another known way of making this key-exchange secure, since the problem of hiding these $b_i$'s is basically the same problem that the homomorphic encryption schemes face when they are turned into public-key schemes, and the solution I always see on the papers is the one I said (using Leftover Hash Lemma).


What are the extended homogeneous coordinates in the EdDSA specification? According to the EdDSA specification from the IETF:

For point addition, the following method is recommended.  A point (x,y) is represented in extended homogeneous coordinates (X, Y, Z, T), with x = X/Z, y = Y/Z, x * y = T/Z

I'm unfamilar with extended homogeneous coordinates, and I'm used to seeing points as simply (x, y).   Can anyone explain where the T and Z variables come from in the specification document?
UPDATE:
I found this answer on Stack Overflow that has some great detail:

Extended homogeneous coordinates are a different form of coordinates that provide particularly fast methods of point addition and point doubling formulas for twisted Edwards curves, introduced in Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, Ed Dawson. Twisted Edwards Curves Revisited, 2008.

$X$ and $Y$ roughly correspond to affine $x$ and $y$, $Z$ comes from regular extended (also called projective) coordinates as a scaling and $T$ is the actually “new” element that contains $X\cdot Y$. In particular, section 3 of the paper by Hisil et al. introduces the extended homogeneous coordinates and how to convert to and from extended homogeneous coordinates.


Can I use ECC for encryption/decryption, just like RSA? I'm familiar with RSA for asymmetric encryption. I also understand it's only supposed to encrypt small amounts of data (smaller than the key) so for encrypting arbitrary data I would typically generate a one-time random key, encrypt just that random key with asymmetric encryption, and then encrypt the actual data using AES with the random key (and then throw away the plaintext key)
Can I also use Elliptic Curve Cryptography for this? And if yes, can I use any common type of curves / keys?
For example, can I create a Ed25519 or Secp256k1 or Secp521r1 keypair, and then encrypt something with the public key so it can only be decrypted with the corresponding private key?
I sometimes read things like 'Ed25519 is only for signatures, not encryption' or 'ECC is only for authentication'.
Suppose I have an RSA keypair MyPrivateRsaKey.pem and MyPublicRsaKey.pem and a small data file secret.txt.I can encrypt secret.txt using MyPublicRsaKey.pem, and then the encrypted data can only be decrypted with MyPrivateRsaKey.pem.
Now if I have a keypair MyPrivateEd25519Key.pem and MyPublicEd25519Key.pem for example, can I do the same? Or am I mistaken and are elliptic curve keys fundamentally unsuitable for this?
P.S. note that for the context of this question, I'm not dealing with key exchange or signatures or certificates or authentication. Just asymmetric encryption+decryption.

This has indeed been answered previously and I'd be comfortable with it being closed as a redirect to prior answers. But just in case:
No, but yes. These are signature schemes, they cannot be used like RSA. The specific thing you're proposing (directly encrypting a tiny amount of data without a hybrid encryption scheme) is not done. Notice that because key sizes for ECC are much smaller than RSA the "tiny amount of data" could only be a few bytes anyway.
However, the thing you'd actually want to do (encrypting arbitrary data) is possible using ECIES, here's a Wikipedia link about this approach.
https://en.wikipedia.org/wiki/Integrated_Encryption_Scheme
Also, if you're serious about using RSA to encrypt data, please stop. Safely doing this is hard in the general case, plus you've got this arbitrary limit on how much data you can encrypt. Use a hybrid scheme (like ECIES) if you want encryption.


How to communicate by email with forward secrecy and deniability? My correspondents and I would like to communicate privately by email. We used to employ PGP but that might have been shooting ourselves in the foot. PGP doesn't have forward secrecy. If any of our private keys are ever compromised (by law, hacking, or rubber hose), then all our past conversations can be immediately decrypted. And our signatures shown in court.
So we switched to instant messenger conversation with Off-the-Record (OTR) messaging because it gives

Encryption
No one else can read your instant messages.
Authentication
You are assured the correspondent is who you think it is.
Deniability
The messages you send do not have digital signatures that are checkable by a third party. Anyone can forge messages after a conversation to make them look like they came from you. However, during a conversation, your correspondent is assured the messages he sees are authentic and unmodified.
Perfect forward secrecy
If you lose control of your private keys, no previous conversation is compromised.

As explained eloquently at http://www.cypherpunks.ca/otr/otr-wpes.pdf
Is there anything like that for email?

OTR can provide forward secrecy because both partners create fresh ephemeral (one-time-use) keys, which are discarded afterwards, so they can't be recovered by later attackers.

The long-term public keys are only used to authenticate them, to avoid any man-in-the-middle attack.

For offline communication like e-mails this is not easily possible, since the receiver can't contribute an ephemeral key, as already mentioned by CodesInChaos.

If you can live without the forward-secrecy (only the other three properties), you can use long-term Diffie-Hellman keys, do an offline DH-exchange with them and derive from the result (preferably with some salt-like entropy input so not each mail has the same) symmetric keys for both encryption and MAC. The receiver then knows that you and her are the only ones which knew the DH result, and thus the encryption and MAC keys, so only one of you both can have sent this. But she also could have created the message herself, so you have deniability, too. Thanks to CodesInChaos for the comment.

If you can beforehand (maybe over an OTR-chat) consent with your partner about a symmetric key, you can simply use symmetric encryption and a MAC in your email, and get the encryption, authentication and deniability (the receiver could have created the same message, as she knew the same key). If both partners delete the symmetric key after the sending/receiving of the message, it is also forward-secret. But it still is not really an offline communication as the online key exchange is needed.

Of course, we could stretch a protocol like OTR over a message exchange by email. But then both mail clients (or some other software which handles the protocol) would have to store crypto status between the individual messages, which also harms the "perfect forward secrecy", since this status could be potentially recovered. (You could switch the key with each message, and discard old ones as soon as you receive the next key from your partner, and send a new message after any important message to limit the time keys have to be hold in storage.)

The paper you linked in section 6 ("EMAIL") mentions this possibility, as well as a "Ring signature", which provides slightly smaller guarantees.


If you SHA something that already has work put into it, is it still safe? For example, let's say I did 1,000,000 rounds of PBKDF2 on some string (along with a high entropy salt).

If I then run the result plus some string through a simple SHA512 hash function, is it still secure due to the amount of work put into it, or has it lost something?

Example:

var x = pbkdf2(someSalt, somePass, 1000000);
var y = sha512(x + someString);

Is y safe?

Theoretically this provides less collision resistance than straight SHA-512 hashing or straight PBKDF2 hashing. The reason is that if you can find a collision in either function, you can either make the input to SHA-512 the same or can (potentially, even though it's practically very hard) exploit the collision in SHA-512.

Practically however, collision resistance stays the same, which is "unbreakable", as we don't know a way to break SHA-512 in that regard, nor do we know how to break the collision resistance of PBKDF2.

As for password-hashing, the application which seems most likely here, the additional hash won't make the construction weaker, as you still have to do the 1M rounds of hashing to get to the relevant SHA-512 input. Note however that using PBKDF2 for password hashing is strongly discouraged in all but the most extreme cases due to much better and stronger alternatives like Argon2 and bcrypt being available.


What's the point of a Meet In The Middle attack using i.e. double AES with throw-away keys? What's the point of a Meet In The Middle attack while using, for example, a double AES encryption and using one time keys?
You can recover the keys for a secret message already known and you can't use those keys to retrieve other secret messages.
So why would an attacker use it?

As mikeazo points out, a meet-in-the-middle (or any other known plaintext attack) against AES is believed to be infeasible; I'll generalize your question to "if we never reuse a key, why do we care about known plaintext attacks?  If the attacker already knew the message, why do we care if he could decrypt it?"

The reason is that the attacker might be able to use that attack even if he has partial information about the plaintext.  For example, suppose that the attacker knew (or guessed) that the text of the message that Alice sent Bob starts off with:

"Hi, Bob!  The password to my bank account is "

In that case, the attacker may be able to use the known partial plaintext to recover the key; if he is able to do that, he can then decrypt the rest of the text, including the bank password.


Key derivation using the main AES encryption key and some plain text? I am using AES 128 bit encryption in java.
I have an encryption key and 10 digit plain text.

I want to derive a key for HMAC using the AES encryption key and the 10 digit plain text. This plain text will remain fixed in my case.

How can I derive key for HMAC using the above ingredients.

To be more precise please refer below diagram:- How can I achieve to get a new key from the respective input.

NIST has defined some key derivation functions, which can be used to derive new key using one of NIST recommended MAC algorithms, AES-CMAC or HMAC. These functions can meet your needs.

The functions are defined in NIST SP 800-108: Recommendation for Key DerivationUsing Pseudorandom Functions.

Because you intent to use AES Encryption Key for encryption using AES algorithm, you need to pick key derivation mechanism that does not use AES algorithm in ways which may conflict with your use of the key. To do this, you may choose to use the functions with HMAC algorithm, for instance with SHA-256 hash function. (Do not choose AES-CMAC.)

When using construct (Counter Mode KDF, Feedback mode KDF or Double-Pipeline KDF) from NIST SP 800-108, the plaintext can be e.g. Label and the AES encryption key needs to be the KI. For instance:

Use KDF in Counter Mode, with

h = the length of HMAC key desired
r = 1
KI = AES encryption key
Label = the 10 digit plain text
Context = empty string or suitable identifier identifying your protocol or key use purpose.

BTW, instead of deriving HMAC key from the AES encryption key, it is more common to use key derivation key to derive all required key material, i.e., to use KDK (Key Derivation Key), which derives enough key material for both the Encryption Key and the HMAC Key. This practice is recommendable because then encryption key is not used for two different purposes: encryption and key derivation. Use of keys for multiple purposes is generally considered back practice as it increases ways possible attacker may try to get information about the key.

I.e. I would recommend you to consider this instead

AES-CTR-KDK(KDK, plaintext-key) = AES-key (first 128-bits) || HMAC-key (last 256-bits).

[These are typical key sizes, customize the key sizes according to your needs.]

Furthermore, when proposing KBKDF (key-based key derivation function) I'm assuming your use of 10 digit plaintext is not used as PIN for authentication purposes. Then be careful, as it might be possible for attacker to brute-force the key space of $10^{10}$.


Clarification of Advantage vs Probability/Success of an Adversary In cryptography, for a polynomial time-bounded adversary $\mathcal{A}$, given a scheme $\Pi$, the success or probability of succeeding $\mathcal{A}$ is the likelihood for $\mathcal{A}$ to break $\Pi$, and its advantage is the absolute value of the difference between its success and a set in stone knowledge. For instance:

If the objective is to prove that $\Pi$ satisfies IND-CPA (indistinguishable chosen-plaintext) security, one would design a game where the objective of $\mathcal{A}$ is to differentiate the result produce by $\Pi$ and a truly random function and outputs its answer as a bit $b^\prime$. The success of $\mathcal{A}$ is $\mathrm{Pr}(b^\prime = b)$, and it advantage is $\mathrm{Adv}_{\mathcal{A},\Pi} =|\mathrm{Pr}(b^\prime = b)-\frac{1}{2}|$. Where $b$ is the bit chosen by the challenge. Here, the advantage is given by subtracting the success with $\frac{1}{2}$, which is the probability of a random guess between $0$ and $1$, the distribution of $b$.

How do you establish the advantage when you have to output the actual result?
For instance, if the game is to compute the discrete logarithm in a group $(\mathbb{G},g,p)$, and we assume that the success for $\mathcal{A}$ is $\mathrm{Pr}(x\in \mathbb{Z}^*_p, y=g^x: x \leftarrow \mathcal{A}(y)) = \lambda$, what is its advantage?

is it simply equal to its success, i.e., $\mathrm{Adv}_{\mathcal{A}} = \mathrm{Pr}(x\in \mathbb{Z}^*_p, y=g^x: x \leftarrow \mathcal{A}(y)) = \lambda$?

or is the advantage the difference between its success and the probability of a successful random guess in the distribution of the output, i.e., $\mathrm{Adv}_{\mathcal{A}} = |\lambda-\frac{1}{\mathrm{order}(\mathbb{G})}|$?

Finally, which concept is better in security proof? computing the advantage or computing the success?
PS: I read the answers to these questions:

What is adversary's advantage in cryptography and why we use it?
Advantage of attacker in CPA secure IBE

But I was not able to get a clear answer. Hence, this new question.

There is nothing special about advantage versus probability of success, and they should be used where it makes sense and improves readability. When considering distinguishing games (like for encryption, PRG, and the like) advantage has the benefit of simplifying notation. Also, it "behaves nicely" in the sense of being able to add advantages and the like (although this should always be checked formally via the distinguishing probability equations). Note that in distinguishing tasks, it is always possible to succeed with probability 1/2. So, it is only interesting to know how much the adversary can succeed beyond 1/2, and this is the advantage. This makes things nice since we can just talk about a negligible or non-negligible advantage.
When considering computational and not distinguishing tasks, advantage no longer makes sense. Here, if the adversary can succeed with non-negligible probability then it's broken. As such, the success probability is all you need to talk about.


Why doesn't TLS provide E2EE? Why doesn't TLS provide end-to-end encryption?

This question is somewhat related to this,  this and this. If you want to talk to someone, say, through facebook, the TLS connection ends in the facebook server and they may be able to read it, before re-encrypting and sending it to the intended recipient. This seems a little off to me. Assuming the only thing facebook needs to forward the message is the metada which is not encrypted anyway, why TLS enables them to decrypt the message?

TLS encrypts a channel, and that channel is between your browser or app and the Facebook server. You do not have a TLS connection to the friend you are sending a message to. There are messaging protocols that do support end-to-end encryption, but Facebook's is not one of them and TLS doesn't really ccome into it.


Does it make sense that a hash is separated by hyphens I'm trying to solve a challenge that is no longer active. I failed it when it was active, and I still can't resolve it. The challenge showed me a hash, and I have no idea what kind it is, and how does it make sense that parts of it are separated by hyphens?
I thought about md5 , is it possible?
14d6532f-aefb-49c7-b418-89ddff7002d9

That's a UUID format. Note that this is a representation of a 128 bit string. Just like "9" is a representation of "1001".
The actual output of the hash is a random looking 128-bit string.
If it is a UUID, it can be different hash functions depending on what version it is.


A5/2 session key derivation Let talk about Implementation and performance analysis of
Barkan, Biham and Keller’s attack on A5/2. In this paper, mentioned that we need to brute force attack on register 4 ($R_4$) to get keystream from below:

$$HP^{-1}C=HP^{-1}K.      \tag{1}$$
Where $HP^{-1}$ is parity check and $C$ is ciphertext and $K$ is keystream.

On the other hand, the equations on the key stream must be adapted into equations on the variables of the $LFSRs$. So we have the following linear
system:

$$Sr=K. \tag{2}$$

where $S$ is multiplication matrix of size $1368*656$ and $K$ is the concatenation of $3$ unknown key streams $k_1$, $k_2$, and $k_3$, and $r$ is the vector of unknowns representing the state of the $LFSRs$.

Where is $R_4$ influence in the first equation?
How we can construct the second equation(Please with details)?

The authors state in 4.3 that the design of the cipher has the following clever feature:

  The dependencies between the LFSRs and the keystream vary greatly with the initial value of $R_4$ and since the variables of $R_4$ play no role in the value of the keystream, so it is not possible to find them.

So, later on they suggest the values of $R_4$ must be bruteforced, as a precomputation.

As for your question 2, you need to plug things in, as in the equations at the end of section  4.3.


Using SHA-256 with different initial hash value FIPS 180-3 defines the initial hash value for SHA-256 as the first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19.  What would be the risks of using a different value (for example: a random salt)?  Conceptually, this would be the same as prepending the message with a block which hashed (using the normal initial hash value) to the specified value.

With the message padding scheme of SHA-2/SHA-256 as it stands (add one 1 bit, a minimal number of 0 bits so that the overall padded message will end on a block boundary, then the original message length over some fixed number of bits), I know no attack enabled by allowing a different IV.

However, allowing an arbitrary IV renders ineffective one of the two redundant safeguards built into SHA-2's padding scheme. If the message length was removed from the above padding scheme, then an adversary having the ability to decide the different IV could do so nefariously; in particular, such that he knows a secret backdoor block $B$ that can be inserted at the beginning of any message, leaving the hash invariant. Proof: one round of SHA-2 transforms the state $S$ according to $S_{j+1}=F(M_j,S_j)\hat+S_j$, where $F$ is a cipher with the (padded) message block $M_j$ used as key, $\hat+$ is addition with some carries suppressed, and $S_0$ is the IV we are discussing. One able to choose the IV could choose it as $F^{-1}(B,0)$, thus such that $F(B,\mathtt{IV})=0$, thus such that $M_0=B\implies S_1=S_0$.


Does DTLS Change_Cipher re-transmission use same epoch as original one or the new one? DTLS endpoints are required to re-transmit the entire flight of handshake messages in case there is a timeout. Before timeout event, the transmit epoch can change at record protocol. Which epoch is used for re-transmission of messages? The old one of the new one?

E.g., during initial handshake, client sends a flight comprising of key_exchange, ChangeCipher & FINISHED messages. The key_exchange, CCS are sent with epoch=0 and FINISHED is sent with epoch=1.

Say ChangeCipher gets lost.

Does the retransmission of full flight happen in epoch-1 (which is latest one)? If this is the case, the peer has no way of decoding the flight.

Or

Does the retransmission of records happen in same epoch as original but new record protocol sequence numbers are used? In this case, handshake protocol needs to pass epoch information to record protocol. Also record protocol is required to maintain multiple transmit epochs.

The handshake protocol retransmits its messages using the same epoch as it used in the first original transmission.

DTLS1.2 RFC6347 section 4.1 hints about it.
However the text to reuse the  same epoch is not explicit.

  ... some care needs to be taken during the handshake to ensure that retransmitted messages use the right epoch and keying material...

For the situation where ChangeCipherSpec gets lost, it cannot be retransmitted in the new epoch. Doing so will lead the ChangeCipherSpec recipient to a situation where it does not have anyway to decrypt it because its own receive side record layer cipher state has not been updated yet with the keys of new epoch.


How can I split a message in parts of similar size or smaller? I have a 130-160 characters message that I need to split in say, 3 parts, and be able to reconstruct it by recovering all 3 parts. I also need that these parts are type-able, meaning that they can't be too long (I mean not much longer than the original message), and they can't contain weird characters.

I tried with Shamir but the results are too long. I used PassGuardian for that.

Any suggestions?

You can also help me with the tags so the right people is able to find this post.

If the requirement is being able to reconstruct a message of $1280=160\cdot 8$ bits from $3$ parts that are among a set of $2^6$ type-able characters (say $10$ digits, $26$ uppercase letters, $26$ lowercase letters, and $2$ other characters, as in Base64), then no cryptography is required. Simply:

split the $1280$ bits of the message into $3$ nearly equaly-sized segments, here of $427$, $427$ and $426$ bits;
append to each segment something allowing to order the $3$ segments and making them a multiple of $6$ bits, e.g. here 00000,00001, 000010; now all messages are $432=72\cdot6$ bits, the two right bits identify the segment number;
encode each segment as $72$ type-able characters, each encoding $6$ bits.

Decoding, identifying and pasting together the segments is easy and left as an exercise to the reader.

If there is the additional requirement that knowledge of $2$ of the $3$ encoded segments should give no useful information about the message, then we need some cryptography. One simple method, optimized to reduce message expansion, is:

generate a random 128-bit $K$;
encipher the message with key $K$ (say using AES in CTR mode with implicit null IV);
split the enciphered message in $427$, $427$ and $426$ bits data segments as above;
XOR the first $128$ bits of each of the segments, and $K$, forming $K'$;
splits $K'$ into $3$ segments of $42$, $43$, and $43$ bits, append these to the respective data segments, and append the terminations 00000,0001, 00010, forming $3$ segment of $474=79\cdot6$ bits, that can be identified by their rightmost 2 bits;
encode each segment as $79$ characters each encoding $6$ bits.

Decoding is easy:

decode each segment of $79$ characters into $3$ segments of $474$ bits;
identify each segment by its right two bits;
remove the terminations, rebuilt $K'$, remove these;
XOR the first $128$ bits of each of the segments, and $K'$, forming $K$;
rebuilt the enciphered message;
decipher it using $K$.

If any of the encoded segments is missing, $K$ can't be formed again.

Notice that we must expand the message with random data somehow, or loose semantic security.


Where can I learn basic cryptography to know more about passwords and Bitcoin? Basically my knowledge in passwords consist of setting up a Diceware master password back then, and I know hashes are not convertible back to the original password.

Some basic question I want to know the answer for is how can a password be predicted from the hash? Like it can be known how many characters long it is exactly or at least roughly?

At the core of your question is a concept called entropy, which is the amount of uncertainty or unpredictability in a set of data.

In cryptography, entropy is related to probabilities, expressed in terms of powers of 2 (bits.)  For example, a fair coin flip has one bit of entropy: it can be either heads (1) or tails (0).  Flipping four coins gives you one of 16 possible outcomes, so it gives you four bits of entropy.  Rolling one six sided die gives you 2.6 bits of entropy ( $2^{2.6} = 6$ ), and so on.  Each Diceware word generated with 5 dice gives you $2^{(2.6 * 5)} = 2^{13}$, or 13 bits of entropy. Ultimately, the number of bits of entropy represents the number of tries required to test every possible input (also known as a brute force attack.)

Be careful not to confuse a password with a hash of a password.  A SHA-1 hash is 160 bits of data that looks very random, so it might appear to have 160 bits of entropy.  If I were to tell my computer to guess every possible value for a SHA-1 hash ( $2^{160}$ ), it would take longer than forever.  However, a hash algorithm is just a math operation, and produces no entropy on its own; a hash digest value contains no more entropy than the amount of entropy that went into its input.  If I know that a hash value is the result of running a user's password through a SHA-1 algorithm, as an attacker I don't have to try all $2^{160}$ possible values.  I just have to figure out all the values the user might have chosen for a password, and run them through the hash algorithm myself.

Because users are humans, the passwords they choose are frequently based in their native language.  If you're guessing the password of an English speaker, it's common to start with a list of frequently chosen English passwords, such as "god", "admin", "root", "password", "abc123", etc, and then move on to testing all the rest of the words in an English dictionary.  If a dictionary has 200,000 possible words in it, the entropy is only 18 bits; it takes only a few milliseconds for a computer to compute the hashes of 200,000 words and test each to see if it matches a given hash value.

Note that password restrictions can severely reduce the number of words I would have to test.  If a password policy says "passwords must be 6 letters long", then I would first test all six letter dictionary words, which is faster than testing all 200,000 dictionary words.  One thing we assume in all cryptosystems is that the attacker knows everything about the system in use, just not the values of the secrets involved.

Check out the wiki page I linked above for a fairly readable introduction to the concepts of entropy.


RSA Signing: SHA512 incompatible with PSS? I am wrapping the RSACng class from the .Net API.
Whilst unit testing, I run checks against an array of possibilities:

Key Size = 1024, 2048, or 3072 bits
Padding Mode = PKCS v1, or PSS (=PKCS v2?)
Hash Algorithm = SHA-1, SHA256, SHA512

I test for all 3*2*3=18 possible configurations. All tests pass except one combination:

Key size = 1024 bits
Padding Mode = PSS
Hash Algorithm = SHA512

Should this be expected, and how could have I anticipated it? So far, Google has not been my friend.

I also ran a similar batch of unit tests for RSA encryption, and noted a 1024 bits key is incompatible with OAEP-SHA1 and OAEP-SHA256 padding modes. I suspect the key is not large enought, but I was again unable to read some info as to why this was happening.

Yes, this is expected, if the RSASSA-PSS signing code/test uses salt the width of the hash, which is customary. In that case, a $h$-bit hash (with $h$ multiple of 8) requires an RSA public modulus at least $2h+9$ bits.

That's semi-clearly stated in PKCS#1 v2.2, section 9.1.1, condition on enBits, with actual test in step 3. That's because the message representative needs to convey $h$ bits for the message hash, $h$ bits for the salt, $8$ bits for a one-byte identifier¹, and then some.

In PSS, the salt length can be made a parameter, rather than fixed to the hash width as usual. Also, it can optionally be deterministic or fixed, rather than random as usual. But far from all APIs allow that.

There are similar limitations for RSAES-OAEP (without flexibility: the tag's hash always is as wide as the hash, even when the tag is empty/absent, as it often is).

¹ That identifier BCh plays a role when using PSS padding for Rabin signatures or when it is used $r\to\min(r^d\bmod N,N-(r^d\bmod N))$ instead of the textbook RSA private key operation, in order to allow immediate textbook-RSA encryption of the signature with any public key with public modulus of the same size as the one used for signature.


Self Generating key encryption based I was wondering someting :
Doing a XOR with a fixed length key on txt files is not secure.
Basically :  My key is "abc"
         abc|abc|abc|abc|abc|abc
         Thi s i s s ome dat a

THIS, is not safe.
BUT ! I was asking myself : why can't I just make a self generating infinite length key ? The user gives me a password, and I just hasing it to create a key, and whenever the length of the file is bigger then the key, i just re-hash the key itself to create a new one !
Example : Let's take a 192 Bytes message. Use SHA256 hashing algo create 48 Bytes keys.

This solution resolve the ciphere vineger problem.
SO MY QUESTION ( here it is :p ) :
Is this one safe ?
Thanks ! ~Amperclock

Is this one safe

That's always a relative term. One can say for certain that breaking this encryption will be no harder than bruteforcing  the first block of 48 bytes, which is more than doable with a few thousand dollars worth of servers.

Worst case, your first block is made up of a bunch of zeroes, and XOR-ing the key into that will make the first bytes of the ciphertext the key in plaintext, because x ⊕ 0 = x. Hashing those bytes to find the key for the rest of the message is trivial. Likewise, if the format is predictable (most filetypes start with a pre-determined header), recovering the key will be trivial. If any part of the plaintext is known, al subsequent bytes can be recovered this way.

Also, it might be identifiable;
Here's a nice paper on stacking hash functions
It basically states that your scheme is also distinguishable. That is, given an output of the length of SHA265, it is computationally cheap to figure out if it's the hash of the previous hash.

But why roll your own? There are multiple cryptographically secure psuedorandom number generators that have stood years of attack and are probably much faster in performance.


Encrypting files with known headers If I encrypt a file of a known format that has a lengthy header (e.g. an XML Excel file), does that render the encrypted file susceptible to a "known plain text" attack?  In other words, if the first X bytes of the decrypted text are known, does that weaken the encryption for the remaining data?

If a popular encryption scheme is being used: No.

The typical solution is that symmetric stream/block ciphers generate a constant stream of new pseudo-random bits which are merged/XOR'd with the plaintext to produce the ciphertext.

The pseudo-random stream is seeded indirectly by the private key - so as long as the previous or future bits of the PRNG can not be infered from known bits (or infer the PRNG seed for that matter), the cipher is protected from classical known-plaintext attacks.


SPDZ- How to do secure equality comparison The SPDZ paper explains how the SPDZ protocol can be used to find the sum/product of secret values and find the sum/product of a secret and a non-secret value (page 6).

The paper seems to say that from this you can do any other operation. How would you use this to do secure equality comparison between a secret and a non-secret value?

The Array Lookup section of the Bristol SPDZ implementation tutorial shows that their implementation has a way of securely evaluating whether a secret value equals a non-secret value to get a secret result. This is heavily used in Array lookups so one would hope it is an efficient operation. How did they implement this? It doesn't seem to be in the paper.

One way of doing this is to subtract the non-secret value from the secret value (in the secure computation) and to test that the result is 0. There are a number of ways of testing 0; generically, you can generate a shared unknown random value, multiply it with the value you want to test and then open. If the opened value is 0 then you know that you started with 0. Otherwise, it's a random value and reveals nothing (since the shared random value is unknown to all parties and so masks the original value).


Why do authors say conflicting things regarding leak-free stages in their paper? In this paper the last sentence of the first paragraph in the abstract states:

  We assume a (necessary) “leak-free” preprocessing stage.

But then later on in section 1.4 they say

  Another interesting open question is to construct a leakage- resilient
  MPC protocol without assuming any leak-free stages,

Why do they say the leak-free stage is necessary but then later on they say it's an interesting open question ? When they say it's necessary doesn't that imply there is no open question (i.e. not debatable) ?

Is there any research done on leak-free stageS?

I think they are saying assuming leak free is necessary to prove security for their protocol, but it would be really cool (thus an open problem) to design a protocol that can tolerate leaks in any stage.


How to determine which type of crypto is used in a text file? is there a tool or a way to determine which type of crypto is used in this type of text:

U3RlZ2Fub2dyYXBoeSBpcyB0aGUgYXJ0IGFuZCBzY2llbmNlIG9m
IHdyaXRpbmcgaGlkZGVuIG1lc3NhZ2VzIGluIHN1Y2ggYSB3YXkgdGhhdCBubyBvbmV=
LCBhcGFydCBmcm9tIHRoZSBzZW5kZXIgYW5kIGludGVuZGVkIHJlY2lwaWVudCwgc3VzcGU=
Y3RzIHRoZSBleGlzdGVuY2Ugb2YgdGhlIG1lc3M=
YWdlLCBhIGZvcm0gb2Ygc2VjdXJpdHkgdGhyb3VnaCBvYnNjdXJpdHkuIFS=
aGUgd29yZCBzdGVnYW5vZ3JhcGh5IGlzIG9mIEdyZWVrIG9yaWdpbiBhbmQgbWVhbnMgImNvbmNlYW==
bGVkIHdyaXRpbmciIGZyb20gdGhlIEdyZWVrIHdvcmRzIHN0ZWdhbm9zIG1lYW5pbmcgImNv

This obviously is not an encryption but a simple coding with Base64 coding:

The decoded text message is:

  Steganography is the art and science of writing hidden messages in
  such a way that no one, apart from the sender and intended recipient,
  suspects the existence of the message, a form of security through
  obscurity. The word steganography is of Greek origin and means
  "concealed writing" from the Greek words steganos meaning "co...

By googling the whole text message, you would find this page in princeton university.

For decoding the message I used this website apparently there are a lot more ways to do that. You may access to more informations about Base64 in wikipedia.

  Base64 encoding schemes are commonly used when there is a need to encode binary data that needs to be stored and transferred over media that is designed to deal with textual data.

You may recognize Base64 encoded messages by the signs "==" and "=" in ending of the message and all other must be simple alphabets in lower and uppercase, and also numbers.


Threshold cryptosystem with a required share I am trying to find an implementation or variant of a (k, n) threshold cryptosystem (as described here Shamir's Secret Sharing) where we can fix at least one of the k key parts, i.e., instead of ANY k key parts able to decrypt the ciphertext I want at least one of the k key parts to be a certain/fixed key part. So sort of a joint account cheque where k out of n signatures are required but the signature of the accountant should always be there. Any ideas?

Here's an easy way to do it:

Take your secret $S$, and select a random value $R$ of the same size, and compute $T = S \oplus R$
Give the accountant the value $R$
Use a $(k-1, n-1)$ secret sharing method to share $T$ to the other parties.

The accountant plus any set of $k-1$ other parties can reconstruct the secret.  And, any smaller subset cannot get any information on the secret $S$.


Generate 64 bit HMAC Given $plaintext$ and its respective authentication $tag$ which is generated from HMAC-MD5 so that $|tag| = 128$ bits.

If the application is constrained and can send only $64$ bits.
Is it ok, if we xor the first $8$ bytes and second $8$ bytes of the $tag$ in order to generate a total $64$ bit $tag$?

I believe the strengthen is really in the key size not really the output size for somebody to do a brute force. What worse can happen is two different inputs could have same signature if we are doing the above ?

Or does this weaken the strengthen in any way?

Key and tag lengths matter independently. A short tag allows a random guess to be valid more often, but does not help an attacker in finding the key. Rather than XOR, NIST recommends truncation if you need a shorter MAC tag. SP 800-107 (pdf) says to use at least 32 bits:

  When an application truncates the HMAC output to generate a MacTag to a desired length, λ, the λ left-most bits of the HMAC output shall be used as the MacTag. However, the output length, λ, shall be no less than 32 bits.

However, using at least 64 bits is recommended:

  A commonly acceptable length for the MacTag is 64 bits; MacTags with lengths shorter than 64 bits are discouraged.

Other than that, I would not use HMAC-MD5, although it has not been broken. HMAC-SHA256 (or HMAC-SHA512 if that is faster) can be truncated to the same size.


Explaining modulo reduction of curve25519, multiply hi bits with 38 trick? I have learnt that there is a trick where you can speed up the reduction modulo of a point (x-value) in a x25519 curve. Since, it uses the prime number $2^{255} - 19$.

From article:

  Reduction modulo exploits the fact that $2^{255} - 19$. $2^{256} \equiv 38$, so $38*r4$ is added $r0$ and $38*r5$ is added $r1$ and so on.

$r_n$ are registers with size 64 bits.

The problem I have. I don't really understand why this is the case? I wonder if anyone can expand on this?

Let $p = 2^{255} - 19$.

Clearly $p \equiv 0 \pmod p$, meaning $p$ (the modulus) divides $p - 0$ (the two sides of the equation), or equivalently: there exists some integer $k$ such that $p - 0 = k\cdot p$.  (Here $k = 1$.)

So $2^{255} - 19 \equiv 0 \pmod p$, and thus $2^{255} \equiv 19 \pmod p$, meaning there exists some $k$ such that $2^{255} - 19 = k\cdot p$.  (Here, again, $k = 1$.)

If we multiply both sides of the equation by $2$, then we get $2\cdot 2^{255} \equiv 2\cdot 19 \pmod p$, meaning there exists some integer $k$ such that $2\cdot 2^{255} - 2\cdot 19 = k\cdot p$.  (Here $k = 2$.)

But this equation is just $2^{256} \equiv 38 \pmod p$.

Hence, whenever you are doing arithmetic modulo $p$, the quantities $2^{256}$ and $38$ are equivalent.  Since reduction modulo $p$ is a ring homomorphism—that is, $$[(a + b) \bmod p] \equiv [(a \bmod p) + (b \bmod p)] \pmod p,$$ and likewise with multiplication—we can split a number $n$ into the low 256 bits $n_{\mathrm{lo}}$ and the rest $n_{\mathrm{hi}}$ so that $n = n_{\mathrm{lo}} + 2^{256} n_{\mathrm{hi}}$.  Then $$n = n_{\mathrm{lo}} + 2^{256} n_{\mathrm{hi}} \equiv n_{\mathrm{lo}} + 38 n_{\mathrm{hi}} \pmod p.$$


Performance of RSA encryption when the public exponent is 3 and 65537 I wanted to test the performance of RSA encryption when the public exponent was 3 and when it was 65537. Python and M2Crypto library were used to generate keys and do encryption:

key = RSA.gen_key(KEY_SIZE, 65537)
key.public_encrypt(s, RSA.pkcs1_oaep_padding)

where s is a 256-bit string and KEY_SIZE is 2048 bit. For each exponent value, I generated 10000 RSA key pairs and measured the total time they took to encrypt the data string (not included the key-generating time).
I expected that when the public exponent was 3, the running time would be much shorter. However, they took almost the same time (around 27 seconds). I used the time.time() function in Python to measure the running time.
Can anyone explain me the reason?
Updated: I have tested the same operations with PyCrypto, Java (using Bouncy castle library) and C (using OpenSSL library) as well. Here are the results:

PyCrypto: around 5s for both public exponents (PE).
Java: 0.7s for PE = 3 and 1.5s for PE = 65537
C: 0.11s for PE = 3 and 0.27s for PE = 65537

This can be due to various reasons, most likely more than one:

First use of that key initializes some data that takes longer to compute than your actual public key operation (for example, sliding window initialization can take as long as public key operation). Since you only perform one operation per key, this makes this probable.
Your key is so short that it is relative to time other stuff takes (padding, calling the library,various checks on input data, splitting and synchronizing threads [in case of private key operations with Chinese Reminder Theorem]).
Your measurement of time is not precise enough.
Your library uses protection against time side-channel. This is very likely if you are using OpenSSL or other well-studied library, since those are usually secure against most side-channels, but this is usually only done for private key operations.
Other things, like processor not having data in it's cache or branch mis-predictions and background work can also be a factor, especially since you didn't mention that you ran public key computation in loop. For example, if your computer decides to do a thread-switch across your measurement, it can make your result seem lot longer.

Generally, you should execute your computation so long that it actually takes more than few seconds to compute, to avoid small factors that invalidate your results. Also, you should be sure that your library doesn't protect against side-channels in your specific scenario. Only then those measurements can be deemed accurate enough to look deeper.

But this usually isn't padding that is case for time being same. Padding is usually at least 10x faster than public key computation (even when public key operation is hand-optimized SSE2 assembly).

My best guess is that your computation is simply not precise, with both not using accurate timing, and executing computation doesn't take long enough (especially executing public-key operation just once per key isn't enough).

UPDATE

You said that you use python's time.time(). On my machine it has 1ms resolution. Now, since you have to start measurement, then stop it after you ended your encryption (since then you generate new key), this adds to inaccuracy of your measurement. Also, you compared your results to Java and C which both are compiled, and therefore I assume quite a lot faster. It could be that simply everything involved in calling proper functions takes far longer than encryption itself. Adding inaccuracy of time.time() this makes your result of 5sec for both quite probable.
To maximize chance of finding difference, I'd recommend generating one key, then encrypting result multiple times, and timing it all.
Since PyCrypto uses built-in pow, I've checked if results differ, and indeed they do in my very simple test. I've got 832ms for 3 and 5200ms for 65537 (for a fairly small prime and 100000 iterations of pow).


Squaring the coefficients in homomorphic encryption In homomorphic encryption scheme FV, I can multiply an encrypted polynomial for any integer scalar, obtaining the same effect on the plain polynomial. For example, given the plain polynomial $\sum_ia_ix^i$, and its encrypted version $\sum_ib_ix^i$, I could multiply the latter by $c$ and decipher it, to obtain $\sum_i(ca_i)x^i$. Is there a way to do the same with squaring? Can I perform some operation on $\sum_ib_ix^i$ and then decipher it, to get $\sum_ia_i^2x^i$? I already tried with $\sum_ib_i^2x^i$, but it just dosen't work.

About the reasons I'm doing this, it's because I have to use a polynomial activation function in a neural network that uses homomorphic encryption, as explained in this paper

In the Fan-Vercauteren scheme, ciphertexts are composed of 2 polynomials, call them $ct_0$ and $ct_1$.
Although homomorphic addition is really simple (add the two parts independently), the same cannot be said for multiplication. As you noticed, simply multiplying the polynomials won't give you the desired result.
The homomorphic multiplication is composed of 2 steps.
First, you compute an intermediary ciphertext (it is not a real ciphertext because it's composed of 3 elements and not 2):
$$\frac{t}{q}ct_0ct'_0, \;\; \frac{t}{q}(ct_0ct'_1+ct_1ct'_0), \;\; \frac{t}{q}ct_1ct'_1$$ all of them rounded and taken modulo q. This intermediate can be obtained with the SEAL library using Evaluator::multiply.
You can use only this operation and keep your ciphertext size growing, but at some point, it would be more efficient to relinearize.
This operation is used to go back to a ciphertext containing only 2 elements, and can be obtained with the SEAL library using Evaluator::relinearize (it needs a key as a second argument that can be generated using KeyGenerator::generate_evaluation_keys.

Now in order to square an element, you just have to multiply it by itself, but using the correct multiplication operation instead of the naive one.

For more details, you can have a look at this documentation.


what is auth data in AES-GCM I am trying to understand AES-GCM and I do not understand what I should transmit to Auth Data during encryption. What kind of data is that?

The relationship between Auth Data and Plaintext can be compared with that of a network packet header and payload. Modern ciphers provide provision to "authenticate" additional data that's not encrypted so that more robust protocols can be designed. Of course, if you don't have header, you can pass an empty bit string to it.


How fast a middle-class computer can verify assymetric signatures (like ECDSA, RSA etc.)? I have an idea for a peer-to-peer network that will require every connected peer to verify many symmetric signatures per second. In bitcoin, it's the same - every peer independently verifies signatures of every transaction. How many signatures, which sign some message (ECDSA or RSA or whatever is fast and secure) can middle-class computer verify per second (I would like to predict it to know how such network could scale)?

According to the SUPERCOP measurements, an Intel Xeon E3-1220v6 ("Kaby Lake", roughly comparable to a low end 7000 series i7) with 4 cores at 3GHz achieves 311689 cycles for one verification of an P-256 ECDSA signature and 51093 cycles for one verification of an RSA signature (presumably with $e=65537$). This means this machine can verify $4\times 3\cdot10^{9}/311689\approx 38500$ ECDSA signatures per second and $4\times 3\cdot10^{9}/51093\approx234866$ RSA signatures (lower exponents or using Rabin-Williams will be faster) per second.

Ed25519 instead of ECDSA-with-P256 will be about twice as fast. Using Rabin-Williams instead of RSA will be about 3.75x as fast (assuming the speedup from RSA-1024 to RW-1024 is the same for RSA-2048 and RW-2048, as there is no RW-2048 data).

It seems like a speed-up of about 2x can be gained for generic ECDSA using batch-verification. A similar (slightly better speedup?) can be achieved for Ed25519. Using RSA-3072 as opposed to RSA-2048 (to obtain a security level comparable to P-256) will bring a slow-down of 1.66, so 84746 cycles or about 141600 verifications per second.


Cutting down the size of a long blowfish key I am reverse engineering a software that uses blowfish for encryption. The target uses an implementation of blowfish that allows arbitrary positive key length with a key size larger than 56 bytes.

I am looking for a way to cut the key size down to 56 bytes so that I can use a standard library to take care of the encryption instead of using a custom implementation like what the target did.

I started by cutting the key size to 72 bytes as I read here that key bytes beyond the 72th have no effect. This 72-byte worked as a substitute for the original longer key.

Is there a way to cut the key further to 56 bytes?

There is no general way yo use a function implementing Blowfish and enforcing its  maximum 56-byte key size, to emulate a function implementing a variant of Blowfish that does not enforce that limitation (which in practice means it uses up to 72 bytes of key). For most keys over 56 bytes, the plaintext/ciphertext mapping will be different; combining multiple calls won't help.

The only exceptions are keys which after truncation to 72-byte happen to be periodic with a period at most 56-byte. In that case, one can find the period, truncate the key to the period, and pass the truncated key to the function enforcing the maximum 56-byte key size. That works if the function supports the truncated key size, because Blowfish specifies that the key is used cyclically.

Example: key ABCDEFGHIJKLMNOPABCDEFGHIJKLMNOPABCDEFGHIJKLMNOPABCDEFGHIJKLMNOP(64-byte) can be truncated to ABCDEFGHIJKLMNOP (16-byte).

Note: If the minimal period of the actual key truncated to 72-byte is not supported (e.g. because the available Blowfish function enforces that the key length is a multiple of 4 bytes), but some multiple less than 56 is supported, then it is possible to use that multiple. Key ABCDEFGHIJKABCDEFGHIJKABCDEFGHIJKABCDEFGHIJKABCDEFGHIJKABCDEFGHIJKABCDEFxxxx (76-byte with the first 72 of period 11) can be truncated to ABCDEFGHIJKABCDEFGHIJKABCDEFGHIJKABCDEFGHIJK (44-byte).

But in anything like reverse-engineering or cryptanalysis, I can't understand why there would be the need to "use a standard library to take care of the encryption instead of using a custom implementation". There should be the freedom of using a compiled language like C/C++ or Go, and then Blowfish is available in source form, that's little code, zapping its 56-byte limit is trivial, and such custom implementation can give the best speed by cutting down on interface.


Signing Files vs. Signing File Hashes What are the security pitfalls that may occur by signing a list of file hashes, versus signing individual files?

In short, the security trade-offs between:

for file in $FILES; do
    gpg --clearsign $file
done

And:

sha256sum $FILES > signatures
gpg --clearsign signatures

There are a few pitfalls:

File name integrity: signing files one at a time signs the contents of the files.  It (typically) does not protect the file names from tampering.  This could be disastrous in some situations (e.g. an attacker could change blacklist.txt to whitelist.txt).

Set membership integrity: signing individual files does not prevent adding or removing files from the set of files that were transmitted.  In some cases, this is important: if you're transmitting a set of log files, an attacker could selectively remove one that captured incriminating information.  If an attacker has the opportunity to see multiple transmissions, they could add files from an old transmission to the new transmission (essentially a variant on replay attacks).  The files would still have valid signatures individually, so the additions would not be detected.  If you're transmitting a set of user accounts (one per file), an attacker could revert their account to an earlier state (e.g. back to having admin status).

I recommend protecting the transmission as a whole instead of part-by-part, if possible.  The easiest way of doing this is usually to create a tarball or zip file and sign the entire archive.  Signing a list of file hashes is also adequate, but take care when coding the verification mechanism.


How do you break encryption on a message? This may seem like a simple question, but I have just started studying cryptography and I can't seem to find any information on this at all. I am trying to write a "simple" encrypted messenger using Java's Cryptography Architecture and Extensions, and I have been studying pentesting on the side, and I was wondering if there was a way that I could test the security of a message I encrypted using any tools (more specifically in Kali.)

This has led me to a more general question that I cannot seem to find an answer to. Google seems to be awash with news about PGP being broken, or the NSA being able to beat encryption, but how exactly are they doing it? Is the assumption that if you have the message, you would also have the hash of the key used to decrypt it, and to decrypt it involves breaking the hash of the key, or is there anything that actually breaks an encrypted message without the key?

Things like John the Ripper seem to only be able to attack password hashes, and I guess you couldn't brute force an entire encrypted message as that could be tens of thousands of characters with an insane number of possible permutations.
Also, would it change anything if you encrypted the message based on a password instead of a cryptographically secure random number? I wanted to try and set up a little cryptographic challenge where the password could be something short so it would not take long to crack, but I can't find any way of testing different password against an encrypted message - even if you know the encryption algorithm?

It may well be that the answer is not a simple tool, but some incredibly complex set of tasks, but at this point, I would just like to know even the general answer so that I can piece together in my mind how this stuff works! Like I say, it is hard to google as all I can find are answers relating to cracking passwords, which I guess is the "sexier" thing to want to try and do, then to try and decrypt a message!

Thanks in advance,
   Chris

As mentioned this is a very broad question, so please forgive me for not going into any great depth on each point.

There are a few ways to beat encryption. One way is to attack the actual math of the cryptography: for PGP that would involve cracking RSA, which would involve finding a way to solve the discrete log problem. This is the hardest method, but also the most complete. The second way is to attack particular implementations: a specific implementation might leak key information through how long encryption and decryption operations take, might leave secret data in memory for an attacker to find, etc. This is often combined with hacking the target's computer, possibly getting access to the plaintext and circumventing the encryption. "Extraordinary rendition" (kidnapping) and "enhanced interrogation" (torture) are other popular techniques for the US intelligence agencies to break encryption. Just torture the target until they give you a valid key.

There generally isn't a hash of a key transmitted. I'm not sure where you got this idea.

Breaking passwords is easy because people chose bad passwords. It's done via trying the most common passwords and seeing which ones hash to the matched hash. Encrypting things based directly on a password would be a terrible idea, key derivation algorithms are used to try to make breaking passwords harder, but they still rely on the user choosing a good password. Also note that hashes and encryption are very different things. They're both part of cryptography, but they serve very different purposes.

In general, there is no easy way to decrypt an encrypted message, so long as the encryption was done with a good algorithm and good implementation. If there IS an easy way to decrypt an encrypted message then the encryption system used is by definition broken.


Encoding a message to a point of curve y^2=x^3+7 and Bitcoin Core Where should I look at in Bitcoin Core source code to figure out how the signature process transform a message in a curve point?

To sign a transaction (message) in the Bitcoin system, you need to encode the message to a point of the curve $y^2=x^3+7$. I read this Koblitz's paper. There are three encoding schemes. I read this question too.

If I look at in Bitcoin Core source code I can't see any of these encoding schemes, it seems to me that message $M$ is directly encoded in a point ($ \rightarrow \operatorname{hash}(M) $) without check; obviously that is not possible, there is roughly a 50% chance that a random 256 bit string doesn't correspond to a point of the curve. I can't find out how/if the ECDSA library checks if $\operatorname{hash}(M)$ is on the curve or not and especially what it does if the $\operatorname{hash}(M)$ is not on the curve.

What encoding scheme does Bitcoin-ECDSA implement and where is it in the source code?

In ECDSA, the message is never encoded as a point in the elliptic curve. Signing in ECDSA loosely works like this:

$$
\begin{align*}
k &= \text{random}(0, n) \\
(x, \_) &= k \cdot G \\
r &= x \bmod n \\
s &= k^{-1}(H(m) + r \alpha) \bmod n
\end{align*}
$$

$r$ and $s$ are the signature, and as you can see $H(m)$ is only ever used as an element of the integers modulo $n$, the order of the generator point $G$ (and $\alpha$ is the private key). Therefore, $H(m)$ is never treated as a point, and thus never needs to be encoded into one.


Construct an encryption algorithm using hash function We know that Cryptographic hash function is generally a one-way function where we can't retrieve the original message. On the other hand, encryption is a two-way-function where we get the original message from the encrypted message or vice versa. So, in a normal sense, we can't use hash function to construct an encryption algorithm.

What I want to know is, if it’s theoretically possible to somehow create an encryption algorithm using a hash function, or if any encryption algorithm uses hash function in any part of their algorithm?

Theoretically, there are several ways to turn a hash function into an encryption system. However, the Devil is in the details. A cryptographic hash function is a function which is resistant to preimages, second preimages, and collisions. As far as I know, it has not been proven that these conditions are sufficient to build a stream cipher. In fact, what we want is a random oracle (there are subtleties with regards to definition, that I will not detail here).

We have no proof that cryptographic functions really exist. We also have no proof that random oracles really exist. And we do not know how to build a random oracle out of a cryptographic hash function. We do know how to build a secure hash function out of a random oracle. However, we also have strong indications that random oracles cannot actually exist, at least in a general sense. Basically we grope in the dark: we have candidates like SHA-256, which appear to be "quite strong" as hash function, and also are reasonably oraclish as far as we known. In fact, the length extension attack is proof enough that SHA-256 is not a random oracle, but this can be fixed by using SHA-256 on fixed-length inputs, or by invoking it as part of more convoluted structures like HMAC.

In any case, if you have a hash-function-with-oracle-powers, then it is rather easy to generate a pseudo random stream from a secret key, by hashing K||n where K is the secret key and n is a counter. By XORing this key-dependent pseudo-random stream with the data to encrypt, you have a stream cipher.

To make a block cipher, you can use a Feistel network where your hash function is used as "confusion function" for each round, although there again there are details (you must inject round subkeys at that point). The theoretical analysis is due to Luby and Rackoff, back in the 1980s. It can be proven that four rounds are sufficient, subject to some details; e.g. if you are targeting $n$-bit blocks, the proof works up to security level $2^{n/2}$ or so (if I remember it correctly). Variants imply unbalanced networks, which allow for better security at the expense of more rounds (see the Thorp shuffle).

Theoretical upper limit for Feistel schemes is that such a scheme is necessarily an even permutation, so if you have $n$-bit blocks and know the encryption of $2^n-2$ distinct plaintexts, you can guess the encryption of the two plaintext blocks that you don't know with probability $1$, instead of probability $0.5$ for a truly pseudorandom permutation. You would be very hard-pressed to find a practical situation where this point actually matters in any way.

Another theoretical method which does not involve a Feistel scheme at all is described in that article: it is a generic method to turn a "seekable pseudorandom stream" (e.g. the hash-based stream cipher alluded to above) into a generic pseudo-random permutation. The implementation overhead is huge, so nobody does that in practice. It still shows that a PRP can be generically built out of a PRF without the (slight) limitations implied by Feistel networks.


What will happen to existing cyphertext when today's encryption is broken? Even optimistically, I think we can all agree that many encryption algorithms that are widely used in production today will be "broken" sometime in the next decades.

With "broken", I mean that (probably because of quantum computing but maybe because of some black swan) it will be possible to decrypt ciphertext that is generated through those algorithms with a substantially lower effort as opposed to today. And over time, this "attack cost" will only decrease.

Again, no doom scenarios, I am optimistic. Let's assume that every system that uses cryptography will upgrade/switch to "quantum computing proof" cryptography before it becomes reasonably easy to break today's encryption.

However, even in this scenario, can we agree that all "old" ciphertext (that is being generated in PRD all over the world as we speak) will be easily breakable ? Again: "sometime in the next DECADES" ...

If we can agree on this, let's discuss the implications. I list some things that I can think of. Please comment, prove me wrong, add, ...

Encrypted e-mails, Whatsapp/Telegram/... messages, ... that are stored on any server or on any device in general (e.g. a mobile phone confiscated by police) will be easily decryptable. Idem for encrypted files on servers or any devices.
TOR traffic will become as crystal-clear as unencrypted direct traffic. Let's assume a TOR entry node logs everything. Once the encryption attack cost is low enough, those logs can be decrypted and they would show for example: "ip address 1.2.3.4 sent me a request at 1:01 AM May 12th to visit website X through TOR path A B C".
Idem for VPN's. Or for "VPN over TOR" or "TOR over VPN".
Also ISPs who keep logs can dig into all that happened in the past. Idem for example for public wifi hotspots who keep logs (or any "proxy" between the users' device and the ISP).
Passwords / secret keys can be "sniffed" from logs.
Payments through cryptocurrencies that promise anonymity (like Monero) will become just as crystal-clear as payments in non-anonymous currencies like Bitcoin.
Again, we assume that also cryptocurrencies will have switched to quantum computing proof cryptography by when the attack cost became very low, but the history of what happened while using the old algorithms will not magically disappear. Hell, not making it disapear is exactly what blockchain does ....

My guess is that this "event", sometime in the next decades, will unveil proof against a lot of criminals who are safe now thanks to cryptography.
Likewise it will open many doors for people with bad intentions ... Sniffing passwords from "old" logs. Blackmailing people through "old" secrets from "old" ciphertext. Company secrets being stolen. Etc etc.

I am not saying that this is good or bad. I am just saying that imo this will be a very notable event in the next decades and that it's worth discussing about what impact this will have.

Since this is a "question answering" and no discussion website, here you go:
If/when today's widespread encryption algorithms become easily breakable (for example through quantum computing), what will be the implications of the fact that the existing data encrypted through these algorithms becomes public to those in possession of the ciphertext ?

For me it is absolutely not certain at all that many cryptographic primitives will become broken. This was certainly true - to some extend - for older algorithms. But modern cryptography is a different beast than the classical ciphers. We know a lot more about various attack vectors and semantic security. So your initial premise is very speculative.

Symmetric algorithms are already thought to be relative secure against quantum analysis, only halving the key strength (in bits) at best. There are a lot of asymmetric primitives that could be broken using a full fledged quantum computer, but there are certainly post quantum algorithms available. They may not be completely stable or standardized yet, but they are there.

Now you start to talk of an "event" that would happen in the future. Now I speculate that this "event" will never happen. Even if the algorithms we use today get broken, they won't get broken all at once. There are different levels of being "broken" as well, even MD5 - a known broken hash - is still secure in many protocols (password hashing, key derivation, HMAC, you name it).

If ciphertext gets broken it will not happen all at once either. And the impact of the plaintext becoming available will depend completely on the contents of the plaintext. This could be huge for state secrets. However, for the majority of the plaintext: the ciphertext will either not be available to persons that want to abuse the information or the plaintext will have completely lost the importance it once had.

Huge data leaks are happening right now, and the world moves on. We don't need any magic cryptographic breakthrough for that. If you want to know the impact you only need to study what is happening today.


Do the Syllae algorithm and Malaysian cipher from Rubicon exist? In the first episode of a tv series Rubicon (exactly in 482 and 491 lines of an English subtitles) there is mentioned “Syllae algorithm” and “Malaysian cipher”. I could not find any details about these crypto technics.

Are they real? If so where could I find more info about them?

Using a search engine, you would quickly have discovered hints that they’re “home-brew riddles”.
For example:

Travers uncovers the same messages hidden inside the crossword puzzles of several major newspapers. He stumbles upon a series of 27 10-digit numbers, one set for each World Series the Yankees have won, that, by way of historic baseball dates, lead to a group of names. And when he finds a sheet of paper marked with 21 three-letter clusters, it's described as a "simple" code designed to direct the recipient to particular letters in a certain book.

source: “Conspiracy thriller 'Rubicon' challenges viewers”, reviewjournal.com, 1 August 2010

Will's observational gifts begin to decipher clues for him that may uncover a sinister and complex conspiracy.

source: “Will Travers”, rubicon.wikia.com, 1 August 2010

As for your questions:

Are they real?

Obviously, the answer is “yes”… based on the fact that an amatuer/home-brew way exists with which viewers have been challenged. But it is my no means something you’ld expect to be known in the realms of professional cryptography.
So, they are “real” in the sense that they ”exist” as amateur/home-brew puzzles. Yet, there is a huge difference between amateur/home-brew puzzles or “deciphering riddles” and well-vetted, professional cryptography!

If so where could I find more info about them?

We don’t tend to handle amateur/home-brew ciphers at Crypto.SE, and we’re definitely not a valid replacement for your favorite search engine. But using the later, you should be able to find fan-sites and forums providing according information. One of many starting points would be the Rubicon Wiki.
Besides that, something tells me that watching the series might help too… but that might just be me.


Why can't decrypt with OpenSSL if salt changed (for CBC and ECB) A file encrypted with OpenSSL (with, for example, AES 256-bit mode CBC) using the Linux command

openssl enc -aes-256-cbc -in texte -out encrypted_texte -k password

has a salt in the first 16 bytes — with the bytes 8-15 being the salt itself. When the file is decrypted, if the salt is modified, OpenSSL will throw a

bad decrypt 140338977786624:error:0606506D:digital envelope routines:EVP_DecryptFinal_ex:wrong final block length:evp_enc.c:520:

error, while if the file was encrypted in mode CFB doesn't give you that error.

Why does this happen? What is different about CFB so that it does not produce an error when the salt is modified, compared to the other blockcipher modes of encryption which bluntly fail? Has it something to do with the padding (CBC and ECB do use padding)?

Here's an example of what I'm trying to do: With dd, just one byte is changed in the salt. When trying to decrypt, openssl with throw the error.

echo 'spam' > food.txt
openssl enc -aes-256-cbc -in food.txt -out food.enc -k IDONTLIKENOSPAM!
printf '?' | dd of=food.enc bs=1 seek=12 count=1 conv=notrunc &> /dev/null
openssl enc -d -aes-256-cbc -in food.enc -out food.bad -k IDONTLIKENOSPAM!

In your command:

openssl enc -aes-256-cbc -in texte -out encrypted_texte -k password

a password is supplied, which will be used to derive the key and IV for encryption. The salt stored in the file is used in conjunction with your password for this purpose. Therefore when you change the salt, you will get both a different IV and a different key in the decryption process, not just the IV. Then you will get problem decrypting in block modes such as CBC and ECB because the padding in the decrypted plaintext will not be correct (decrypted with a wrong key). While in stream modes like CFB, there is no padding, so modifying the salt won't cause a problem, but you will get wrong plaintext back.

Edit to add: the EVP_BytesToKey() function is used to turn the password and salt into the key and the IV.