Using two elliptic curves to do a range proof Suppose Alice holds a secret value $a$ to which she has publicly committed to using two elliptic curves of distinct order. The curves are $g$ and $g'$ of orders $q$ and $q'$ (with $q < q'$) and generator points $G$ and $G'$. The commitment would be $(A, A')$, where $A = a⋅G$ and $A' = a ⋅ G'$.

I'm wondering if Alice could use a variation on the method described here to prove to a verifier that $A$ and $A'$ are derived from the same $a$ AND that $a < q$. Specifically, I am thinking Alice could do the following:

Pick a large random value $r$ and map it to both curves as $R = r ⋅ G$ and $R' = r ⋅ G'$
Compute $u = H(G, G', A, A', R, R')$, where $H$ is a hash function
Compute $v = r + a ⋅ u$ such that $\frac{v}{u} < q$. This could require iterating through several values of $r$
The proof then is $(R, R', v)$ (the verifier already has $A$ and $A'$)

To check that $A$ and $A'$ are derived from the same $a$ and that $a < q$, the verifier could do the following:

Compute the value of $u$
Check that $\frac{v}{u} < q$
Check that $v ⋅ G = R + u ⋅ A$ and $v ⋅ G' = R' + u ⋅ A'$

Some limitations of this approach are:

To be secure, $a$ must be large (over 224 bits) high-entropy value
To be practical, $a$ would probably need to be smaller than $\frac{q}{2}$. Otherwise, picking $r$ that satisfies the constraints would be difficult

Are there any other limitations?

This answer from Yehuda Lindell refers to an earlier version of this question which started like:

"Suppose I wanted to prove that $0<a<q$ for some larger integer $a$ and a large prime $q$, without revealing the value of $a$. I'm wondering if I could use a variation on the method described here to do that."

I am going to write this as an answer rather than as a comment, since this type of mistake repeats itself multiple times on this forum.

First, specifically to this question: the question doesn't make sense. What are you trying to prove? That there exists an $a<q$; of course there does. That you know an $a<q$; of course you do. These range proofs make sense when you have a commitment to or encryption of $a$ and want to prove that $a<q$. I am not saying this to be critical but to address a mistake that is very common.

Now, to the more general issue, which is the important one. Zero-knowledge proofs only make sense when you have a well-defined statement that you are trying to prove. It is important to write down this statement clearly, and then see if it is trivial. For example, a statement that says "for all primes $q$ there exists an integer $a$ such that $a<q$" is trivial. That is; it always holds (for all primes $q$) and thus there is nothing to prove. Note that there are statements that look less obvious. For example, given a group of order $q$ with generator $g$ and a group element $h$, the statement "there exists a value $x\in\mathbb{Z}_q$ such that $h=g^x$" is also always true, and thus is trivial. This may seem confusing since this is exactly the statement of the Schnorr discrete log proof; I will explain below. Finally, any statement that can be verified in polynomial time does not make sense for zero knowledge (at least as we formulate it) since the verifier can check itself, making it trivial. In short, in order to talk about zero knowledge in a non-trivial way, there needs to be a well formulated NP statement (NP so that the prover can be polynomial time) that cannot always be verified in polynomial time without any additional information.

Having said the above, there is sometimes a need to prove that the prover knows something. For example, for every $g,h$ as above, there always exists some $x$ such that $g^x=h$ but it is not necessarily known (and cannot be found efficiently). Thus, a zero-knowledge proof of knowledge can be used in such circumstances. Another classic example is that I know the value inside a commitment or ciphertext (without revealing it). Here too there should be a clearly formulated NP statement and finding the witness should be something that cannot in general be done in polynomial time.

I hope that this helps...


Block Ciphers / Kerckhoffs Principle I am newbie to the crypto world, but my question is, If block cipher BLOCK satisfies the following relation (where ENC is encrypt and "+" means XOR): For ever pair of blocks of input A and B, ENC(A+B) = ENC(A) + ENC(B).

I was wondering what would be the security of BLOCK? Assuming the key is of fixed size and that you have unfetterd access to the ENC function. In other words, how hard is it to decrypt a given ciphertext without knowing the details of BLOCK.

In other words, how hard is it to decrypt a given ciphertext without knowing the details of BLOCK.

Pretty easy; all you'd need to do is ask for:

ENC(0x000..0001)
ENC(0x000..0002)
ENC(0x000..0004)
ENC(0x000..0008)
ENC(0x000..0010)
...
ENC(0x400..0000)
ENC(0x800..0000)

For an $n$-bit block cipher, that's $n$ queries.

Then, you find the linear combination of the above values that gives you the known value ENC(BLOCK) (for example, by Gaussian Elimination); by the homomorphic property you listed, that immediately gives you the value of BLOCK

This same strategy can be devised as a known ciphertext attack, using $n+\epsilon$ random known plaintexts, that'll allow you to decrypt any ciphertext with high probability.


What is the approximate effort to break one additional round of a primitive? Many of the cryptographic primitives currently in use have a number of their rounds already broken.  Generally and with no particular primitive in mind, what is the scale of the effort to break one more round? Is is anything like $O(n)$, or more like $O(n^{something})$ where $n$ is the number of rounds for any individual primitive? In short, is breaking each additional round as easy or harder than the previous one? Or are there impediments other than simple computational time & effort?

So for example, assume an iterated primitive of $n$ rounds in total, where each round is $r_i$.  I'm asking is it as easy to break $r_{i+1}$ as it was to break $r_{i}$? It seems to me that this relationship should be independent of $n$ itself within the particular primitive. I'm not comparing between primitives.

This question is loosely based on the numbers of broken rounds identified in Origin of values for "security margin"?.

Think of breaking through rounds as doing ballistics tests to see how deep a projectile can get into a defensive barrier. Breaking through the first layer or two is easy, but each subsequent layer becomes increasingly harder to penetrate. It would be impossible to ask exactly how difficult it is without knowing both the projectile and the defensive material. All you can say is that each layer makes it less and less likely that anything will get through. Breaking an iterated cipher is exactly like that, but with more math.

  Generally and with no particular primitive in mind, what is the scale of the effort to break one more round?

There is no way to answer this without knowing the particular primitive you are talking about. In some cases, for a cipher with a small number of very complex rounds, extending an attack to another round may be a truly monumental effort and the discovery may be significant. For a cipher with a huge number of simple rounds, breaking one more may be just a matter of revisiting the original attack. In general, it's easier to extend an attack one more round for ciphers with a large number of simple rounds than with a few complex ones. This is why people tend to refer to broken rounds only in the context of the number of total rounds. Finding an attack that breaks 9 rounds is a big deal for a cipher with 10 rounds, but is not a big deal at all for a cipher with 72 rounds. That's why security margin is given as a percent.

  In short, is breaking each additional round as easy or harder than the previous one?

Each round introduces more confusion and diffusion. With the exception of a few rare types of attacks which do not depend on the number of rounds (like slide attacks), following e.g. a differential trail or linear hull through more rounds may not be possible without using completely new techniques in the attack. In general, each additional round is significantly harder to break than the last.


Could a 2nd EC private key be derived from a public key? I understand that the public key does not expose the private key.  That is not the question.

The question is:  Given a EC public key, can a different, but plausible and functional private key be derived to match the public key?

In other words:

In basic arithmetic, if you know a x b = c, and you know any two variables, then you can calculate the third.  But in ECC, we have a public key q, a well known point G, and a private number d.  The public key is derived from the private key by ECPoint q = CreateBasePointMultiplier().Multiply(parameters.G, d);.  I have to assume Multiply is a special form of multiplication, such that knowing q and G do not result in knowing d.  Maybe it's essentially looping over a finite field many times over, or something like that.  But could a different private key be selected that would result in the same public key?

In other words, specifically, let Alice and Bob both have ECDH keypairs, and exchange public keys.  They each remember the other's public key for later authentication.  When somebody claims to Alice "I am Bob, and here's my public key," then Alice confirms the public key matches what she remembers, and she challenges him, "Ok, prove it. Here is my (Alice) public key.  Use it to derive our shared secret, and HMAC sign the following challenge.  Send me back the result as a challenge response.  If you can do that, you must know your private key corresponding to the exposed public key."  Could Eve capture Bob's public key, then derive some different private key to correspond to it, and then impersonate Bob by saying "I am Bob, and here's my public key."  Even though Eve doesn't have Bob's private key, she's able to produce some other private key that's compatible with Bob's public key?

Given a EC public key, can a different, but plausible and functional private key be derived to match the public key?

No, a public key will correspond to only one private key (with one minor exception, which I will explain below).  With Elliptic Curve systems, the private key is an integer $d$ between 1 and $q$ (the order the generator point $G$), and the public key is most commonly the point $dG$, which defined to be $\underbrace{G + G + ... + G}_\text{d copies}$.

Now, the order of the generator has this property: all multiples less than the order will be distinct.  That is, if we consider the sequence of points $G, 2G, 3G, 4G, ..., (q-1)G, qG$, there will be no duplicates in that sequence.  What this means is that, since a public key occurs somewhere in the sequence, that is the only occurance; there won't be another private key (less than $q$) that will also yield that public key.

Now, the minor exception I mentioned: some elliptic curve systems don't use the full point $dG$ as the public key, sometimes they use only the x-coordinate as the public key.

It turns out, in that case, there is a second private key value that would yield the same public key; the value $q-d$.  There are no others, and that second key turns out to be of no use to an attacker; recovering that value is no easier than recovering the original value of $d$.


Multiplication instead of Key Derivation Function? context
In a one message communication.
We are right after 2 DHKE (instead of one). Both users then have 2 secret numbers, J and K.
question
Is it a risk to replace the use of a Key Derivation Function with a multiplication of the form S=J**K, creating a big number and only use the bits we need to exchange the only message that conversation needs using a xor operation between S and the message?
Thanks
edit:
After generating the arrays of solutions, that idea is definitely BAD for even values of J and if you don't truncate the first bits. Many numbers have a bias and large contiguous 0s are happening.
Other than that, it really seems random.
edit2:
"Other than that, it really seems random.". Let me rephrase it: if you are not using even values, no bias occur and the generated number really seems random and completely unrelated to previous values.

Is it a risk to replace the use of a pbkdf function with a multiplication of the form S=J**K, creating a big number and only use the bits we need to exchange the only message that conversation needs using a xor operation between S and the message?

One concern I would have would be a possible bias in the bits of $S$; at the very least, the lsbit of $S$ would be 0 with probability 0.75; if you use that to xor with the message, that would mean that the attacker would learn some probabilistic information about that bit.

In addition, if you encrypt the message without doing any sort of integrity protection, that means that the attacker can modify the encrypted message (for example, by flipping bits within the ciphertext) which would yield predictable changes in the decryption of the modified message.

I would suggest that you stick with conventional wisdom when implementing your system; for example, you might want to use:

$$S = \operatorname{SHA-256}( J \mathbin\| K )$$

(possibly along with nonces that are exchanged along with the DH negotiation), and then use $S$ as a key to AES-GCM, which encrypts the actual message.


DES : Is Double Encryption using same key twice equivalent to single DES using different key but of same size If we encrypt a plain text using Double DES but with same key K1,
Can we get the same result as if we would encrypt the plain text using single DES but with different key, say K2.
What I'm asking is can we achieve this for same size of K1 and K2 :
DES(K1,DES(K1,m)) = DES(K2,m)

What would be effective key bits for the first ?
I know this is the case for Mono-Alphabetic shift cipher but I'm confused for DES.
By Key Size I mean like 64 Bit key for which their are 2^55 computations.

Can we get the same result as if we would encrypt the plain text using single DES but with different key, say K2.

It has not been formally proven, but it is extremely plausible to assume that there isn't an equivalent 'double key', that is, for a K1, there isn't a K2 where DES(K1, DES(K1, M)) = DES(K2, M) for all values M (or even a number of values of M.
What has been proven (and is somewhat similar) is that there exist K1, K2 values for which there is no K3 for which DES( K1, DES( K2, M )) = DES( K3, M ) always holds; this is known as the 'DES is not a group' theorem (although it is typically expressed differently).  However, this result does not immediately imply what you are asking about.


How can I create a stream cipher from a block cipher? Assuming $k$ is the key (128 bit) and $m$ is the message (128 bit), how can I use the block cipher $blockenc(k,m)$ to make a stream cipher which can produce quintillion pseudo-random bits?

There are 3 modes of operation which make a stream cipher out of a block cipher:

Cipher Feedback Mode,
Output Feedback Mode, and
Counter Mode.

Taking example of the Counter Mode, this is how encryption and decryption works

$$C_i = P_i \oplus BlockEnc_k(count)\\
P_i = C_i \oplus BlockEnc_k(count)$$
$count$ is increased by 1 with every
 byte of the stream.


How to recognize Authenticated Encryption with Associated Data ciphersuites I have some doubts regarding AEAD ciphersuites and I need some clarification. In the following ciphersuites list:

dhe_rsa_aes_128_sha
dhe_rsa_aes_256_sha
ecdhe_ecdsa_aes_128_gcm_sha256
ecdhe_ecdsa_aes_128_sha
ecdhe_ecdsa_aes_256_gcm_sha384
ecdhe_ecdsa_aes_256_sha
ecdhe_ecdsa_chacha20_poly1305_sha256
ecdhe_rsa_aes_128_gcm_sha256
ecdhe_rsa_aes_128_sha
ecdhe_rsa_aes_256_gcm_sha384
ecdhe_rsa_aes_256_sha
ecdhe_rsa_chacha20_poly1305_sha256
rsa_aes_128_sha
rsa_aes_256_sha
rsa_des_ede3_sha

I have some questions:

Can you help me identify the ciphersuites that provide Authenticate Encryption with Associated Data (AEAD) from those that do not?
Are GCM and Poly1305 ciphers indicates AEAD and the rest of ciphers do not provide it? Can you list all the AEAD algorithms?
Is it always the case that AE ciphersuites must be also Forward Secrecy ciphersuites? or there is no relation that binds the two?
Is Authenticated Encryption (AE) is the same AEAD? or they are different terms?

Can you help me identify the ciphersuites that provide Authenticate
  Encryption with Associated Data (AEAD) from those that do not?

All which explicitely name gcm or chacha20_poly1305 are AEAD ciphersuites. The others use the TLS default which is MAC-then-encrypt with CBC.

  Is it always the case that AE ciphersuites must be also Forward
  Secrecy ciphersuites?

There's no technical reason that forces this to be the case. In fact RFC 5487 defines TLS_PSK_WITH_AES_128_GCM_SHA256 which uses AES-GCM (AEAD) but doesn't offer forward-secrecy. And if you don't accept a PSK suite as an answer here, RFC 5288 defines TLS_RSA_WITH_AES_128_GCM_SHA256, which uses RSA key-transport (and thus offers no forward secrecy).

However, AEAD is what some people call "modern crypto". And as such it is usually paired with other "modern crypto", which does usually mean that you prefer to use forward-secrecy with AEAD suites and only have the non-forward secrecy ones for fallback, after all, clients who implement AES-GCM will also have all the other modern crypto like ECDHE.

  Is Authenticated Encryption (AE) is the same AEAD? or they are
  different terms?

Technically yes. An AE scheme only needs to deliver authenticated encryption of the plaintext, the AEAD scheme also needs to authenticate data as well, so every AEAD scheme is also an AE scheme but not the other way around. Practically however, I am not aware of any scheme that is practically used and is AE but not AEAD (and even then, conversion would be quite simple).


FHE - Brakerski's "Scale Invariant" Scheme I thought the current state of the art for fully homomorphic encryption was Brakerski, Gentry and Vaikuntanathan's scheme (BGV) based on standard/ring LWE employing modulus switching for noise management.

I recently came across a paper by Zvika Brakerski on a "scale invariant" FHE scheme, based on gapSVP, that does not require modulus switching.

Is there an opinion on whether the latter "scale invariant" scheme (I haven't fully read the paper as yet) represents the current state of the art in the FHE world?

I think arguments could be made for either, but I would still call BGV the state of the art for FHE for the following reasons:

A public implementation exists
We have benchmark info
Other protocols have successfully applied it with real world use and analysis here and here (though presumably the scale-invariant system could replace BGV in this work)

All of this could change though. Someone could release an implementation of the cipher and benchmark the benefits. Recent papers are beginning to mention the scale-invariant system. The authors list a number of potential benefits of their system. And a recent blog post details the simplistic nature of the cipher.

There are reasons to believe that the scale-invariant system will not become state of the art though. This system uses rationals (fractional ciphertexts modulo 1) which is different and I'm not sure how that affects implementation. The blog post talks about this and mentions using reals, truncated and that this does not affect correctness. But what about performance?

One popular optimization to FHE ciphers is ciphertext packing (putting multiple plaintexts into a single ciphertext). This allows SIMD like computations on encrypted data. The authors of the paper you mention do not mention packing in $\S$4.2-Implications and Optimizations. Though it appears to be at least an option (see comment by Chris below). Multiplication in the scale-invariant cipher appears to be less efficient too.


mixing round functions and key schedules what is the security of an encryption algorithm that takes the key schedule of algorithm X and the round function of algorithm Y?
should it need a new security proof? or it relies on X and Y's security?

Assuming the 2 algorithms play well together you would end up with a composite of the cryptographic properties of both algorithms - the key schedule would have the properties of X's key schedule and the round function would have the properties of Y's round function. Taking them out of context of their original algorithm won't (usually) change their cryptographic properties.
Many encryption algorithms have been built like this, and the scheme tends to work. That said, you still need to make sure they play well together but that's easier than reviewing an entirely new algorithm.
Update
A list of algorithms using components from other cryptosystems is as follows:

TwoFish

Twofish's distinctive features are the use of pre-computed key-dependent S-boxes, and a relatively complex key schedule. One half of an n-bit key is used as the actual encryption key and the other half of the n-bit key is used to modify the encryption algorithm (key-dependent S-boxes). Twofish borrows some elements from other designs; for example, the pseudo-Hadamard transform[3] (PHT) from the SAFER family of ciphers. Twofish has a Feistel structure like DES. Twofish also employs a Maximum Distance Separable matrix.

SAFER

In cryptography, SAFER (Secure And Fast Encryption Routine) is the name of a family of block ciphers designed primarily by James Massey (one of the designers of IDEA) on behalf of Cylink Corporation. The early SAFER K and SAFER SK designs share the same encryption function, but differ in the number of rounds and the key schedule. More recent versions — SAFER+ and SAFER++ — were submitted as candidates to the AES process and the NESSIE project respectively. All of the algorithms in the SAFER family are unpatented and available for unrestricted use.

RC6

In cryptography, RC6 (Rivest cipher 6) is a symmetric key block cipher derived from RC5. It was designed by Ron Rivest, Matt Robshaw, Ray Sidney, and Yiqun Lisa Yin to meet the requirements of the Advanced Encryption Standard (AES) competition. The algorithm was one of the five finalists, and also was submitted to the NESSIE and CRYPTREC projects. It was a proprietary algorithm, patented by RSA Security.

DEAL

DEAL is a Feistel network which uses DES as the round function. It has a 128-bit block size and a variable key size of either 128, 192, or 256 bits. For key sizes of 128 and 192 bits, the cipher uses 6 rounds, increasing to 8 for the 256-bits size. The scheme has a comparable performance to Triple DES, and was relatively slow compared to many other AES candidates.

CAST-256

CAST-256 uses the same elements as CAST-128, including S-boxes, but is adapted for a block size of 128 bits – twice the size of its 64-bit predecessor. (A similar construction occurred in the evolution of RC5 into RC6). Acceptable key sizes are 128, 160, 192, 224 or 256 bits. CAST-256 is composed of 48 rounds, sometimes described as 12 "quad-rounds", arranged in a generalized Feistel network.

Camellia

Like other AES candidates, E2 operates on blocks of 128 bits, using a key of 128, 192, or 256 bits. It uses a 12-round Feistel network. E2 has an input transformation and output transformation that both use modular multiplication, but the round function itself consists only of XORs and S-box lookups. The single 8×8-bit S-box is constructed from the composition of an affine transformation with the discrete exponentiation x127 over the finite field GF(28). NTT adopted many of E2's special characteristics in Camellia, which has essentially replaced E2.


Understanding simplification steps when solving complicated equations in Galois Field I just encountered a problem when I tried to understand a basepoint conversion from x25519 to ed25519. I can't really wrap my head around how the value of $x$ can be the stated value below? Can someone please, go through the derivation steps of $x$, especially the modular arithmetic part?

From Base point in Ed25519?

  $$ x^2=\frac{1-(4/5)^2}{-1+(121665/121666)\cdot(4/5)^2} \text. $$ Now
  by considering the symmetric representants (that is, from the set
  $\{-(q-1)/2,\dots,(q-1)/2\}$) for the elements of $\mathbb F_q$, we
  can interpret one of the roots of this equation as being positive and
  the other as negative, corresponding to the signedness of their
  symmetric representant. The unique "positive" solution to the
  equation above is precisely
  $15112221349535400772501151409588531511454012693041857206046113283949847762202$.

All these operations are in a finite field, in particular, a prime field with modulus $p = 2^{255}-19$.

So, for example, $4/5$ is not $0.80$, but $4$ times the inverse of $5$ modulo $p$ (i.e. the number that, when multiplied with $5$, results in the remainder $1$ when divided by $p$). In particular, $1/5$ is $11579208923731619542357098500868790785326998466564056403945758400791312963990$ (because that times 5 is equal to 1 when reduced modulo $p$). The same applies to multiplication, addition and so on - everything is modulo $p$.

The final result is correct, as demonstrated by this Sage code:

sage: F = GF(2^255-19)
sage: xx = (F(1)-(F(4)/F(5))^2) / (F(-1) + (F(121665)/F(121666))*(F(4)/F(5))^2)
sage: xx.sqrt(all=True)
[15112221349535400772501151409588531511454012693041857206046113283949847762202,
 42783823269122696939284341094755422415180979639778424813682678720006717057747]


Time complexity to solve Discrete log problem What is the time to complexity to solve
Discrete log  problem now in $Z_p$?

Initially for $n$ bit prime $p$, it was $Exp(n^{1/3})$.

These days the fastest general method to solve discrete logarithms modulo primes is the number field sieve, which has the asymptotic complexity

$$
e^{(1.92+o(1)) (\log p)^{1/3} (\log\log p)^{2/3}}
$$


Example of existentially unforgeable and identity of the signer I am Reading "Security Arguments for Digital Signatures and Blind Signatures
"

  Providing a new message-signature pair. This is called existential
  forgery. In many cases this attack is not dangerous, because the output message is likely to be meaningless. Nevertheless, a signature scheme which is not existentially unforgeable does  not guarantee by  itself the identity  of the signer. For example, it cannot be used to certify randomly looking elements, such as keys.

I am trying find an example of a signature that is not existentially unforgeable and does not guarantee by itself the identity of the signer. Could you help me please?

The goal in this context is to guarantee that given a signature, or a set of signatures, you can confidently determine the public key that made them.

For a trivial example of how this might break down, consider an Ed25519 signature under a public key $A$, namely is a pair $(R, s)$ of curve point $R$ and scalar $s$ such that $[8 s] B = [8] R + [8 H(R, A, m)] A$, where $B$ is the standard base point and $m$ is the message.  If we didn't hash $A$ in with $R$ and $m$, the verification equation would be $[8 s] B = [8] R + [8 H(R, m)] A$.  There are several other public keys under which the same signature satisfies that verification equation: $A' = A + P$ where $P$ is a point of order dividing 8, since $[8] P = \mathcal O$.

That doesn't mean, given a target public key for which you don't know the corresponding scalar, you have any hope of finding a message/signature pair you didn't already have—i.e., it does not violate existential unforgeability.  It just means that you can find another public key under which a message/signature pair you already have is also valid.

One of the basic ideas of Chaum's ecash was to anonymize transactions except fraudulent double-spending transactions, so given one signature neither you nor the bank could determine who made it (but you could still confirm its legitimacy), whereas given two signatures the bank can deanonymize the fraudster.  However, rather than drop spoilers in your lap, I will leave you now to learn the thrilling details from the paper you are no doubt enjoying!


Parallel-resistant proof-of-work scheme? I am looking for a proof-of-work scheme which cannot be effectively parallelized.

For example, in hashcash (and by extension bitcoin) you have some collision-resistant hash function $f()$, a target $T$ and some constant $C$. You obtain the proof of work by running $P=f(C, N)$ for some nonce $N$ which gets incremented with each iteration, untill $P\lt T$ (intuitive definition). The computee then publishes $C, N$ and the verifier verifies the condition by running the hash function once.

This can be easily parallelized by using multiple processors and assigning a portion of $N$ to each one.

I know scrypt aims to be memory-intensive and thus expensive and that bcrypt does something similar.

My approach so far is to use a secondary proof by obtaining $P$ as described above and then running $C' \gets P$ and $P'=f(C',N')$ untill $P'\lt T$ as above. This forces a parallel environment to do the same job as the first scheme, provided the adversary can only afford $max(N)$ processors. It also prohibits the use of single-processor systems (and it's kind of a dumb solution anyway).

I tried to look into literature but unfortunately I'm not mature enough for it. I also understand my question is borderline reference-request but I think I could argue it is acceptable. I leave judgement to you.

To conclude: Is there a proof-of-work scheme based on some hard-to-parallelize (P-complete) problem? Intuition tells me this is a problem based on work (repetition) so it is inherently parallelizable.

What I will describe is "the RSA timelock proof of work protocol",

which does not seem to have a canonical reference.

The server generates large random primes $\hspace{.02 in}p$ and $q$, then calculates

$M \: = \: \hspace{.02 in}p\hspace{-0.02 in}\cdot\hspace{-0.02 in}q \;\;$ and $\;\; L \: = \: \left\lfloor \sqrt{M}\right\rfloor\hspace{-0.02 in}+\hspace{-0.02 in}1 \;\;$ and $\;\; \lambda \: = \: \operatorname{Lcm}(\hspace{.03 in}p\hspace{-0.03 in}-\hspace{-0.04 in}1,\hspace{-0.01 in}q\hspace{-0.03 in}-\hspace{-0.04 in}1) \;\;\;$.

The server publishes $M\hspace{-0.02 in}$, stores $L$ (not necessarily secretly), and keeps $\lambda$ secret.

To give a challenge with difficulty paramter $T$, the server samples $n$ from $\{L,L+1,L+2,L+3,...,(M-L)-2,(M-L)-1,M-L\}$

and then sends $T$ and $n$ to the challenge's recipient.

To solve a challenge, the recipient iterates $\: n\mapsto \operatorname{mod}(n^2\hspace{-0.02 in},\hspace{-0.01 in}M\hspace{.02 in})$

$T$ times and then sends the result to the server.

The client (if honest) will end up with $\:\operatorname{mod}(n\text{^}\hspace{.01 in}(\operatorname{mod}(2^T\hspace{-0.02 in},\lambda)),M\hspace{.02 in})\:$, $\:$ which the server can easily calculate.


Is reusing keys for CBC and CBC-MAC secure when using encrypt-then-MAC? I know reusing keys is a bad idea, especially for CBC and CBC-MAC, but the example for why on Wikipedia seemed to use encrypt-and-MAC. It seems obvious that the last block of encryption will be equal to the MAC when used in this way.

If it's instead used in encrypt-then-MAC, wouldn't that be acceptable? Every bit of the MAC would rely on every bit of the ciphertext, preventing chosen ciphertext attacks.

Is there something I missed here?

No, it is not necessarily secure. Here is a simplified example of why not.

Assume one block zero messages are encrypted without padding. The ciphertext is $I||E(I \oplus 0)$. The MAC value is thus $E(E(I) \oplus E(I)) = E(0)$. So regardless of the IV, the MAC is the same for all such messages. So if you encrypt several zero messages you can leak that fact through the MAC.

When you take padding into account this exact issue is no longer possible, but you should see how it is possible for the MAC and encryption functions to end up using the same values.


Why is this homomorphic encryption correct? In LTV-FHE, section 3.3.2 Formal description, a ciphertext looks like this $c=hs+2e+b = (2g/f)s+2e+b$, where $h = 2g/f$ is the public key, $f$ is the secret key, $g, s$ and $e$ are chosen randomly, and $b$ is the bit to be encrypted.

Following the equation $c = (2g/f)s+2e+b$, the bit $b$ can be obtained easily performing a modulo 2 operation for a ciphertext.

What is the hardness that protects against this simple modulo reduction ?

Note that $h\in R_q$, which hides the parity of $2g/f$ since $q$ is a prime. For example, $h=[2x^2-6x-8]_{17}$. In addition, all the operations (including addition and multiplication) to compute $c$ are done in $R_q$.


hybrid PKE scheme CCA2 insecurity I'm reading "An Efficient CCA2-Secure Variant of the McEliece Cryptosystem in the standard model" by Rastaghi which states:

  As we know, in hybrid PKE schemes XOR alone cannot perfectly hide
  challenge bit to the CCA2 adversary

The author does not define hybrid PKE schemes. What is their definition?
Why is it that XOR alone cannot perfectly hide challenge bit to the CCA2 adversary in hybrid PKE schemes?

The author does not define hybrid PKE schemes. What is their
  definition?

A hybrid public-key encryption scheme is a scheme that uses public-key encryption along with symmetric encryption to gain speed advantages for long messages.

The usual instantiation is to simply encrypt a key for the symmetric scheme and prepend the resulting cipher text. The more modern approach is to choose a random element from the PKE scheme's message space and encrypt it. Then use the hash of said element as the key for the symmetric scheme. This is called the KEM/DEM approach and allows for easier usage of elliptic curves (see ECIES) and code-based crypto (see McBits by Bernstein et al).

  Why is it that XOR alone cannot perfectly hide challenge bit to the CCA2 adversary in hybrid PKE schemes?

This means that the following scheme isn't CCA2 secure. Encrypt by choosing a random key from the PKE's message space use this key as one-time-pad, prepend the random key - encrypted with the PKE. Decrypt by decrypting the random key with the PKE and then use the result to decrypt the data with the OTP. Note: The OTP could be replaced by a stream cipher and the key may also be the result of a key-derivation function.

You see what is missing here? The message is not authenticated.

Say you're given a cipher text $c$ for an unknown message $m$ to be decrypted (if you can you win the CCA2 experiment). Suppose further that $c=(E_{PK}(k),H(k)\oplus m)$ which is standard construction for this. Note that $H(k)=k$ is allowed. Now randomly choose a $r$ of length $||m||$ and compute $c'=(E_{PK}(k),H(k)\oplus m\oplus r)$. Note that $c\neq c'$. Now query the decryption oracle for $c'$ and obtain $m'=m\oplus r$. Now finally reconstruct the message $m=m'\oplus r$ and you have "won" the CCA2 experiment.


How to determine which tweak was used Imagine the following situation:

you have a tweakable block cipher
you have a plain text block
you have a cipher text block
you have the key which was used to encrypt the plain text block

I have these questions to it:

Is there a way to determine the tweak which was used? (a method which is significantly faster than brute forcing)
Is a tweakable cipher considered more secure if there is no fast method to do that?
Is any tweakable block cipher explicitly protected against that?

My concrete case is the following: I wrote an implementation of threefish in python. To check if I did sth wrong, I looked for test vectors in the internet. Every vector worked, except one. The difference between this vector and a previous example on the same page was only the tweak (to show that changing the tweak leads to another cipher block). So I wanted to know if there might be a fast way to calculate the tweak they actually used. Though this is very specific to threefish, I was curious if this might be a general design goal of tweakable ciphers.

This is outside the goal of tweakable block ciphers.  For a counterexample, the following is an example of a secure (if inefficient) tweakable block cipher in the paper introducing tweakable block ciphers as Theorem 1 (p. 35): $$\widetilde E_K(T, M) = E_K(T \oplus E_K(M)),$$ where $E_K(M)$ is a block cipher.  If you know $K$, $M$, and $C = \widetilde E_K(T, M)$, then it is trivial to compute $$T = E_K(M) \oplus {E_K}^{-1}(C).$$

The intentional nonsecrecy of the tweak is made clear in the introduction to the paper: all the uncertainty from the attacker's perspective is contained in the key; the tweak is just an index into a family of independent secret permutations.

It's unlikely that any tweakable block cipher is designed to keep the tweak secret.  You may as well just use a longer key if you're going to choose it unpredictably.  But maybe if you gave more details about your intended application, it might become clearer what you need?


Why does SHA2-224 use different IV's than SHA2-256? Given that it's otherwise just a truncation, I can guess that being able to compute the 224 value from the 256 value is an unwanted property, but that's just speculation.

The $\operatorname{SHA-224}$ is defined in the exact same manner as $\operatorname{SHA-256}$ with different initial values and the digest is obtained truncating the hash value, FIPS PUB 180-4 Page 23.
The different initial value provides domain separation. With domain separation  $$\operatorname{SHA-224}(m) \neq \operatorname{SHA-256}(m)|_{224}$$ where $|_{224}$ is the truncation. If the IV's would be the same then the truncated values would be the same as the initial bits of the full hash, breaking domain separation.
A nice definition of domain separation can be found Hashing to Elliptic Curves, ietf draft

Cryptographic protocols that use random oracles are often analyzed
under the assumption that random oracles answer only queries generated
by that protocol.  In practice, this assumption does not hold if two
protocols query the same random oracle.  Concretely, consider
protocols $P1$ and $P2$ that query random oracle $R$: if $P1$ and $P2$
both query $R$ on the same value $x$, the security analysis of one or
both protocols may be invalidated.
A common approach to addressing this issue is called domain
separation, which allows a single random oracle to simulate multiple,
independent oracles.  This is effected by ensuring that each simulated
oracle sees queries that are distinct from those seen by all other
simulated oracles.  For example, to simulate two oracles $R1$ and $R2$
given a single oracle $R$, one might define
$$R1(x) := R(\text{"R1"} \mathbin\| x)$$    $$R2(x) :=
 R(\text{"R2"} \mathbin\| x)$$
In this example, $\text{"R1"}$ and $\text{"R2"}$ are called domain
separation tags; they ensure that queries to $R1$ and $R2$ cannot
result in identical queries to $R$. Thus, it is safe to treat $R1$ and
$R2$ as independent oracles.

A random oracle is like a kind of hash function and the same concept applies to hash functions.
The initial values required to be a nothing-up-my-sleeve numbers to eliminate the suspicion of hidden properties, though that is psychological.
Similar to $\operatorname{SHA-224}$,

$\operatorname{SHA-384}$ is a truncation of $\operatorname{SHA-512}$ with different initial values.
$\operatorname{SHA-512/256}$ is a truncation of $\operatorname{SHA-512}$ with different initial values.
$\operatorname{SHA-512/224}$ is a truncation of $\operatorname{SHA-512}$ with different initial values.

As a side note; the truncation, naturally, provides resistance to length extension attack.


DTLS 1.2 Key Expansion I am using DTLS 1.2 and my cipher is TLS_ECDHE_WITH_AES_128_GCM_SHA256

According to RFC 5246(RFC 5246 key calculation) i am calculating keys but i can not find the size of these keys in this RFC.

What is the size of following keys.

1- Client_Write_Mac_Key

2- Server_Write_Mac_Key

3- Client_Write_key

4- Server_Write_key

5- Client_Write_IV

6- Server_Write_IV

In the case of a GCM-based ciphersuite, there is no MAC key. If the tool insists on a size, give it 0.

See RFC5246 section 6.2.3.3 (which discusses AEAD ciphers, of which GCM is one example); it explicitly states that, in this case, no MAC key is used.

In addition, the IV sizes are 4 bytes; these 4 bytes are combined with the 8 bytes from the TLS record to form the 12 byte GCM nonce; see RFC5288 second 3.

And, of course, the encryption keys for GCM128 is 16 bytes, yielding a total of:

  1- Client_Write_Mac_Key - 0 bytes

  2- Server_Write_Mac_Key - 0 bytes

  3- Client_Write_key - 16 bytes

  4- Server_Write_key - 16 bytes

  5- Client_Write_IV - 4 bytes

  6- Server_Write_IV - 4 bytes


Which party have to be online during garbled circuit-based MPC protocol? Suppose that Alice, Bob and Charlie want to compute some functions without revealing each input to the function one another.
We can construct the protocols using garbled circuits by multiple communications among the three parties.

Assuming all the parties are semi-honest, which party do we need to let be online in the following setting?

The function $f$ is evaluated by taking the input values from Alice and Bob. After the communication between Alice and Bob, we get some result $a$ in Bob's hand (but Bob does not know exact value of $a$).

The function $g$ is evaluated by taking the input values from Bob and Charlie.
Bob takes as input $a$ to $g$.

Cleary, during the evaluation of $f$, Alice and Bob must be online.
Must Alice be online during the evaluation of $g$?

Alice can construct a garbled circuit for $f$, send to Bob the keys corresponding to her input, and use oblivious transfers to let him learn the keys associated to his input. After that, she can go offline. Bob can then locally compute his output $a$ (meaning, he does not have to be online during this part of the computation). Then, he plays with Charlie the same way Alice played with him: he must be online to send to Charlie a GC, some keys, and execute oblivious transfers. Both can go offline after that, and Charlie can locally compute his output.


Physical Level Encryption What types of algorithms that are capable of signing a message are out there that run on a physical level, e.g. lacking the infrastructure of a standard PC, no memory, processor or motherboard in the traditional sense?

I'm curious whether there are some strong really low level implementations (if these statements don't contradict each other)

It is well known that you can compute any combinatoric function (and hence, any encryption method) with a sufficient number of NAND gates, and so the answer to your question would appear to be "yes, any algorithm is able to run on a "physical level", without a fancy GUI, multitheaded operating system, memory, processor or even a motherboard".

However, I do notice that in the question title, you mention "Encryption", while in the text, you mention "Signing".  Now, we in the cryptographical community use those terms to mean rather different things:

Encryption means a method of transforming the data in such a way that someone without the 'key' cannot read it (but someone with the key can).
Signing means a method of producing a tag with the data and a 'private key', in such a way that someone with the 'public key' can verify that the data and the tag correspond to each other.

In addition, there is a third option, which we don't call signing, but is sometimes confused with it:

A Message Authentication Code (MAC) is a method of producing a tag with the data and a 'key' in such a way that someone else with the 'key' can verify that the data and the tag correspond to each other.

Signatures and MAC do sound similar; the distinction is that with a MAC, the person authenticating the MAC can also generate valid MACs if he wants; with a signature, someone with only the public key cannot generate valid signatures.  This is a distinction that sometimes comes in handy, however known signature methods are considerably more expensive than MACs.  Because of this, we never use a signature unless we need this additional property.

Now that we have defined the terms, we can get back to your question: is your question about encryption, signature generation or MACs?

Well, in practice, it is quite possible to encrypt data or generate MACs without any processor being involved, and we actually sometimes do it in practice.

When we're talking about generating signatures, well, it's more questionable.  Generating a signature is considerably more complex; you could do it without an internal processor (using a pile of NAND gates), however, it's not clear why anyone would choose to.  I don't know the internals of every crypto chip that does signatures (or even the internals of everything I've used), but of the ones that I do know, they all have an internal processor involved (at the very least, to orchestrate the signature process)


Is this block encryption scheme using PCBC for RSA secure? I stumbled over this post, containing code to encrypt larger messages with RSA by splitting them into blocks using PCBC mode
I will copy the relevant part here, but for details see the original posting or this archived copy.

# As indicated in Prologue, this is an implementation of an idea of the present
# author to closely combine asymmetric and symmetric encryptions, which
# presumably is novel.
#
# Encryption will be done with receiver's public key on blocks chained in a way
# analogous to the chaining in common symmetric block encryption processing. The
# chaining value is initialized by a pseudo-random iv. A plaintext block (as a
# big integer resulting from character to integer transformation) is xor-ed with
# the chaining value before being encrypted. The chaining value is then updated
# by xor-ing it with the current plaintext block and the ciphertext block. (In
# distinction to the well-known CBC chaining, we empoly thus PCBC chaining. Note
# that the variable chaining sums up via xoring the values of pp and cc of all
# preceding blocks such that it has a in this context very desirable high error
# propagation property. The iv and the last chaining value obtained are then
# encrypted and appended to ct, the list of the ciphertext blocks, for purposes
# of authentication (integrity check). It is to be particularly remarked that we
# have, as described, integrated certain well-known techniqes commonly employed
# in symmetric block encryption into asymmetric encryption. A normal message is
# processed in this example. In its place there could of course be anything else
# instead, e.g. a secret key for use in a symmetric block cipher (which is how
# RSA is commonly used in other software).
#
# Users employ for encryption and decryption the functions
# rsaencryptplaintexttoct() and rsadecryptcttoplaintext() respectively in case
# the given secret material is in form of a text string, and the functions
# rsaencryptbytearraytoct() and rsadecryptcttobytearray() respectively in case
# the given secret material is in form of a byte sequence.

# Encrypt pt, a list of integers of mb bits (integers in [0, 2**mb-1]) to ct,
# another list of integers, with the public key of the receiver. Note that ct
# returned is a list of integers which may be larger than mb bits, i.e. up to
# receivern-1.
#
# mb: See comments of rsakeygeneration().
#
# (receivere, receivern): The public key of the receiver.

def encrypttoct(pt,mb,receivere,receivern):
assert mb%8 ==0 and mb >= 2048 and 2**mb < receivern
tpmb=2**mb
tpmbn1=tpmb-1
RANDOM=random.SystemRandom()
# A pseudo-random iv is generated to be the initial chaining value.
iv=RANDOM.randint(1,tpmb-1)
chaining=iv
ct=[]
# Each pp is a block of plaintext.
for pp in pt:
    assert pp < tpmb
    u=chaining^pp
# Encrypt with receiver's public key to obtain the ciphertext block.
    cc=pow(u,receivere,receivern)
    ct.append(cc)
# Update the chaining value by xor-ing it with the plaintext block and the
# ciphertext block (limited to mb bits).
    chaining^=pp^(cc&tpmbn1)
# Here at the end of the loop the chaining has its last value.
# Encrypt iv and the last chaining value and put them into ct.
g=pow(iv,receivere,receivern)
h=pow(chaining,receivere,receivern)
ct+=[g,h]
return(ct)

(all rights to this code belong to the original author Mok-Kong Shen

It strangely looks like this is somehow the PCBC mode decryption as described in Wikipedia used for encryption.

Is there any issue resulting from using that with RSA instead of a symmetric cipher?

Assuming that RSA is as secure as BlockCipher XYZ, will this give the same security as PCBC used with XYZ?

Is there any issue resulting from using that with RSA instead of a symmetric cipher?

The difference - with regards to security - between symmetric and asymmetric encryption is that anybody is supposed to have the public key for asymmetric encryption, including the attacker. This has to be taken into account when generating a mode of operation for RSA.

  Assuming that RSA is as secure as BlockCipher XYZ, will this give the same security as PCBC used with XYZ?

Nope. Assume that the first plaintext block is zero. Then the IV (initial chaining value) is encrypted twice in this scheme. As modular exponentiation itself is deterministic, this will result in repetition within the ciphertext. This repetition will show that the plaintext block is zero, thus leaking information to an attacker.

That's a fundamental break in CPA security. There may be other issues, but this is enough to declare the scheme to be broken when used as direct replacement of CBC or PCBC with a symmetric cipher.


Does it matter how the IV and XOR are applied for a single AES-128 block? I want to encrypt 128 bits of data. I understand the problem with ECB, so I generate a 128-bit Initialization Vector to use for encryption and send with the encrypted data. Is there a "best" way to apply this IV?

The Block Cipher Modes of Operation can use the IV in a couple of ways:

The IV is XOR'd with the payload, then this is used as the plaintext for AES, then the AES output is the ciphertext.
The IV is the plaintext for AES, and the output is XOR'd with the payload, then this is the ciphertext.

My system is not concerned with a stream of data, only a single 128-bit block. The receiver can never be expected to have received a prior 128-bit message. So, the modes of operation (CBC, CTR, GCM, etc.) are not fully applicable.

Are each of these functionally the same for that single block? Instead of applying the IV "before" or "after" as above, what if I XOR'd the key with the IV?

Yes there are differences.

The first one is identical to CBC mode encryption. CBC requires an IV that is indistinguishable from random to an adversary.

The second is identical to CTR mode encryption where the IV is the initial counter value; the IV only needs to be unique - but the IV can be randomized, as a 128 bit random number is unlikely to repeat.

You never want to do anything to your key other than using it for your cipher. If you want to create multiple keys, use a Key Based Key Derivation Function such as HKDF rather than XOR.

Note that generally you should try and find the best mode for your operation, and only then generate your IV using the rules for that specific mode.

Authenticated encryption using an AEAD cipher such as AES in GCM mode often makes a lot of sense. GCM for instance generally uses a 96 bit IV / nonce instead of a 128 bit IV.


File Hash of Encrypted File Simple question. I have a source file and I have encrypted it with a certain public key. If I take this exact same source file, encrypt it with the exact same key a few hours later would the file hash of the two encrypted files be the same?

The short answer is NO: you will not obtain identical ciphertexts from the same file encrypted using two different runs of a decent public key file-encryption software; their hash will not coincide.

The longer answer (in theory):

If you use a deterministic public key encryption scheme like textbook RSA, i.e., without randomized padding, then yes.

If you use a secure public key encryption scheme such as RSA OAEP (providing at least IND-CPA security), i.e., encrypting the same message twice with the same public key produces different ciphertexts with overwhelming probability, then no.

However, in the latter case your randomness used for encryption may be computed pseudorandomly from some known value (such as the message itself), as for instance used in message-locked encryption, then the answer turns to yes again.

Hybrid encryption:

If you encrypt larger files (larger then the supported message space of the public key encryption scheme) with a public key encryption scheme you should use hybrid encryption. This is also what will be used by a file-encryption software.

Let us denote the public key as $pk$ and the document as $m$.

Then encrypting the first time results in $(c_1,c_2)=(E_{pk}(k),E_k(m))$ for a random symmetric key $k$.
The second encryption will result in $(c_1',c_2')=(E_{pk}(k'),E_{k'}(m))$.

If you set $k=k'$, i.e., use the same symmetric key, then $c_2=c_2'$ (depending on the mode of operation used for the symmetric cipher you may also require to use the same IV/nonce). Otherwise, if $k\neq k'$ then $c_2\neq c_2'$ with overwhelming probability.

If you use a deterministic public key encryption scheme, then $c_1=c_1'$. If you use a probabilstic (secure) public key encryption scheme, then $c_1\neq c_1'$ with overwhelming probability (as said above, one however can turn probabilistic public key encryption deterministic public key encryption).

Hashing the ciphertext

Now, the first part of the answer only refered to deterministic/probabilistc encryption. It additionally depends on what you see as the hash of the ciphertext, or if you hash the file as it is, and what you want to guarantee in your application and what you want to store.

If you only store the hash of the second component $c_2$ when using hybrid encryption, then the hashes will be identical if you use the same symmetric key (as well as IV/nonce), i.e., $k=k'$, and the document does not change.
But why then use public key encryption? You could encrypt $k$ using $pk$ (store it with the encrypted file) and then decrypt and encrypt the file again and make the comparison.
Alternatively, you could in addition to the file store the encrypted hash of the file.
You could also simply store a hash of the unencrypted file.
You could also simply ignore hashing and compare the encrypted files.


Homomorphic crypto allowing anonymous yes/no votes? I'd need a crypto system allowing online yes/no votes but without revealing who voted what. Is a "partial" homomorphic crypto system what I'm after? Would, for example, Damgård-Jurik work in my case?

In my scheme there would be a server getting the votes and the server shouldn't see who voted what. However we can consider that the server shall not cheat: he won't modify the voting results. But the votes should still be anonymous.

If I need homomorphism, how does it work? Does each voter need to get the encryption from the previous voter? Or can the centralized server receive all the encrypted votes and then "mix" them himself and, once mixed, get the result?

How does it work it there are say, four voters: does the scheme break if only three people vote?

For example I played with the nice simulator here, which expects 8 voters. You can't put seven voters on that page: is this just an implementation detail of that site or is Damgård-Jurik expecting all the votes from a number of voters known beforehand?

Also the page shows who voted what, but it's not clear to me if it's for instructional purposes or if, when the vote counts happens, the votes aren't anonymous anymore.

A homomorphic cryptosystem has some operation $*$ on ciphertexts that correspond to some other operation $\circ$ on plaintexts, that is
$$\mathcal{D}(c_1 * c_2) = \mathcal{D}(c_1) \circ \mathcal{D}(c_2).$$
Typically, the ciphertexts you get by applying $*$ look like ciphertexts that are produced by the encryption algorithm. For Damgård-Jurik, $*$ is multiplication modulo $n^{s+1}$ and $\circ$ is addition modulo $n^s$.

A cryptosystem is secure if the ciphertext does not help you to say anything about the message encrypted.

Suppose you encode "yes" as $1$ and "no" as $0$. The voter will encrypt his encoded vote and send it to the server. Suppose the server receives ciphertexts $c_1, c_2, \dots, c_L$ that are all encryptions of $0$ or $1$. The server can now multiply the ciphertexts to get a single ciphertext, which by the above requirement will satisfy
$$\mathcal{D}\left(\prod_i c_i\right) \equiv \sum_i \mathcal{D}(c_i) = \text{number of "yes" votes.}$$
The server can therefore find the correct election result by decrypting the product ciphertext.

It does not really matter how many ciphertexts are submitted.

If the server is passive (honest-but-curious, will try to break confidentiality without deviating from instructions), the voters are honest and the cryptosystem is secure, the server cannot deduce anything about the votes from the ciphertexts (except the result, of course, since he decrypted a ciphertext containing the result). Damgård-Jurik is generally believed to be secure.

The interesting question is of course what happens when the voters aren't honest or the server tries to cheat. There's a lot of nice cryptography in the answers to those questions.


Proving Sigma Protocol on a Schnorr Protocol Variant Let p, q be chosen as in Schnorr's protocol, and let $g_1, g_2, h$ be elements in $Z^*_P$ of order q.

Assume that the prover P gets as input $w_1,w_2$ where $h = (g_1^{w_1}g_2^{w_2}) \mod q$.

Consider the following protocol:

a) P chooses $r_1,r_2$ at random in $Z_q$ and sends $a = (g_1^{r_1}g_2^{r_2}) \mod q$ to V .

b) V chooses a challenge e at random in $[0,2^t-1]$ and sends it to P.
Here, t is fixed such that $2^t < q$.

c) P sends $z_1 = (r_1 + e*w_1) \mod q$, and $z_2 = (r_2 + e*w_2) \mod q$ to V , who checks that $g_1^{z_1}g_2^{z_2} = (a*h^e) \mod q$, that p and q are prime and that $g_1, g_2$ and h have order q, and accepts iff this is the case.

I need to prove that this is a Sigma-protocol for the relation $h = g_1^{w_1}g_2^{w_2}$
(in the description of the relation, it is understood that it should also be satisfied that p
and q are prime, $w_1,w_2$ are in $Z_q$, and that $g_1, g_2$ and $h$ are in $Z^*_p$ and have order q).

This Sigma protocol is basically a variant of the Schnorr knowledge of exponent protocol but with respect to two different generators. Therefore, also the proof is really similar to the classic one:

Completeness

This is kind of straightforward: $$g_1^{z_1}g_2^{z_2}=g_1^{r_1+ew_1}g_2^{r_2+ew_2}=g_1^{r_1}g_2^{r_2}g_1^{ew_1}g_2^{ew_2}=g_1^{r_1}g_2^{r_2}(g_1^{w_1}g_2^{w_2})^e =ah^e \mod q $$

Special soundness

Let's assume we have two accepting transcripts $(a,e,(z_1,z_2))$ and $(a,e^{'},(z^{'}_1,z^{'}_2))$. A knowledge extractor could extract the witness in the following way. We have that:

$$g_1^{z_1}g_2^{z_2} = ah^e$$ and $$g_1^{z_1^{'}}g_2^{z_2^{'}} = ah^{e^{'}}$$
Let's divide the two equations and we will get: $g_1^{z_1-z_1^{'}}g_2^{z_2-z_2^{'}} = h^{e-e^{'}}$, which yields: $$g_1^{\frac{z_1-z_1^{'}}{e-e^{'}}}g_2^{\frac{z_2-z_2^{'}}{e-e^{'}}} = h=g_1^{w_1}g_2^{w_2}$$.
Therefore the extractor has that $w_1=\frac{z_1-z_1^{'}}{e-e^{'}} \mod q$ and $w_2=\frac{z_2-z_2^{'}}{e-e^{'}} \mod q$ .

Honest-Verifier zero-knowledge (HVZK)

Let's build the simulator given a random $(z_1,z_2)$ and $e$. The first message message $a$ can be obtained by $a=h^{-e}g_1^{z_1}g_2^{z_2} \mod q$.
Clearly, $(a,e,(z_1,z_2))$ have the same distribution as in a real run. Namely, random values
satisfying $g_1^{z_1}g_2^{z_2} = ah^e$.


GCM mode of operation and IV size less 96 bits GCM specification defines the initial counter value $Y_0$ for encryption/decryption operations as follows:
$$
Y_0=\begin{cases}
IV||0^{31}1 &\text{if len}(IV)=96\\
GHASH(H,\{\},IV)& \text{otherwise}
\end{cases}
$$

I don't understand why hashing with $GHASH$ is used for $len(IV)<96$. Suppose I am using 64-bit deterministic IV's; it seems logical to create  128-bit deterministic initial counter value as
$$
Y_0=IV||0^{63}1
$$
I believe it does not contradict GCM specification. Why the specification suggests to use pseudorandomized initial counter value?

If you want to use 64 bit deterministic IV's then you can. The NIST specifications  call this the "deterministic construction" listed in section 8.2.1 of Special Publication 800-38D: Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC.
The "deterministic IV" is then called the "invocation field" of the IV. That leaves you with 32 bits for the "fixed field", for which it is specified that:

Similarly, the entire fixed field may consist of arbitrary bits when there is only one context to identify, such as when a fresh key is limited to a single session of a communications protocol. In this case, if different participants in the session share a common fixed field, then the protocol shall ensure that the invocation fields are distinct for distinct data inputs.
...
The lengths and positions of the fixed field and the invocation field shall be fixed for each supported IV length for the life of the key. In order to promote interoperability for the default IV length of 96 bits, this Recommendation suggests, but does not require, that the leading (i.e., leftmost) 32 bits of the IV hold the fixed field; and that the trailing (i.e., rightmost) 64 bits hold the invocation field.

So as long as you are sure that your deterministic IV is unique, i.e. is a nonce, then you can do with the fixed field whatever you want - as long as both the encrypting party and decryption party use the same value, of course. So you can simply generate an IV consisting of a fixed field consisting of all zero's (a constant of 4 bytes set to zero) and use the nonce for the remaining part.
This way you don't need to use $\mathit{GHASH}$ for calculating $Y_0$ at all, which is more secure and more interoperable as not all GCM implementations may allow IV sizes other than 96 bit.
You would of course end up with $$Y_0=0^{32}\|nonce\|0^{31}1$$ instead of $$Y_0=nonce\|0^{63}1$$ for $Y_0$ but that doesn't matter much. In the resulting scheme, $0^{32}\|nonce$ would be called the IV and the postfixed $0^{31}1$ is generated by the GCM implementation. Of course, if you use $nonce\|0^{32}$ as IV then you would get your construction - and as you can see it is allowed but not recommended by NIST.
If your IV is smaller than 96 bits, you can always simply pad until you've got 96 bits; as long as the IV is unique, there is no problem.


Do parts of a hash carry the properties of the entire hash? When I need to generate unique id's based on some information hashing is typical choice. However, sometimes that id needs to be of a particular size.  I've seen a lot of schemes (HMAC-MD5-96 in SSH, CGA in SeND for IPv6) that use a portion of a hash, so I'm thinking it might be alright to use it that way.

Which properties of a hash are preserved and which do not apply anymore?

Obviously, with less bits, the chance of collision goes up, but can I still rely on the partial hash for uniform character distribution?  What about the avalanche property?  I'm guessing that if a hash modifies the entire hash upon the smallest change to the input, that would imply that a portion of that hash would be equally well changed.  Am I thinking about this correctly?

Also, would these behaviors be different for different hashing algorithms?

Yes, starting from a appropriately good hash or MAC, removing output bits demonstrably does not weaken it beyond the limit imposed by the number of remaining bits, with regards to collision-resistance and preimage-resistance, and other useful properties (such as impossibility to guess anything on the output without knowledge of the input). Put simply, if a standard hash is entirely unbroken, its restriction is unbroken.

More precisely, one appropriately good condition is secure in the Random Oracle Model. For a MAC, it is also enough that without the key, no attacker could harness enough computing power to distinguish the function from a random function with odds better than 50%, given access to an unlimited supply of $(input,output)$ pairs with $input$ iteratively chosen. For a Merkle–Damgård hash like $SHA256$ there are additional technicalities [we replace the key with the constants in the definition of the hash, and posit that they have been chosen at random; also we must make an exception for the length-extension property: from the length of a message $M$, it is trivial to construct extensions $E$ so that $H(M||E)$ is efficiently computed from $H(M)$ without knowledge of $M$].

Proof: If a function is secure in the Random Oracle Model or/and computationally indistinguishable from a random function, then a restriction with less output bit is also secure in the Random Oracle Model or/and computationally indistinguishable, because removing bits deprives an attacker of information and can only increase the difficulty of a distinguisher. Being secure in the Random Oracle Model or/and computationally indistinguishable implies collision-resistance and preimage-resistance within the limits of the number of bits in the output, both for the original function and its restriction.

It is not appropriately good that breaking collision-resistance or/and preimage-resistance of the original hash or MAC is computationally hard. For example consider $H(M) = C||SHA256(M)$ for some 256-bit constant $C$. This 512-bit hash is at least as collision-resistant and preimage-resistant as $SHA256$, which is rock solid. Yet a restriction to its left 256 bits is the constant $C$, and offers no security at all.


How do you work out the private key in a RSA cryptosystem knowing a certain public key? The public key:

n = 85 and e = 19

I know that n is the product of two prime numbers, now is it right of me to figure them out by process of elimination which I got p or q equals 17 and 5. Or is there a proper method of working this out?

In your case you can factor $N (= 85)$ and use that to compute $\phi(N)$, which in turn allows you to compute $d = e^{-1} = 19^{-1} \text{ mod } \phi(N)$. Factoring $N$ yields $5 * 17 = 85$ which in turn means $\phi(N) = (5-1)(17-1) = 64$. Finally, $d = 27 = 19^{-1} \text{ mod } 64 $.

Note that for most actual instances of RSA $N$ is usually at least 1024 bits, and as such cannot be efficiently factored by pretty much anyone. Hence recovering $d$ from just $(e, N)$ is considered unfeasible. This is critical to the security of RSA. It intuitively makes sense too, if you can recover the private key using only the public key then the private key isn't very private.


Uncompress password protected WinRar file without password I would like to know how to extract contents of the password protected WinRar file without the password.

I have downloaded that WinRar file from a file hosting website and found out that it was password protected after I downloaded it. I would like to know is there any way to “unprotect” a password protected file so I can decompress the contained files.

Brute-force attacks take ages. One thing is that I found out that brute force attacking tries every combination of words from the word-list. Therefore, I would like to know if it is possible to brute force attack the file using individual passwords one-by-one, instead of going through all possible permutations of all the individual passwords contained in my word-list.

Why can't you simply ask the person who made that file to tell you the password?

No one knows how to decode an AES-encrypted file, such as password-protected WinRar files, without knowing the password.

As far as we know, the only way to decode AES-encrypted files is to somehow obtain the right password, and then use that password to decrypt the file.

In the movies, sometimes you see people "cracking" a password.
They try all possibilities for the first letter,
and then when they get the first letter right,
they try all the possibilities for the second letter, etc.
Eventually all the letters fill in, and the then the actor has the whole password.

It doesn't work like the movies with AES. AES passwords are all-or-nothing. If you get all-but-one of the letters right when typing in your password, you get exactly the same "failed" message as if you typed in a completely wrong password.
(It's not possible to distinguish the random-looking gibberish from decoding with an almost-correct key from other random-looking gibberish from decoding with a completely wrong key).
It's not possible to tell if one guess is "closer" to the right password than another guess.

(There are various "timing attacks" that, with some systems, can tell a researcher if one guess is "closer" to the right password than another, but they don't work on AES-encrypted files).

There are various "password unlocker" programs that will try one guess at a time until they stumble on the correct WinRar password.
If the person who made the password-protected WinRar file picked a "strong" password -- for example, a passphrase of 8 words randomly chosen using dice from a short dictionary -- we expect that it will take more than a thousand years to stumble across the correct password.
If that person picked a "very weak" password -- such as a single word in the dictionary, or a single dictionary word followed by a single digit, or a single word repeated 8 times, or a sequence of 5 completely random characters -- we expect that it will take less than a day for that program to run through all those very weak passwords and find the correct one.

EDIT:

According to Wikipedia: WinRAR, the "method of encryption" used by WinRAR is the AES (Advanced Encryption Standard) with a 128-bit key.

I agree with Thomas. It's probably hopeless trying to crack it without knowing anything about the password.
If you do find a way to crack AES, Bruce Schnier, the readers of crypto stackexchange, and every other cryptographer on the planet would be fascinated to find out, especially those cryptographers who work at the SVR, the NSA, and other intelligence agencies.


Encryption using deterministic CSPRNG as secure as CSPRNG As a beginner it seems that a scheme derived from a CSPRNG should be as secure as that CSPRNG. Is this a correct assumption? Are there restrictions or known special cases? A rough outline would be:

Generate an IV using a non-deterministic CSPRNG.
Use that IV to seed a deterministic CSPRNG.
XOR each byte of input with a byte from the d-CSPRNG #2.
Concatenate(IV, output of #3)
Use key to seed a deterministic CSPRNG.
XOR each byte of #4 with a byte from the d-CSPRNG #5

In pseudo-code:

# encrypt
iv = randomBytes(IV_SIZE)
c1 = xorUsingPRNG(plaintext, dCSPRNG(seed = iv))
iv_c1 = iv ++ c1
c2 = xorUsingPRNG(c1, dCSPRNG(seed = key))

# decrypt
iv_c1 = xorUsingPRNG(c2, dCSPRNG(seed = key))
iv = iv_c1[0:IV_SIZE]
c1 = iv_c1[IV_SIZE:]
plaintext = xorUSingPRNG(c1, dCSPRNG(seed = iv))

Both the Key and IV are of reasonable size (meaning they are significantly larger than just a few bits).

Are there any known attacks that would work on such a scheme - under assumption that the CSPRNG used is secure.

If the CSPRNG is secure and produces "random" numbers than the output of (any_data XOR random_numbers) should have the same properties in terms of randomness/distribution for as long as those two are independent.

If the CSPRNG is secure then even if one knows or choses the plaintext it shouldn't be feasible to reconstruct the seed used nor should it be possible to extract the keystream because of the randomization in #3.

Obviously the following doesn't work:

Seed a d-CSPRNG with the key
XOR input with output of d-CSPRNG

because this is trivially broken with known/chosen plaintext attacks.

Your scheme can be easily rewritten to adhere to a more common scheme:

generate a random data key (called "the IV" in your scheme)
use the data key to encrypt a message giving the ciphertext (using a stream cipher)
wrap (encrypt) the data key using a cipher parameterized with the master key and store it with the ciphertext.

And the additional step:

encrypt the ciphertext using a cipher parameterized with the master key as well.

Other than #4 this is a very common construction and known to be secure - given that the parameters are indeed configured / generated correctly.

It is also easy to see that the pass with the master key over the ciphertext is spurious if the previous encryption with the data key is secure. That means that a whole pass of a cipher over the ciphertext is performed for no reason, presuming that the stream cipher using the data key is secure.

Relying on deterministic CSPRNG's is often very dangerous from an implementation perspective. CSPRNG's are generally designed to produce random data. They may automatically reseed at times and the implementation may change between versions. A very good example of this is SHA1PRNG used in Java, which is not well described and had all of the described issues (and more) on Android.

Besides that, CSPRNG's are often designed to be very sturdy - a good stream cipher will generally beat the heck out of a CSPRNG in practice when it comes to generating output. The fact that a stream cipher could be seen as a CSPRNG (with a predetermined seed size and without reseeding) doesn't change that.

Likewise XOR with a static key stream is not a brilliant wrapping mechanism. If any data is leaked the data key (your IV) may be at risk. Theoretically it may be perfectly secure given that the message is randomized, but I'd rather use a wrapping mechanism found in FIPS certified hardware (for instance).

Note that the scheme does not protect the integrity of the ciphertext (nor the wrapped key, but the integrity of the wrapped key can be determined by decrypting integrity protected ciphertext). Generally you should try and use authenticated modes of encryption.


Cracking hashes: With vs without knowing the salts Let's assume the following situation:

The attacker has extracted 1000 password hashes from a website (vuln.com) along with all their usernames and hashing algorithm (assume bcrypt). The only piece of information stopping them from cracking all the hashes is the missing passwords and salts. Assume the salts are all cryptographically random.

What would change if the attacker also has all the salts?

What are the differences between cracking the hashes with and without knowing the salts?

The point of using salt is not that it's secret. In fact, it's usually stored together with the hashed password. The point of using salt is that it's different for each entry. This has a few major benefits:

Two users who use the same password won't have the same hash. Hence an attacker can't see which users share a (presumably weak) password.
In a dictionary attack, the attacker can't use a precomputed table of bcrypt hashes. Instead, they have to compute each hash for each salt anew. In particular, the use of salt is a pretty good defense against attacks using rainbow tables.


RSA: large private exponent often yields large public exponent In this answer to a question about choosing RSA's exponent (whether it is better to choose the private or the public exponent), user @Jus12 stated:

When choosing $d$ first: [...] guarantees with high probability that $e$ will be large, making encryption slow.
When choosing $e$ first: can choose very small or pre-determined value of $e$; [...] guarantees with high-probability that $d$ is large so various attacks still don't work.

I easily understand that a small value for $e$ leads to a large value for $d$, as $e\cdot d\geq k\varphi(N)+1$ with $k\in\mathbb Z$ and $N=pq$ being the RSA modulus.
However, I do not see why a large $d$ will probably also result in a large value for $e$. I just see no obvious reason why a large $e$ is more probable than a small one.
I did a quick test for $p=5$ and $q=11$. Considering every $d>\max(p,q)$ as "large" I get the following results:
 d   e
------
13  37
17  33
19  19
21  21
29  29
31  31
33  17
37  13
39  39
------
23   7
27   3

In this case, large $e$'s are more than four times more frequent than small ones. But why is this?

For any integer $k>1$, the function $F$ onto $\Bbb Z^*_k$ (the subet of integers in $[0,k)$ that are coprime with $k$ ) defined by $x\mapsto x^{-1}\bmod k$ is a permutation of $\Bbb Z^*_k$.

For any finite set $\Bbb S$ and any permutation $F$ of $\Bbb S$, if $x$ is uniformly random on $\Bbb S$ then $F(x)$ is uniformly random on $\Bbb S$.

It follows that if we choose $d$ uniformly randomly in $\Bbb Z^*_{\varphi(N)}$ (which is a fair model of choosing a large random $d$ ), and compute $e=d^{-1}\bmod\varphi(N)$, then the resulting $e$ is uniformly random on $\Bbb Z^*_{\varphi(N)}$. The average of $e$ is going to be about $\varphi(N)/2$, thus not "small" in the sense that has in RSA for "small $e$".

In an RSA context, $\log_2(N)\approx\log_2(\varphi(N))$. If $N$ is $n$-bit, a random element of $\Bbb Z^*_{\varphi(N)}$ is going to be $k$-bit or less with probability less than $2^{k-n+1}$, thus very seldom "small" (e.g. for 2048-bit $N$, 128-bit or less with probability $2^{-1919}$ ). That applies to $e$ for a random $d$ (large or not).

Summary: Choosing $d$ at random and computing $e$ from that gives overwhelming assurance that $e$ is not small. There's no such thing as large $d$ implying large $e$.

Note: the question is correct when stating that choosing $e$ small then $d=e^{-1}\bmod\varphi(N)$ ensures that this $d$ is large. But it is wrong in assuming that a large $d$, or/and a large $e^{-1}\bmod\varphi(N)$, is enough that the attacks alluded to don't work (this is referring in particular to Dan Boneh and Glenn Durfee's Cryptanalysis of RSA with Private Key $d$ Less than $N^{0.292}$, in proceedings of Eurocrypt 1999).

For example, we could chose $r$ a random prime of $\frac27\log_2N$ bits, then $e=(\varphi(N)/2+r)^{-1}\bmod\varphi(N)$, then $d=e^{-1}\bmod\varphi(N)$. That $d$ is $\varphi(N)/2+r$, thus about 1 bit less than $N$, thus large. However $r$ is another working $d$, and is consistently small enough to allow the attack.

What matters to prevent the attack is that there exists no small positive working $d$, in other words that $e^{-1}\bmod\lambda(N)$ is not small, where $\lambda(N)$ is the the Carmichael function, with $\lambda(N)=\varphi(N)/\gcd(p-1,q-1)$ when $N$ is the product of two distinct primes $p$ and $q$. That is insured when $e$ is small and the factors of $N$ chosen randomly and mostly independently, making it unlikely that $\gcd(p-1,q-1)$ is unduly large.


What does it means the security parameter K for cryptographic signatures schemes Cryptographic schemes claim to use a security parameter K for deriving signing key and verification key. What does this parameter signify ? how can be chosen?

The security parameter (usually denoted $k,\lambda$ or $\kappa$) is the input to the algorithms of a cryptosystem against which we measure security. That is it should have no effect on correctness of the scheme but only its security against attacks.

Formally the only requirement for this parameter is that attacks grow in time super-polynomial in this parameter and the time for legitimate applications of the scheme grows polynomially in this parameter.

Practically one also often encounters security parameters to make comparisons between parameter sets across schemes. For example a 384-bit elliptic curve has 192-bit security, AES-192 has 192-bit security and 3072-bit RSA has 128 bit security. So if you are asked for a security parameter independent of the scheme it usually is the "x-bit security" parameter, but when asked for a concrete scheme it usually is the "x-bit $Scheme" parameter. For all practical purposes a general security level / parameter of 128-bit is sufficient.


Why is RSA encryption key based on modulo $\varphi(n)$ rather than modulo $n$? While calculating RSA encryption key we take modulo $\varphi(n)$ rather than modulo $n$. I can’t understand why it’s done this way.

Firstly, a number theory textbook might well help here. I own An Introduction to the theory of numbers which will give you a grounding in this and many other number theory topics which crop up in crypto. It's not my favourite book notation-wise, but in terms of topics covered it is very thorough.

Now, on to what you need help with. There exists a theorem called the division theorem that says any number $n = pq + r$, with the constraints that $n > q > r \geq 0$. In plain words, any number $n$ may be represented by a quotient $q$ (possibly multiplied by a number $p$) and a remainder $r$. An example would be to say that $13 = 7 + 6$ - you recognise this in that $13/7$ could be written as "$1$ remainder $6$".

Modular arithmetic is related - let's start off with $13 \equiv 6 \mod 7$. Intuitively, modular arithmetic is often explained as "you take the remainder and that is the result" which isn't far from the truth - what we actually say is that $7$ and $13$ are part of the same congruence class - that is, $q$ and $r$ ($7$ and $6$) remain the same and the congruence class is made up of all the $n$ for all the $p$ possible. So for $p=2$, $n = 2*7 + 5 = 19$. So $19\equiv 5 \mod 7$ (feel free to check it!).

So, you're concerned with the use of $\mod \phi(n)$ in RSA - well the expression usually given is $de = 1 \mod \phi(n)$. We can re-write that in division-theorem form as $de = k\phi(n) + 1$ - where $k$ is $p$ from the previous example, but renamed so as not to be confused with the prime $p$ that forms $n$.

Now observe what you may have learnt about exponents - that $x^{a+b} = x^ax^b$ and that $x^{ab} = (x^a)^b)$ If you're not convinced, pick numeric examples. Now, a message $m$ raised to the power $de$ is $m^{de}$ - but we have a different expression for $de$ already - that is - $m^{de} = m^{k\phi(n) + 1}$. This can then be written as $(m^{\phi(n)})^k \times m^1$.

There is a very good reason for this form being desirable - namely the Euler-Fermat generalisation to Fermat's Little Theorem, which states that:

$$a^{\phi(n)} = 1 \mod n$$.

Hopefully you should see that our manipulating the algebra to get $m^{\phi(n)}$ in it is not an accident at all - since under $\mod n$, $(m^{\phi(n)})^k \times m^1$ becomes $1^k \times m^1 = m$. This is what makes RSA work the way it does.

I'd also like to address the point fgrieu has raised in his comment, since it is important. The requirement is for the private key is such that $de = 1 \mod \phi(n)$ - or $de = 1 + k\phi(n)$. Clearly, $k$ can be any number we like - any congruence class for which this relation holds will work.

The lowest common multiple of two numbers is the smallest possible number such that both these numbers divide it - for example, the lowest common multiple of $4$ and $6$ is $12$. n this case we observe $4$ divides $12$, as does $6$. Now, the lowest common multiple of $p-1, q-1$ is a number such that both $p-1$ and $q-1$ divide it - well $\phi(n)$ is one such number, for starters! However, (thanks to Poncho), we can say that it is not the smallest possible number. To explain this, consider that $p$ is an odd number and that odd numbers can all be written of the form $2k+1$ for some $k$. If we subtract one, we are left with an even number which will have at least one factor of $2$. Therefore, since $p-1$ and $q-1$ are both even and both have a factor of two, their product ($\phi(pq)$) will have two factors of $2$ at the least, which is 2x what is necessary (at the minimum). More generally, the definition of a lowest common multiple uses the fundamental theorem of arithmetic to demonstrate that the lcm is in fact equal to the product of the maximum power each prime is raised to in each number's prime expansion - eurgh, yes? Well, let's look at that. I chose $4$ and $6$ before - now the prime expansions are $4 = 2^2$ and $6=2\times 3$. Taking the maximum exponentiation of each prime, $2^2 \times 3 = 12$. However, if we did $4\times6 = 2^2 \times 2 \times 3 = 2^3 \times 3$ we see we have gained an extra, unnecessary factor of $2$.

It turns out the Euler-Fermat generalisation can be generalised again - to the Carmichael theorem which states that:

$$a^{\lambda(n)} = 1 \mod n$$

Where $\lambda(n)$ is the smallest such integer where this expression is true. A slight detour - $\phi(pq)=\phi(p)\phi(q)$ and since $\phi(p) = p-1$ that is how we end up with our definition of $\phi(pq)=(p-1)(q-1)$. Now, in the general case, it turns out that $\lambda(pq) = lcm(\lambda(p), \lambda(q)) = lcm(p-1, q-1)$.  By the same reasoning as the case with $\phi(pq)$, $de = 1 \mod \lambda(pq)$ allows us to invert $m^e$ back to $m$ under $\mod n$.

fgrieu has used the term "Rings" - if you're interested in those, I highly recommend Rings, Fields and Groups which is possibly the best Maths textbook I have ever read. It's about (abstract) algebra and also covers some of the number theoretic points, but not as many as a pure number-theory textbook does.


how much trust can we place in protocol verifiers? I read many papers on authenticated key exchange protocols, and most security proofs are done by the authors. In this method, you can imagine that the efficiency is low. Moreover, even if you have proven an AKE protocol's security under a certain model (say eCK), you still cannot ensure the security under all other models, including real life.

This lead me to ask: Can verify protocol's with some automated tool, for example Tamarin? This would be very efficient after all. My initial worry would be whether this will be accepted by people and as convincing as the traditional way?

We know that traditional mathematical proofs can contain mistakes, and that these mistakes can remain undiscovered for years. Sometimes, the scheme is secure even if the proof is incorrect, e.g. RSA-OAEP. Sometimes, the scheme is mildly flawed, the flaws undiscovered because of mistakes in the proof, e.g. HMQV. And sometimes a scheme is simply insecure.

We know that formal systems can fail to describe the real world and therefore prove incorrect results, e.g. BAN logic, but nowadays formal systems seem much more complete.

Formal systems typically work with idealized cryptography. It is sometimes possible to prove that some idealization is sound, but in general this is difficult. Which means that in principle, it might be possible to design schemes that are secure in the formal system, but insecure regardless of what cryptography is used to instantiate the formal object. Similar results exist for the random oracle model and the generic group model, but still the random oracle model is considered a good heuristic for security in the real world (the generic group model less so).

Many systems restrict attention to various forms of encryption and digital signatures. This is in some sense good, because it is likely that the idealization is sound. On the other hand, you often cannot even express Diffie-Hellman in the formal system, which means that it is less useful. Where Diffie-Hellman can be expressed, the group model is often very limited, which means that the formal system might be unable to express various attacks involving subtle properties of groups, and as such it is much less clear how sound the idealization is.

The end result is that formal systems with tool support that are sound and capable of modeling the schemes you are interested in are useful and often very easy to work with. Traditional mathematical proofs are useful, but they are difficult to work with.


How can I convert a DER ECDSA signature to ASN.1? I having trouble verifying an ECDSA signature signed using client side javascript with Java/BouncyCastle.

The javascript signing function source:

sign: function (hash, priv) {
        var d = priv;
        var n = ecparams.getN();
        var e = BigInteger.fromByteArrayUnsigned(hash);

        do {
            var k = ECDSA.getBigRandom(n);
            var G = ecparams.getG();
            var Q = G.multiply(k);
            var r = Q.getX().toBigInteger().mod(n);
        } while (r.compareTo(BigInteger.ZERO) <= 0);

        var s = k.modInverse(n).multiply(e.add(d.multiply(r))).mod(n);

  return ECDSA.serializeSig(r, s);
},

serializeSig: function (r, s) {
        var rBa = r.toByteArrayUnsigned();
        var sBa = s.toByteArrayUnsigned();

        var sequence = [];
        sequence.push(0x02); // INTEGER
        sequence.push(rBa.length);
        sequence = sequence.concat(rBa);

        sequence.push(0x02); // INTEGER
        sequence.push(sBa.length);
        sequence = sequence.concat(sBa);

        sequence.unshift(sequence.length);
        sequence.unshift(0x30) // SEQUENCE

        return sequence;
},

The server side verify function source:

  /**
     * Verifies the given ASN.1 encoded ECDSA signature against a hash using the public key.
     *
     * @param data      Hash of the data to verify.
     * @param signature ASN.1 encoded signature.
     * @param pub       The public key bytes to use.
     */
    public static boolean verify(byte[] data, byte[] signature, byte[] pub) {
        ECDSASigner signer = new ECDSASigner();
        ECPublicKeyParameters params = new ECPublicKeyParameters(ecParams.getCurve().decodePoint(pub), ecParams);
        signer.init(false, params);
        try {
            ASN1InputStream decoder = new ASN1InputStream(signature);
            DERSequence seq = (DERSequence) decoder.readObject();
            DERInteger r = (DERInteger) seq.getObjectAt(0);
            DERInteger s = (DERInteger) seq.getObjectAt(1);
            decoder.close();
            return signer.verifySignature(data, r.getValue(), s.getValue());
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

Does anyone know what format the javascript signature is in (DER?) and if so how to convert it to ASN.1?

I tried:

public static byte[] toASN1(byte[] data) {
            try {
                ByteArrayOutputStream baos = new ByteArrayOutputStream(400);
                ASN1OutputStream encoder = new ASN1OutputStream(baos);

                encoder.write(data);
                encoder.close();
                return baos.toByteArray();
            } catch (IOException e) {
                throw new RuntimeException(e);  // Cannot happen, writing to memory stream.
            }
}

but validation still fails.

Disclaimer: I don't know Javascript and I do not practice BouncyCastle. However, I do know Java, and ASN.1.

ASN.1 is a notation for structured data, and DER is a set of rules for transforming a data structure (described in ASN.1) into a sequence of bytes, and back.

This is ASN.1, namely the description of the structure which an ECDSA signature exhibits:

ECDSASignature ::= SEQUENCE {
    r   INTEGER,
    s   INTEGER
}

When encoded in DER, this becomes the following sequence of bytes:

0x30 b1 0x02 b2 (vr) 0x02 b3 (vs)

where:

b1 is a single byte value, equal to the length, in bytes, of the remaining list of bytes (from the first 0x02 to the end of the encoding);
b2 is a single byte value, equal to the length, in bytes, of (vr);
b3 is a single byte value, equal to the length, in bytes, of (vs);
(vr) is the signed big-endian encoding of the value "$r$", of minimal length;
(vs) is the signed big-endian encoding of the value "$s$", of minimal length.

"Signed big-endian encoding of minimal length" means that the numerical value must be encoded as a sequence of bytes, such that the least significant byte comes last (that's what "big endian" means), the total length is the shortest possible to represent the value (that's "minimal length"), and the first bit of the first byte specifies the sign of the value (that's "signed"). For ECDSA, the $r$ and $s$ values are positive integers, so the first bit of the first byte must be a 0; i.e. the first byte of (vr) (respectively (vs)) must have a value between 0x00 and 0x7F.

For instance, if we were to encode the numerical value 117, it would use a single byte 0x75, and not a two-byte sequence 0x00 0x75 (because of minimality). However, the value 193 must be encoded as two bytes 0x00 0xC1, because a single byte 0xC1, by itself, would denote a negative integer, since the first (aka "leftmost") bit of 0xC1 is a 1 (a single byte of value 0xC1 represents the value -63).

I insist on these details because my guess is that it is what the Javascript code does incorrectly. The Javascript code invokes a method called toByteArrayUnsigned; that name is evocative of conversion to an unsigned representation (i.e. always positive, even if the first bit is a 1), and that's wrong for DER. I invite you to save the raw signature in a file and decode it "by hand" to see if it matches the fine details of ASN.1 encoding, as explained above (the openssl asn1parse command may help, too).

(If my guess is right, you should have a probability of about 1/4 of getting a correct signature nonetheless -- when the values $r$ and $s$ happen to be short enough to have a high bit set to 0 when using unsigned encoding, i.e. a situation where the bug is benign.)


How to make cookies tamper-proof and secure by using encryption and hash / MAC Our company has decided to ditch server side sessions in favor of storing authenticated information such as user id and access privilege information in a cookie.

Before everyone jumps up and down about this approach, given that this is a business decision - how would I do this right? The basic need is to prevent user from tampering the cookie to avoid promoted privileges / or pretend to be a different user and also hides the information. Assumption is all systems are running HTTPS hence let's pretend we won't have cookies being hijacked and replayed etc.

I've read Should we MAC-then-encrypt or encrypt-then-MAC? but I just want to know if this naive approach can work: (plaintext below is my cookie in json format).

// where only 1 secret for AES is used
aes-ctr((plaintext || sha2-256(plaintext)) || iv

Or do I have to do this?

// where 2 secrets are used, one with HMAC and one with AES
let E be: (aes-ctr(plantext) || iv)
then E || hmac (E)

Or are both approaches insufficient?

There are a few key difference between the 2 approaches:

1st approach: In the digest part, we are doing the simple sha256 without the use of nonce or key.

2nd approach: We are using HMAC with one key and another key for AES.

Based on my limited understanding, the listed arguments against a plain digest as oppose to HMAC is due to opportunities for length-extension based attacks. However in my case, given I've AESed the digest, there should be no such opportunity.

Other attacks listed in here: http://www.thoughtcrime.org/blog/the-cryptographic-doom-principle/ appears to be applicable for block mode only, where we are using CTR.

Apologies if this question appears naive - I am a newbie in cryptography.

I am going to answer my own question based on the comment from Ricky Demer:
https://crypto.stackexchange.com/a/16431/991

Given the attacker knew what the plaintext should be, for example:

{"userId":1}  --> this is knownText

And with the first approach, which was

aes-ctr((plaintext || sha2-256(plaintext)) || iv

Attacker can simply perform

(knownText || sha2-256(knownText)) XOR cipherText

To compute the AES cipher stream. Without having to know the key, the attacker can then compute:

(modifiedText || sha2-256(modifiedText)) XOR [deduced AES cipher stream]

Where modifiedText can be

{"userId":2}  --> I want to pretend to be user 2

and then append the original IV.

This would decrypt fine and also validates fine given the first approach. Hence it is insecure.


Does an IV need to be used in AES CTR mode? If I encrypt a message once using AES CTR, will I need an IV? Additionally, if I do use an IV, will I need to send it with the cipher text?

Yes, you need an IV in CTR mode and you do need to send it with the ciphertext, or at least make it possible for the encryption process to know it. Specifically, you need a nonce. The nonce can be anything, as long as it is unique so no key:nonce tuple ever repeats. The nonce is part of the counter. CTR mode operates by encrypting this value and XORing the result with the plaintext. When the next block is to be encrypted, the value is incremented by one and the process repeats.


Paillier Encryption: problems with double encryption Given have two public keys $k1$ and $k2$, $E_{k1}(E_{k2}(m_1))$ and $m_2$.

Is it possible to calculate $E_{k1}(E_{k2}(m_1 + m2))$? (or with multiplication instead of addition)

At a first glance, I thought that it is possible:

Calculate $E_{k2}(m_2)$.
Calculate $E_{k1}(E_{k2}(m_1))^{E_{k2}(m_2)}$.
From the power property of Paillier encryption, this should be the same as: $E_{k1}(E_{k2}(m_1)\cdot E_{k2}(m_2))$.
From the homomorphic property, this is $E_{k1}(E_{k2}(m_1 + m_2))$.
I thought that decryption of the above expression, first with the corresponding private key of $k_1$ and then with that of $k_2$ should give $m_1 + m_2$.

First of all, if you see any problem in my construction, or if you can see another way to do it - please explain.

I tried to run this procedure using two implementations I found on the Web, but I got wrong results.

What am I doing wrong?
Is it possible at all?

No, this is not possible. The homomorphism only works at one layer.

A ciphertext in Paillier is $g^m\cdot r^n\bmod{n^2}$. The plaintext space is the multiplicative group of integers modulo $n$. So, for it to even have a chance to work, first of all, the modulus of the outer encryption would have to be greater than $n^2$, where $n$ is the modulus of the inner. Assume this is true. Let the moduli be $n_i$ and $n_o$ for the inner and outer encryptions respectively (and $n_o > n_i^2$ (I'll similarly subscript all the other parameters).

So, for the encryption of $m_1$ we get $g_o^{g_i^{m_1}\cdot r_i^{n_i}\bmod{n_i^2}}\cdot r_o^{n_o}\bmod{n_o^2}$. Now, what we want is something like $g_o^{g_i^{m_1+m_2}\cdot r_i^{n_i}\bmod{n_i^2}}\cdot r_o^{n_o}\bmod{n_o^2}$. Possible options to get there include exponentiating the first by $m_2$, but that doesn't work. We could multiply the first by encryption of $m_2$ with the outer key, but that doesn't work. Even multiplying by the double encryption (first with inner, next with outer) doesn't work.

I know this isn't a rigorous proof, but there doesn't seem to be a way. The algebraic structure is just too mangled after a second encryption for it to work.