How do voters verify a Helios (v3) election result? So from my understanding of verification specification version 3, a Helios election proceeds as follows:

A voter retrieves the system's public key to encrypt their vote & submit it. The voter gets a fingerprint representing their vote.
When the election period is over, a list of all names & their fingerprints are made public so that an individual voter can see that their vote is in the list correctly
Using the homomorphic properties of the encryption algorithm, all votes are summed
A couple of key people are selected to watch as the private key is used to decrypt only the final summed result, proving that it was done with all votes counted correctly

Questions:

How does an average voter know that his vote actually counted? He doesn't have any way of performing the summation and obtaining the private key to decrypt.
If at the end of the election the private key is made public, then is knowing the list of fingerprints alone enough to calculate the result themselves? I assume no, otherwise individual votes would be known after the fact.
How does the summation process prevent someone from submitting a value outside the range of allowed values, unless they decrypt each individual result... which I thought was the whole point of the homomorphic encryption to not do that?

How does an average voter know that his vote actually counted? He doesn't have any way of performing the summation and obtaining the private key to decrypt.

This is not actually true. He does have a way of performing the summation. From the spec, "all captured votes are displayed (in encrypted form) for all to see". Given the encrypted votes, you can do the summation. The summation is deterministic, so the homomorphic tally that you come up with in your audit, should be the same tally that each of the trustees comes up with. So when the trustees publish their partial decryption of the summation (the decryption factors), the decryption proofs, and the proof of knowledge of the private key, you can verify that they indeed know the private key, verify that the decryption factors are correct (given the tally you computed using all the encrypted votes). Do this for all trustees and you know all decryption factors are correct. Given all the decryption factors, you can decrypt the summation. At this point, you know that the decryption factors match the tally you computed, and you have used those to get the plaintext of the summation. You still need to make sure that your vote is in the list.

There are still a number of other things you need to do to really verify everything. See Verifying a Complete Election Tally for the complete information.

If at the end of the election the private key is made public, then is knowing the list of fingerprints alone enough to calculate the result themselves? I assume no, otherwise individual votes would be known after the fact.

According to the spec:

  When a voter generates a ballot, Helios provides the ballot fingerprint, which is the base64-encoding of the SHA256 hash of the  data structure defined above.

Since it is just a SHA256 hash, even having the private key will not allow an attacker to compromise the privacy of votes given only the fingerprints. They would have to have the <VOTE> data structure.

How does the summation process prevent someone from submitting a value outside the range of allowed values, unless they decrypt each individual result... which I thought was the whole point of the homomorphic encryption to not do that?

The documentation you link to describes how this is done at a high level.

  A zero-knowledge proof, denoted , is a transcript of a non-interactive proof that the corresponding ciphertext encodes an integer value between 0 and max. For the overall proof, the ciphertext whose value is being proven to be between 0 and max is the homomorphic sum (element-wise product) of the choices ciphertexts.

I'm sure they specify exactly how the zero-knowledge proofs work somewhere.


Is there a scheme that allows to use RSA based challenge response protocol limited to signing only 8 bytes to create a secure signature of any data? I have a tiny device that has a challenge-response authentication mechanism where the device signs 8 bytes of any data with it's internal 2048 bit RSA key.

I would like to be able to certify any data using this mechanism by using a number of challenge-response pairs securely chained together (using only 1 pair already discarded because of insecurity of 64 bit long hashes). Each challenge may contain only 8 bytes, each response is a 256 long SHA256withRSA signature. The requirement is to use as few operations as possible since one operation takes 1 second to execute.

The idea is to securely prove presence of the device in a certain situation.

Any suggestions?

Yes! Here is one such scheme.

Let $s=\mathcal S(x)$ be what that the question's tiny device produces for 64-bit input $x$, and $\mathcal V(s,x)$ the public verification function for that, which outputs $1$ if $s$ matches $x$, $0$ otherwise. I'll assume this resists existential forgery under adaptive chosen message attack, and we want to extend it to arbitrarily large messages $m$; and we can assume that the question's tiny device is used only as we specify.

Let $P$ be a PRF with 256-bit output, perhaps $P(K,m)=\operatorname{HMAC}_\text{SHA-256}(K,m)$.

The signer willing to sign $m$:

draws a 256-bit true random bitstring $K$ (it shall remain secret until the last step of the signature);
computes $P(K,m)$ and breaks it into four 64-bit $x_0$, $x_1$, $x_2$, $x_3$;
obtains $s_0=\mathcal S(x_0)$, $s_1=\mathcal S(x_1)$, $s_2=\mathcal S(x_2)$, $s_3=\mathcal S(x_3)$ from the question's tiny device;
outputs $\overline{\mathcal S}(m)$ built as $\overline s=K\|s_0\|s_1\|s_2\|s_3$.

The public verifying function $\overline{\mathcal V}(\overline s,m)$

breaks $\overline s$ into $K$, $s_0$, $s_1$, $s_2$, $s_3$ (or if $\overline s$ does not have the appropriate length, outputs $0$ and terminates);
computes $P(K,m)$ and breaks it into four 64-bit $x_0$, $x_1$, $x_2$, $x_3$;
outputs $\overline{\mathcal V}(\overline s,m)$ computed as $\mathcal V(s_0,x_0)\cdot\mathcal V(s_1,x_1)\cdot\mathcal V(s_2,x_2)\cdot\mathcal V(s_3,x_3)$.

With $K$ unpredictable to an adversary, it is impossible to obtain $\mathcal S(x)$ for chosen $x$. In 34 years of operation of the question's tiny device at a rate of one evaluation of $\mathcal S$ per second, it will output less than $2^{30}$ values of $s=\mathcal S(x)$. Thus each adversarial attempt at finding suitable $(K,m)$ has odds less than $2^{4(30-64)}=2^{-136}$ to yield $x_0$, $x_1$, $x_2$, $x_3$ all among those for which the corresponding $s$ was produced by the tiny device, which would allow a forgery. Thus if an adversary can make no more than $2^{96}$ evaluations of $P$, residual odds of forgery by that method are less than $2^{-40}$ (the only other methods are exploiting some weakness in the original $\mathcal S$ or $\mathcal V$, or the TRNG generating $K$, or the PRF $P$). A rigorous security proof could be made.

If we want to push things towards shorter signature, we could use three signatures rather than four by making $P$ costly to compute; say, using Scrypt: $P(K,m)=\operatorname{Scrypt}(P=K,S=m,N,r,P,{dkLen}=24)$ with parameters $N,r,P$ optimized to match the computing capabilities of the computer used for signature and yield one second computation. We could also shorten $K$ to $40$ bits (there will be a number of collisions, but it won't really harm much).

Addition: if for some reason a secure TRNG is not available to the signer, we can do with a 32-bit counter $c$, and an extra invocation of $\mathcal S$; we

generate $K$ as $\operatorname{SHA-256}\big(\mathcal S(\text{00000000}_\text{ h}\|c)\big)\;$; or if we know the format of the output of $\mathcal S$ we can isolate some random bits of that, rather than hashing;
use $x'_i$ rather than $x_i$ so that the left half of $x'_i$ is never $0$ (these input values of $\mathcal S$ being reserved for random generation as above); e.g. if the halves of $x_i$ are $l_i$ and $r_i$, we use $x'_i= \begin{cases}x_i=l_i\|r_i&\text{if }l_i\ne0\\(r_i\oplus i)\|r_i&\text{if }l_i=0\text{ and }r_i\ne i\\i\|r_i&\text{if }l_i=0\text{ and }r_i=i\\\end{cases}$
increment $c$ before disclosing $K$ or $\overline{\mathcal V}(\overline s,m)$.


What are the differences between X9.31 RSA operation and PKCS#1 RSA operation? NIST and other - mainly older - standards often don't just mention PKCS#1 RSA algorithms but also X9.31 RSA algorithms.

What are the differences between X9.31 and PKCS#1 (v2.1) with regards to

key pair generation;
signature generation;
encryption (if applicable)?

Well, there are indeed differences between the two standards, as you can see below:

  key pair generation

X9.31 requires that $p-1$, $p+1$, $q-1$, $q+1$ all have prime factors between $2^{100}$ and $2^{120}$, and that $p$ and $q$ differ in at least one of the first 100 bits.  These requirements are there to frustrate suboptimal factoring methods, and have been inherited (albeit in an adjusted form) by FIPS 186.

X9.31 requires that $e$ be between 2 (well, 3 for RSA) and $2^{k-160}$ (where the modulus is $k$ bits); that is, it forbids public exponents close to the size of the modulus.

PKCS #1 does not list any specific requirements on key generation.

  signature generation

X9.31 lists a deterministic signature padding format of the form: 0x6bbbbbb...bbba[hash][hash code], where [hash] is where you insert the hash, [hash code] is a 16 bit value that encodes the hash type, and there are enough b digits to make the value precisely fill the block.  BTW: since X9.31 assumes that the key size is one of a specific set of values, all of which are multiples of 4, there's no problem with the leading hex digit being '6'.

PKCS #1 lists rather different signature padding types; RSASSA-PSS (which is a probabilitic signature type), and RSASSA-PKCS1-v1_5 (which is deterministic).

I've never actually seen the X9.31 padding format used in practice.

  encryption

X9.31 does not address encryption at all.


Is $f(x)\oplus x$ a one-way function? Given that $f$ is a OWF and $|f(x)|=|x|$ for all $x$, is $g(x)=f(x)\oplus x$ necessarily also a OWF?

While poncho's answer gives an interesting example, why this can go wrong in practice, it does not necessarily answer the question from a theoretical point of view.
After all, we don't know whether $f(x) = AES_k(x) \oplus x$ is one-way. (Even if it might be reasonable to assume that.)

So, let's give a theoretical example.
Assume that a one-way function $h$ exists where in- and output length are the same. We call this length $n/2$. I.e. we have a one-way function $$h : \{0,1\}^{n/2} \to \{0,1\}^{n/2}.$$

From this function, we now construct a new function
$$f : \{0,1\}^{n} \to \{0,1\}^{n}$$ as follows:
$$f(x_1\Vert x_2) = 0^{n/2}\Vert h(x_1),$$
where $|x_1|=|x_2|=n/2$.

It is easy to show via reduction that $f$ is one-way whenever $h$ is one-way.
Let $\mathcal{A}$ be an attacker against the one-wayness of $f$, then we construct an attacker $\mathcal{B}$ against the one-wayness of $h$ as follows:
Upon input of $y$, $\mathcal{B}$ invokes $\mathcal{A}$ on input $0^{n/2}\Vert y$. Eventually, $\mathcal{A}$ outputs $x_1'\Vert x_2'$ and $\mathcal{B}$ outputs $x_1'$.

It is trivial to see that if $\mathcal{A}$ runs in polynomial time (in input length $n$) then $\mathcal{B}$ also runs in polynomial time (in input length $n/2$).

It is also easy to see the following holds: $$\Pr[\mathcal{B}(y) \in h^{-1}(y)] = \Pr[\mathcal{A}(0^{n/2}\Vert y) \in f^{-1}(0^{n/2}\Vert y)].$$
Therefore it follows that $f$ is one-way whenever $h$ is.

Now lets use this function $f$ in the proposed construction:

$$g(x) = f(x)\oplus x = (0^{n/2}\Vert h(x_1) ) \oplus x_1\Vert x_2 = x_1\Vert (h(x_1)\oplus x_2)$$

This is obviously not one-way. An attacker upon seeing an image $x_1\Vert y$ can simply output $x_1\Vert (y\oplus h(x_1))$ as a valid preimage.


Algorithm for factoring a 30 decimal digit number My professor has given me an RSA factoring problem as an assignment. The given modulus is 30 decimal digits long. I have been searching a lot about factoring algorithms. But it has been quite a headache to choose one for my given requirements. Which algorithms give the best performance for 30 decimal digit numbers?

Note: So far I have read about Brute force approach and Quadratic Sieve. The latter is complex and the former time consuming.

Which algorithms give the best performance for 30 decimal digit numbers?

30 decimal digits is 100 binary digits.

Trial division will require around $2^{50}$ divisions.
Pollard-Rho-Factoring will require around $2^{25}$ checks - this may be a good pick for you if you want to implement it yourself quickly and don't mind having to wait a bit on an optimized execution result.
Most decent quadratic sieve implementations will do this number within seconds.
Most ECM implementations will do that too. If you need something more optimized than Pollard-Rho, using ECM is probably a good pick. Refer to this database for optimal curve representation choices and the Handbook of Applied Cryptography (Ch14, PDF) for fast scalar multiplication strategies.


Does it make any sense to sign a GCM authentication tag with RSA? To achieve double insurance for authentication, can we sign the GCM final tag with using RSA?
with RSA, no one is able to create his own tag since the private key is not known.
However, according to FIPS.186-4, it looks like the input to RSA must be compliant to NIST approved hashing function.
Possible for this GCM + RSA combination?

Not much; signing the GCM tag using RSA is inadequate.
For a start, knowing the AES secret key, it's easy to make a message with any desired content (except in the very end), and an AES-GCM cryptogram that checks, and has any desired tag. Thus any holder of the AES secret key can forge a message that pass verification under the RSA public key of another person, after intercepting a ciphertext signed by that person.
Also, one holding the AES secret key can prepare two very different messages and their AES-GCM encryption sharing the same tag, allowing to spread FUD by showing that the signature of one message also applies to another message.
Further, if RSA-signing the tag was done nevertheless, that must not be with textbook RSA, which is insecure when directly signing small values $m$ such as the 128-bit tag (e.g. when $e$ is so small that $m^e<n\,$, or under the Desmedt-Odlyzko attack for any $e$).

An appropriate way is sign-then-encrypt: signing the plaintext using RSA (e.g. per RSASSA-PSS or RSASSA-PKCS1-v1_5), appending the signature, then using AES-GCM on the whole. This way only the holder of the RSA private key (rather than any holder of the AES-GCM secret key) can make a valid message that pass verification under the corresponding public key; and the signature (which discloses information about what's signed) is not accessible before decryption.
Here I don't recommend encrypt-then-sign, because I do not rule out that the integrity could be vulnerable to a replacement of the original AES secret key.


Exponentiation in ECC I have a naive question, what is the nomenclature of exponentiation mean in ECC?

I was reading about exponential ElGamal, what does it mean if a generator point $G^x$ ?  What does $G * \ldots * G$ actually mean?

I know what point double and point addition are, they are inline with scalar operations with the base point.  How can two curve points be multiplied together?

In a group, where there is by definition only one operation, exponentiation means repeated application of the group operation, whatever that is. That is, if the group operation is noted $\circ$, $g$ is a group element, and $x$ is a positive integer, $g^x$ is short for $\underbrace{g\circ g\circ\dots\circ g}_\text{$x$ terms}$.

In elliptic curve groups, the operation is the point addition with which you are hopefully familiar.


Homomorphism and Zero Knowledge in FIPS 140-2 compliant systems I am analyzing a system that needs to be at least level 3 FIPS 140-2 compliant. The system may leverage from homomorphic and Zero Knowledge constructs, but, as far as I can see, the algorithms approved for FIPS are the most standard ones: RSA, AES, SHA-*, etc.

Is there a similar standard (or an extension to FIPS 140-2) that enables the use of (say) Lifted ElGamal or Paillier? If not, how could one evaluate commercial solutions that support said algorithms?

I'm no FIPS expert but I strongly suspect the answer is no. FIPS is incredibly restrictive and laughably behind the times.

To evaluate those algorithms that don't appear in FIPS, first make sure their component parts are secure (maybe even built with FIPS algorithms as subroutines). Then, if there are known answer tests anywhere, maybe from the authors of the algorithm, you can test the implementation against those. Do a thorough code audit, making especially sure that the malleability of a partially-homomorphic scheme does not lead to a side channel somehow.

If you get to this point, the schemes will be better-audited than 99% of crypto code, and you can probably sleep soundly knowing that you did the best you could with a non-standard algorithm.

As an aside, exactly what "homomorphic" and "zero-knowledge" techniques does it use? The term "zero-knowledge" especially is thrown around a lot in industry, so there's really no telling what they're doing without more info.


Symmetric mutual authentication with client using a derived secret I'm attempting to find a client/server authentication protocol that allows the client and server to authenticate each other when the client doesn't know the server secret but does have a sensitive key derived from the secret.

I would like to use asymmetric certs, but the server in this case is extremely limited in CPU and memory resources, on the order of 16MHz and 32K Ram; but it does have hardware AES support. Speed of the process is critical to the user-experience, but security is paramount.

I was thinking through it and I'd like something like this (The most secure form of each function is implicit):

ClientID (CID): Unique client identifier that ties the token to the client.

Client Token (CT): HMAC(Secret, CID)

Secret (S): A secret that the server knows. The server (or a third party that also knows the key) creates tokens through an offline commissioning process.

Client -> Server
CID, CNonce

Server -> Client (Server derives expected CT with secret and CID)
SNonce, HMAC(CT, CNonce)

Client -> Server
HMAC(CT, SNonce)

This seems to give me a few properties that I need:

The client can verify that the server knows the secret because it is able to HMAC CNonce with a derived CT.
The server can verify that the client has the token because it can HMAC the SNonce with the CT.
Replay attacks are mitigated by the nonces.
MITM attacks mitigated because the token is never transmitted.

The general answer is "no, you can't authenticate someone over a wire unless they know some secret information." The only way to authenticate someone is to have them do something that no one else can do. If you're trying to do it by just sending messages between the parties, the only way I can do something that someone else can't is if I know something they don't (whatever I would send is based only on things I know; if they know what I know they could figure out what I would send themselves).

Your scheme isn't quite that, though. You do have a secret on each side; in fact, it's the same secret on each side (i.e. CT). With a shared secret, authentication absolutely becomes possible; when the shared secret is high-entropy (i.e. not derived from a password), it's even better. MACs should be a decent way to achieve this, although I'd be wary of possible pitfalls (one notable one being that an attacker could get whatever he wants MACed by the server, but with a strong MAC this only allows straight replay, and the scheme stops that).

The other part of your scheme is deriving the shared secrets from a server master secret. If the idea of using HMAC with a secret key to derive client tokens is that you don't need to have a master list of client tokens, then that seems like a sensible approach; HMAC should stop an attacker from creating any secret tokens that they don't already know from other sources. TLS uses HMAC as a PRF to produce cryptographic keys from a secret, so it's a perfectly reasonable choice (the way TLS uses it is having a seed and computing HMAC(secret, label+seed), but in your case you don't need a label).

Much depends on what you plan to do after authentication -- if they'll keep communicating, nothing you did prevents an attacker from tampering with the rest of the communication. For instance, an attacker can hold up message 3 and then send it days later. Is this a problem for your protocol? If so, you have to deal with it somehow.


What does Keccak being "efficiently invertible" mean? Reading through Wikipedia, I saw this:

  It has been shown that the Merkle–Damgård construction, as used by SHA-2, is collapsing and, by consequence, quantum collision-resistant, but for the sponge construction used by SHA-3, the authors provide proofs only for the case that the block function f is not efficiently invertible; Keccak-f[1600], however, is efficiently invertible, and so their proof does not apply.

So:

What does "efficiently invertible" mean in this case? It isn't reversible (as in decryption), so what else could that mean?
Why is Keccak invertible? Is it by design or did they not bother as it's not important?

What does "efficiently invertible" mean in this case? It isn't reversible (as in decryption), so what else could that mean?

Why is Keccak invertible? Is it by design or did they not bother as it's not important?

If you look closely, you will see it does not claim that Keccak is efficiently invertible, it says that Keccak-f is efficiently invertible.
Keccak-f is the function used to mix the internal state in the sponge construction.
Since it is a permutation, it is invertible. If you have the entire state, you can apply the inverse permutation to go backwards to the previous state.
Since the hash function does not output the entire state as the hash output, an adversary may not perform this operation when given the hash output to find the preimage, so it's not a problem for Keccak-f to be invertible (though there may be more subtle differences when using a permutation versus a function to mix the state).
So efficiently invertible means the same thing that it usually does.
As for why the designers chose it, you would probably need to ask them to get a definitive answer. It is not difficult to ensure that a function is an invertible permutation, as long as each step is invertible the entire function will be.


Why the extra bits in Hash width? Quark says u-Quark has 64 or 128 security (bits). But u-Quark width is 17 bytes means 136 bits.

Why this difference? If the hash produced is 136 bits then why do we call them as 128-bit hash value and not 136-bit hash value? If I wish to use the hash value generated, then should I use just the 128 bits or all 136 bits must be used?

Simple example: Suppose you have a hash that is 136 bits but the last 8 bits are always 0.

Clearly it is not more secure than just the first 128 bits.

In practice it will be less obvious but it means that the 136 bit long output will be one of only $2^{128}$ different values.

The extra bits are required to guarantee 128 bit security and cannot be omitted.
To continue the analogy, assume that the 8 extra zero bits are mixed with the rest of the 128 bits. You simply don't know which bits to omit.

To give a possibly more visual, short example consider the following fictitious hash outputs:

$100, 110, 011, 010$

Since there are only 4 possibilities the hash could not have a security level greater than $2^2$. (You could simply attack it by guessing one out of the $2^2$ values.)

However, the output is 3 bits long and you cannot remove any of the bits. If you did you would have less than $2^2$ possibilities left.


Hash functions to generate a one-time pad Maybe this is a newbie question:

Stream cypher, will XOR message bits with one-time pad bits.
Suppose I have a pseudorandom number generator, like a Mersenne Twister or something similar. I could use the pseudorandom string to XOR the message.
Use the password as the seed of the generator. Same password = same pseudorandom sequence.
Could hashing blocks of the pseudorandom sequence create a stronger one-time pad stream?

First things first: a PRNG (Pseudo Random Number Generator) can not provide a one-time pad.

As a reminder: a one-time pad…

has to be truly random,
must be at least as long as the plaintext,
is never reused in whole or in part, and
is kept completely secret.

Only when all four points are met, we´re talking about OTP.

Your PRNG idea fails to meet those parameters as it is neither truly random, nor as long as the plaintext. Also, when not using a CSRNG (Cryptographically Secure Random Number Generator), you´re bound to reuse it in part due to the repeating internal state of regular PRNG algorithms.

Example: the “Mersenne Twister” PRNG you mentioned as example is not cryptographically secure. Given a small amount of output, it´s relatively easy to compute all future outputs. In other words: it´s rather predictable and nothing you want to use when it comes to cryptography. Such algorithms were not build to be cryptographically secure! They were designed for things like Monte-Carlo simulations.

Keeping it short (and actively ignoring other potential issues like missing authentication etc.): the security of your “cipher” will stand and fall with the security of your PRNG – which means that whatever you create with a regular PRNG, can not be considered to be cryptographically secure.

Honestly, when I look at the well-vetted options available (various cryptographically secure stream-ciphers, numerous secure block ciphers which can be run in CTR mode, etc.) I can only wonder why you would even think about creating your own, home-brew solution based on some PRNG. You can trust in the fact that trying to create a stream cipher based on a simple PRNG is a really bad idea.

Same goes for your related key generation ideas… there is a reason why pbkdf solutions exist!


Why does the NIST CTR DRBG apparently output the internal state when no additional input is given? After reading through the specification of the FIPS CTR_DRBG in SP 800-90A (see Section 10.2.1), I got the impression that the output of the DRBG coincides with its internal state as long as no additional input is given.

Let $(K, V)$ denote some previously initialized internal state. Let $E: K \times V \rightarrow V$ denote what ever block encryption algorithm is used.

When the CTR_DRBG_GENERATE function is called with no additional input, the output is calculated as described in 10.2.1.5.1, more specifically in the loop in step 4, which amounts to

$E(K,V+1) || E(K,V+2) || ... || E(K,V+n)$,

provided enough bits are requested.

Then the internal state is updated by calling the CTR_DRBG_UPDATE function with $\operatorname{provided\_data}= 0$ as specified in 10.2.1.2. Here in step 2 apparently the exact same loop happens, as above in step 4, except that it only generates a string of length of the internal state. Still, the new internal state starts with

$E(K,V+1) || E(K,V+2) || ... $.

There is still a final XORing with $\operatorname{provided\_data}$, but since that consists of all zeroes, it does not change anything.

Am I missing something here? Outputting the internal state like this seems unnecessary, because it allows anyone observing the output to predict all future output. At least before non-zero additional input is provided to the generate function or a reseed happens. This makes this CTR_DRBG specification completely incompatible with the AIS 20 requirement for forward secrecy, see 4.6.1 (DRG.1.2).

It is also completely avoidable, by simply adding different constants before encrypting, e.g. n+1, n+2, ... . Interestingly enough this seems to happen for the HASH_DRBG (10.1.1.4), although the situation is a little different there.

I am at a huge loss of why this could be the case. Is there a different threat modeling than what I have in mind? Is this forward prediction resistance simply not considered important enough?

Still, the new internal state starts with

  $E(K,V+1) || E(K,V+2) || ... $.

There is where you are incorrect; the CTR_DRBG_GENERATE function updates $V$ while it runs, and hence the new internal state is actually>

$E(K,V+n+1) || E(K,V+n+2) || ... $

(where the $V$ value is initial value of $V$ when generate is called, not when the update is called).

Because these are encryptions of blocks that are distinct from the blocks used to generate the random output, there is minimal leakage of the new state (well, someone looking at the random output could deduce what the new state is not; however that's not of much help to an attacker)


Security implications of storing an ssh passphrase I'm trying to understand the security implications of encrypting an ssh key with a passphrase, and storing the passphrase in the MacOS key chain or Gnome key-ring.

As I understand it, my ssh key passphrase needs to be long to prevent offline attacks (e.g., an attacker getting access to un-encrypted backups).

The operating system key-ring is encrypted using using my login password (OSX, gnome-keyring). The password normally isn't long (compared to a passphrase) as the operating system rate limits login attempts.

If I backup both my ssh key and my key-ring, have I reduced the complexity of cracking my ssh key from guessing my passphrase to guessing my password? Since it's implemented in both Gnome and MacOS and I haven't seen any warnings about this I feel like I must be wrong, but I'm not sure why.

(..) encrypting an ssh key with a passphrase (..and..) storing the passphrase in the MacOS key chain or Gnome key-ring (..) encrypted using my login password (..)If I backup both my ssh key and my key-ring, have I reduced the complexity of cracking my ssh key from guessing my passphrase to guessing my password?

Yes for competent attackers (as posited in cryptography), and as long at the key-ring does not use dedicated hardware to limit the number of (consecutive) invalid login password presentations (like for the PIN of Smart Cards).

Further, if the login password is short and the passphrase long and good, "reduced" implies "lowered" for all reasonable parametrization of the key stretching for the password and passphrase (key stretching use purposely slow computations in order to slow down dictionary search, and is becoming increasingly critical to any competent use of password, except perhaps with dedicated hardware to limit the number of password presentations).

Rationale for yes: with the methods used by the key-ring and login assumed known, finding its password allows to recover the passphrase (or perhaps, with tight integration of the ssh key encryption with the key-ring, perform anything that knowledge of the passphrase allows; but this is both unusual, and ineffective in the situation).


decrypt AES without whole key Is there a way to decrypt a AES cipher Text which was encrypted twice with some key, when having a part of this key? (the last 3 bytes of the key are missing)

As an above comment said, you have $2^{24}$ different combinations to test as the key. However, if you don't have anything to verify with (i.e. the plaintext is still random data), no.


Malleability of homomorphic encryption El Gamal is a malleable homomorphic encryption system, so is Rabin. Are all homomorphic encryption systems malleable? Or are there any that are not malleable?
Thanks!

The answer may depend on your exact definitions of "homomorphic" and "malleable", but I'll give it a shot.

Basically, homomorphic encryption denotes that, given encryptions $E_k(x)$ and $E_k(y)$ of some values $x$ and $y$, it is possible to obtain an encryption of $x\ast y$ under $k$ from $E_k(x)$ and $E_k(y)$, where $\ast$ is some binary operation, without knowledge of the key $k$. Typically, $\ast$ is the usual addition or multiplication on (bounded) integers, but the attack actually works for almost arbitrary operations (namely, there must be a pair $(x,y)$ such that $x\ast y\notin\{x,y\}$): Assume that an attacker knows $x$ and $y$ along with their encryptions $E_k(x)$ and $E_k(y)$. He may then compute $E_k(x)\mathbin{\hat\ast}E_k(y)$, where $\hat\ast$ denotes the "lifted" version of $\ast$, to obtain a ciphertext $\zeta$. By specification, $\zeta$ decrypts to $x\ast y$, which was assumed different from both $x$ and $y$. Hence, the attacker has obtained a ciphertext ($\zeta$) corresponding to a plaintext ($x\ast y$) he knows but whose ciphertext he has not observed before.

Therefore, any homomorphic encryption scheme is malleable.


Simple secret key encryption with PyNaCl I am playing around with PyNaCl to get a bit into cryptography atm.

Now I wrote two scripts to encrypt a file with a secret key and then decrypt it again using that key. The encryption part works fine but I am having trouble with decrypting the file again.
I get the error nacl.exceptions.ValueError: The nonce must be exactly 24 bytes long when I execute decrypt.py. When I explicitly hand the nonce generated in decrypt.py to the decrypt() function I get the error nacl.exceptions.CryptoError: Decryption failed. Ciphertext failed verification

When I use the last three lines of decrypt.py in encrypt.py however, it works for some reason. But of course I don't want to instantly decrypt the file I just encrypted, instead I want to do that with a separate script at a later point.

Also, I am only using SCRYPT here because PyNaCl does not contain Argon2 in my installation for reasons unknown. I am also aware that I hardcoded the salt in a variable, this is just for testing purposes. Later I want to generate that with utils.random and write it to the encrypted file.

My scripts look as follows:

encrypt.py

from nacl import pwhash, secret, utils

password = b'lala'
infile = "test.mp4"
outfile = "out.crypt"

kdf = pwhash.kdf_scryptsalsa208sha256
salt = '\x1b\r\xbfxrL\xee\x83x\x0b\x83\x13O\x1dv\xbc\xd5\x13\x18w;G\xd6\x88 \xae\x8b\x96^\xbd4\xbc'
ops = 33554432
mem = pwhash.SCRYPT_MEMLIMIT_SENSITIVE

with open(infile, "rb") as in_file:
    data = in_file.read()

derivatedKey = kdf(secret.SecretBox.KEY_SIZE, password, salt,
                 opslimit=ops, memlimit=mem)
secretBox = secret.SecretBox(derivatedKey)
nonce = utils.random(secret.SecretBox.NONCE_SIZE)
encrypted = secretBox.encrypt(data, nonce)

with open(outfile, "wb") as out_file:
        out_file.write(encrypted)

decrypt.py

from nacl import pwhash, secret, utils

password = b"lala"
infile = "out.crypt"
outfile = "decrypted.mp4"

kdf = pwhash.kdf_scryptsalsa208sha256
salt = '\x1b\r\xbfxrL\xee\x83x\x0b\x83\x13O\x1dv\xbc\xd5\x13\x18w;G\xd6\x88 \xae\x8b\x96^\xbd4\xbc'
ops = 33554432
mem = pwhash.SCRYPT_MEMLIMIT_SENSITIVE

key = kdf(secret.SecretBox.KEY_SIZE, password, salt,
               opslimit=ops, memlimit=mem)
box = secret.SecretBox(key)
nonce = utils.random(secret.SecretBox.NONCE_SIZE)
decrypted = box.decrypt(infile)

with open("outfile", "wb") as out_file:
    out_file.write(decrypted)

Any help would be greatly appreciated!

It's not really a cryptography question, but I think the decryption would go better if you read the data from infile first (box works on strings of data, not filenames), so

with open(infile, 'r') as in_file:
    encrypted = in_file.read()

and later:

decrypted = box.decrypt(encrypted)

where the nonce before it can go, as it is not used (the encrypted data contains the generated salt from encrypting).

Also the quotes on "outfile" can go. It's a variable.


ipsec, esp: Which key is used to generate the HMAC Short Question:
Are the keys for the ICV calculation and the encryption the same in IPSEC/ESP?
Or do there exist two keys in the SA?

Long Question:
Before a new IPSEC-ESP connection is established, IKEv2 is used to start a new session.
This involves also a DH key agreement.
This key is than stored in the IKE-SA.

Once the session is established, ESP uses the key in the IKE-SA's for the message encryption/decryption.
After the payload was encrypted, the ICV is calculated by a HMAC calculation.
But this HMAC requires also a key.
I have already searched for a few hours without being successful.

Is it the same key that is used for encryption, is it calculated out of the encryption key or are there two keys stored in the SA?

I wasn't able to find the answer in rfc4303 (ESP), rfc2104 (HMAC) or rfc7296 (IKEv2).

And there are not many books about IPsec out there.

Are the keys for the ICV calculation and the encryption the same in IPSEC/ESP? Or do there exist two keys in the SA?

No, the keys are not the same.  Yes, there do exist two keys in the SA (at least, for SAs that have separate encryption and integrity transforms - not all do).

You do derive both the encryption and the HMAC key at the same time, from the same secret, but they are not the same (that'd be bad key hygene).  Instead they are derived from the same secret (and also you generate the keys for the SA protecting traffic flowing in the opposite direction at the same time).

That is, IKE generates a long random-looking string (which it refers to as KEYMAT); if the encryption key is n bits and the integrity (ICV) key is m bits (and AH is not being used), then at least 2n+2m bits of KEYMAT are generated, and then:

The first n bits is used as the initiator-to-responder encryption key (that is, used to protect traffic flowing from the initiator to the responder)
The next m bits is used as the initiator-to-responder integrity key
The next n bits is used as the responder-to-initiator encryption key
The next m bits is used as the responder-to-initiator integrity key

To see the text of the standard, see section 2.17 of RFC7296:

  In any case, keying material
     for each Child SA MUST be taken from the expanded KEYMAT using the
     following rules:

  All keys for SAs carrying data from the initiator to the responder
        are taken before SAs going from the responder to the initiator.

  If multiple IPsec protocols are negotiated, keying material for
        each Child SA is taken in the order in which the protocol headers
        will appear in the encapsulated packet.

  If an IPsec protocol requires multiple keys, the order in which
       they are taken from the SA's keying material needs to be described
       in the protocol's specification.  For ESP and AH, [IPSECARCH]
       defines the order, namely: the encryption key (if any) MUST be
       taken from the first bits and the integrity key (if any) MUST be
       taken from the remaining bits.

The HMAC key is the 'integrity key'


How to find the inverse of a polynomial in NTRU-PKCS I am coding a java based implementation of the NTRU public-key cryptosystem. I can comprehend the majority of the algorithms involved in the encryption and decryption process well enough, but the key generation process is giving me serious trouble.

I'll briefly go over some basics of the cryptosystem for those that are unfamiliar, otherwise, skip ahead to the paragraph titled The Problem.

We'll be working with polynomials with degree $<n$. Adding and subtracting these polynomials functions normally, however multiplying these polynomials works different¹². Given two polynomial $A$ and $B$ of degree $<n$, their product is
$$A \cdot B = c_0\,x^0 + c_1\,x^1 + \ldots + c_{n-1}\,x^{n-1} = C$$
where each coefficient $c_k$ is calculated by³:
$$c_k=\sum_{0\le i<n}a_i\,b_{(k-i\bmod n)}$$
multiplying each coefficient of $a$ with the same from $b$ in reverse order (if $b_k$ is the first coefficient in $b$ then $b_{k-1}$ loops around to the last coefficient in $b$ and so on) ensure the degree of the resulting polynomial remains $<n$.

The key $F$ is a polynomial with coefficients in $\{-1,0,1\}$. An example (where $n=7$) is:
$$1\,x^0 + 0\,x^1 + 0\,x^2 + 1\,x^3 + -1\,x^4 + -1\,x^5 + 0\,x^6$$
or more plainly:
$$1 + x^3 - x^4 - x^5$$

$F$ functions as the private key but must be verified to have inverse polynomials $F_q$ and $F_p$, which are polynomials of degree $<n$ with integer coefficients $q_i$ with $0 \leq  q_i < q$, and $p_i$ with $0 \leq p_i < p$, where $q$ and $p$ are predefined integers ($q$ is coprime with prime $p$).

$F$ must satisfy that $F_q$ and $F_p$ exist given:

$$F \cdot  F_q \equiv 1 \pmod q \quad\text{and}\quad F \cdot  F_p \equiv 1 \pmod p$$
that is, if we define $C=F \cdot  F_q$, its coefficients $c_k$ must verify
$$c_k\bmod q=\begin{cases}1&\text{if }k=0\\0&\text{otherwise}\end{cases}$$
and same for $F \cdot F_p \equiv 1 \pmod p$.

With all that being said…

The Problem

I am still struggling to grasp the algorithm used to calculate the polynomial inverses of the private polynomial key $F$, $F_p$, and $F_q$ for $$F\cdot F_q \equiv 1 \pmod q$$ and for $p$ etc.

Or to even verify if $F$ is invertible. I've seen different pseudocodes explaining the algorithm but all I've seen are poorly elaborated. Other explanations of the algorithm amount to "You can calculate the inverse using the extended euclidean algorithm" with no example, and looking at the eea myself I'm still none the wiser on how it's applied. I'd greatly appreciate a concise explanation in relation to the polynomial $F$ integer $p/q$ and polynomial degree $n$.

Let me know if there seems to be any key concepts I'm missing or critical variables I've omitted.

Notes of the editors:
¹ In this modified polynomial multiplication, $x^n$ is assumed to be $1$ in coefficients of degree $\ge n$.
²  Equivalently, this is polynomial multiplication modulo $x^n-1$.
³ $u \bmod n$ is defined as the integer $v$ with $0\le v<n$ and $u−v$ a multiple of $n$.

Disclaimer: I'm not familiar with NTRU, and not in my comfort zon. Hence the many edits.

The problem asked can be summarized as: given $n$, $q$ coprime to prime $p$, and for $0\le i<n$ the coefficients $f_i\in\{-1,0,1\}$ of $F=\displaystyle\sum_{0\le i<n}f_i$, find the $n$ coefficients $q_i$ of $F_q$ and $p_i$ of $F_p$ such that, with polynomial multiplication performed modulo $x^n-1$, $F\cdot F_q\equiv1\pmod q$ and $F\cdot F_p\equiv1\pmod p$, or determine that's impossible.

We can treat the problem for $F_q$. The same method will apply for $F_p$. Alternatively, since $q$ and $p$ are coprime, we can find $H$ with $F\cdot H\equiv1\pmod{(p\,q)}$ and if it exists reduce its coefficient modulo $q$ and $p$ to find the $q_i$ and $p_i$ (but if there's no $H$, we could only conclude that at least one of $F_q$ or $F_p$ does not exist).

One conceptually simple method is to see the problem as a system of $n$ linear equations in $\Bbb Z_q$, with $n$ unknowns $q_i$, obtained by using the question's definition for the equivalent equation $F_q\cdot F\equiv1\pmod q$:
$$\forall k\in[0,n-1),\quad \sum_{0\le i<n}q_i\,f_{(k-i\bmod n)}\equiv\begin{cases}1&\text{if }k=0\\0&\text{otherwise}\end{cases}\pmod q$$
and use Gaussian elimination.
If we use the question's $F=1+x^3-x^4-x^5$ for $n=7$, that linear system goes$$
q_0-q_2-q_3+q_4\equiv1\pmod q\\
q_1-q_3-q_4+q_5\equiv0\pmod q\\
q_2-q_4-q_5+q_6\equiv0\pmod q\\
q_3-q_5-q_6+q_0\equiv0\pmod q\\
q_4-q_6-q_0+q_1\equiv0\pmod q\\
q_5-q_0-q_1+q_2\equiv0\pmod q\\
q_6-q_1-q_2+q_3\equiv0\pmod q$$
that is, by realigning$$\begin{matrix}
+q_0&    &-q_2&-q_3&+q_4&    &    &\equiv1\pmod q\\
    &+q_1&    &-q_3&-q_4&+q_5&    &\equiv0\pmod q\\
    &    &+q_2&    &-q_4&-q_5&+q_6&\equiv0\pmod q\\
+q_0&    &    &+q_3&    &-q_5&-q_6&\equiv0\pmod q\\
-q_0&+q_1&    &    &+q_4&    &-q_6&\equiv0\pmod q\\
-q_0&-q_1&+q_2&    &    &+q_5&    &\equiv0\pmod q\\
    &-q_1&-q_2&+q_3&    &    &+q_6&\equiv0\pmod q\end{matrix}$$
The matrix of coefficients is circulant, and its last line has the coefficients of $F$ in reverse order.

This one happens to have no solution except for $q=1$: if we sum all the lines we get $0\equiv1\pmod q$. Mere generally, except for $q=1$, there can't be a solution when $0=\sum f_i$ as in the example.

While we could in general solve the system (or find that it has no solution) by Gaussian elimination and careful application of arithmmetic in $\Bbb Z_q$, that has cost $\mathcal O(n^3\,\log q\,\log\log q)$ and uses $\mathcal O(n^2\,\log q)$ memory. And while there are better methods for a circulant matrix, I won't go further into that.

Better methods to solve this problem are derived from the Extended Euclidean Algorithm, which given $A$ and $B$ in a principal ring, finds $U$ and $V$ in that ring with $A\cdot U+B\cdot V=G$, where $G$ is the Greatest Common Divisor of $A$ and $B$. As a byproduct that gives the modular inverse $U$ of $A$ modulo $B\ne0$, or tells that it does not exist when $G\ne1$.

That algorithm finds the inverse in particular in these rings:

The ring $\Bbb Z_q$ (the integers), where for non-negative $a$ and $b$ it can go:

If $b=0$, output "$a$ has no inverse modulo $b$" and stop.
$c\gets a$, $d\gets b$, $u\gets0$ and $v\gets1$.
Repeat

If $c=0$, output "$a$ has no inverse modulo $b$" and stop.
If $c=1$, output "the inverse of $a$ modulo $b$ is $v$" and stop.
Perform Euclidean division of $d$ by $c$ yielding quotient $z$ and remainder $r$ with $0\le r<c$.
$d\gets r$ and $u\gets u+z\cdot v$.
If $d=0$, output "$a$ has no inverse modulo $b$" and stop.
If $d=1$, output "the inverse of $a$ modulo $b$ is $b-v$" and stop.
Perform Euclidean division of $c$ by $d$ yielding quotient $z$ and remainder $r$ with $0\le r<d$.
$c\gets r$ and $v\gets v+z\cdot u$

The ring of polynomials with coefficients in the field $\Bbb Q$ (the rationals), where it can go:

If $B=0$, output "$A$ has no inverse modulo $B$" and stop.
$C\gets A$, $D\gets B$, $U\gets0$ and $V\gets1$.
Repeat

If $C=0$, output "$A$ has no inverse modulo $B$" and stop.
If $C$ has degree $0$ (that is, has only term $c_0$), output "the inverse of $A$ modulo $B$ is $(1/c_0)\,V$" and stop.
Perform polynomial division of $D$ by $C$ yielding quotient $Z$ and remainder $R$ of degree less than the degree of $C$.
$D\gets R$ and $U\gets U+Z\cdot V$.
If $D=0$, output "$A$ has no inverse modulo $B$" and stop.
If $D$ has degree $0$ (that is, has only term $d_0$), output "the inverse of $A$ modulo $B$ is $(-1/d_0)\,V$" and stop.
Perform polynomial division of $C$ by $D$ yielding quotient $Z$ and remainder $R$ of degree less than the degree of $D$.
$C\gets R$ and $V\gets V+Z\cdot U$.

The ring of polynomials with coefficients in a finite field $\Bbb Z_p$ for prime $p$: same as above, except that when a coefficient $\displaystyle\frac st$ is obtained, we replace it with the integer $0$ when $s=0$, or otherwise with the integer $(t/\gcd(s,t))^{-1}\,(s/\gcd(s,t))\bmod q$.

The later is exactly what we need for $F_p$: we feed $A=F$ and $B=x^n-1$ to the algorithm, and it computes $F_p=A^{-1}\bmod B$ (or tells that is does not exists).

However, for a composite $q$, it can appear $\displaystyle\frac st$ that can no be brought back in $\Bbb Z_q$ because $\gcd(t,q)\ne1$.

I'm not sure about:

If we can conclude that when we hit the problem, we can stop and conclude that $F$ is not invertible.
If we can compute the inverse in the ring of polynomials with coefficients in the field $\Bbb Q$, and reduce in the end. I think we could find that $F$ is not invertible, but it really is invertible modulo $q$.

When $q$ is the product of distinct primes, we can get around that by finding the inverse modulus each prime dividing $q$, and using the Chinese Remainder Theorem to work back the coefficients of the inverse modulo $q$. We do not need to know the factorization of $q$ in advance: when we hit the problem, the GCD gives us a (perhaps partial) factorization of $q$. However I'm not sure of what to do when $q$ is divisible by a square of a prime.

Under work: further straighten that, example.

For a full-blown, faster method, see Joseph H. Silverman, Almost Inverses and Fast NTRU Key Creation, NTRU Technical Report #014, 1999.


How broken is a xor of two multiply with carry generators? How broken is a xor of two LCGs?
How Brittle Are LCG-Cracking Techniques?

Based on the above two questions, I have simply one additional question: how broken is a XOR of two 64-bit multiply with carry generators, with one generator's output rotated by 24-bits before the XOR, and independently generated seed states, with the first output discarded?

Furthermore, what is the fastest attack against this generator with only $2^{20}$ outputs?

I see no reason to expect your construction to be cryptographically secure.  A single MWC generator is not something that was ever designed to be cryptographically secure.  A cryptographically-strong PRNG needs to be designed in a very different way from a non-crypto PRNG.  In particular, it sounds like MWC was designed to have a long period.  But having a long period does not guarantee that a PRNG will be crypto-strength; not anywhere near it.  And xor-ing two non-crypto-strength PRNGs is not in general a good way to build a crypto-strength PRNG; there's no reason to expect that such a scheme will be secure.

Crypto-strength PRNGs have much stronger requirements, so there is no reason to expect that a statistical non-crypto PRNG will be cryptographically strong (it almost certainly won't be, if it wasn't designed to be).  If you want a crypto-strength PRNG, you need to pick one that was designed to be that way from the start; you're not likely to fare well by picking a non-crypto PRNG and then trying to tweak it.

In any case, this approach seems misguided.  We have crypto-strength PRNGs that are secure, fast, and well-vetted.  I don't know why one would mess around with trying to design your own based upon a non-crypto PRNG; that way tends to lead to insecurity.  If you think you can do better than the entire field at designing fast crypto-strength PRNGs... well, maybe you can, but I doubt the odds are on your side.  Instead, I recommend you use a standard crypto-strength PRNG, if you need crypto-quality pseudorandom numbers.

I recommend take a look at What stops the Multiply-With-Carry RNG from being a Cryptographically Secure PRNG?, as well as by KISS: A Bit Too Simple (PDF).  The first one handles the plain MWC construction by Marsaglia; the later analyzes the non-cryptographic scheme by Marsaglia named KISS (which combines the output from two MWC generators as well as a linear congruential generator and a  binary linear generator).  Both do not exactly represent the same construction, but the broad lessons probably apply here as well.  I've paraphrased from my answer there and extended it to apply to this specific question as well.


What is the order of the Identity point on prime order elliptic curve groups? I'm trying to understand how the identity point is represented in a group of prime order.
What I think is correct:
If the group has even order, then the identity point is in the group, because the identity point has order 2.
If the group has prime order, like elliptic curves such as secp256 then the identity point can still be represented as a group, but is the point at infinity. If the point could not be represented in the group, then it would not be a group.
I do not believe I completely understand the second point. What order is the identity point if it is in the group?

For something to be a group, it must have an identity. This is a definition.
The order of an element, $g$, in a group is defined to be the smallest positive number $n$ such that $g^n = 1$, where $1$ is the identity of the group.
By this definition, the order of the identity in any group is $1$.


To answer this, let's look at what the elements of $\mathbb{F}_{2^4}$ are: polynomials with coefficients in $\mathbb{F}_2$ that are reduced modulo $f(x)=x^4+x+1$. This reduction means that any power of $x$ greater than or equal to $x^4$ can be rewritten as a sum of smaller powers: in particular, $x^4=x+1$, and higher powers we can factor this $x^4$ out first. Using this, our elements are of the form $a_3x^3+a_2x^2+a_1x+a_0$, where each $a_j$ is either $0$ or $1$. Now, if we take an element of our field, say $g=0x^3+0x^2+1x+0=x$, we can compute powers of $g$ by repeated multiplication:

$g^0=1$
$g^1=x$
$g^2=x^2$ and so on.

When we take higher powers, this starts getting interesting. For $g^4=x^4$, we can reduce our element mod $f(x)$, and we get $g^4=x+1$. We can continue from here and get $g^5=g\cdot g^4=x\cdot(x+1)=x^2+x$. At $g^7$, we have $x^4+x^3$,
which we once again reduce and get $x^3+x+1$; $g^8=x^4+x^2+x$ which reduces to $x^2+1$.

Your question asks how we can compute powers of a generator $g=(0010)$, so let's examine what the notation $(0010)$ means in this case. As mentioned above, our elements are of the form $a_3x^3+a_2x^2+a_1x+a_0$. We can identify this polynomial with its list of coefficients, $(a_3a_2a_1a_0)$, so that
$1=(0001)$, $x=(0010)$, $x+1=(0011)$, and so forth. In your particular example, you have $g=(0010)$, which is just $x$. Then $g^2=x^2$ like before, which converts to the list $(0100)$. So to calculate these, what we do is convert to polynomial form, do the polynomial arithmetic described above, and convert back to a list of coefficients.


Attacking hashed password by timing attack and other means This question is inspired by this recent one, which raises a point that need to be made quantitative to be meaningfully discussed. I chose an unusual approach: a new question worded as homework that could be asked in a computer security with applied cryptography class (please use meta for critics of that method).

Some system keeps track of user passwords as (userID, H) pairs with H of 20 octets and a single pair per userID. To test an alleged Password for some userID, it is checked that some (userID, H) exists; then computed D of 20 octets as
   PBKDF2(PRF = HMAC-SHA-1, Password, Salt = userID, c = 10000, dkLen = 20);
then the alleged Password is accepted according to the C expression memcmp(D, H, 20)==0.
The value of c is 10 times what is described to be a significant burden for opponents in RFC 2898 defining PBKDF2.
The documentation of memcmpstates:

  int memcmp(const void *s1, const void *s2, size_t n);

  The function compares successive elements from two arrays of unsigned
  char, beginning at the addresses s1 and s2 (both of size n), until
  it finds elements that are not equal:

  If all elements are equal, the function returns zero.
  If the differing element from s1 is greater than the element from s2, the function returns a positive number.
  Otherwise, the function returns a negative number.

Assume than an adversary

can submit (userID, Password) pairs and determine if that's accepted or not, at a rate of $r\approx2^{10}$ pairs per second;
can at every such attempt measure the running time to fine accuracy, and consistently deduce how many elements have been compared in memcmp;
can perform PBKDF2 at a rate of $h\approx 2^{40}$ per second (less computing power than devoted to bitcoin mining according to this statistic);
does not initially know any H;
gets hold of $n\approx16$ target userID.

Give some approximation (as a function of the parameters) of the expected wall clock time since (5) for a competent adversary to find an acceptable (userID, Password) pair, without and with the insight given by (2), for these two models of choice of Password:

uniformly at random among $2^b$ for $7\le b\le90$; detail the adversary's strategy when $b\approx44$ per XKCD recommendation;
by user, with $u\approx 1/4$ of users having picked a password that occurs at least $5$ times in a list known to the attacker, comprising password choices assumed about representative of how actual users choose passwords, with statistics per these 2040 lines of the form a*b (or just a when b is $1$), each line meaning that b distinct password choice(s) each occur a times in the list (note: the threshold of $5$ keeps $\approx50\%$ of the $32603388$ choices, and $\approx4\%$ of the $14344391$ distinct choices).

Propose C code for a memneq function, usable as replacement of memcmp where sign of its result is immaterial, and likely to close the timing vulnerability.

Outline standard techniques to dramatically improve security with no change of the current passwords.

Let's make things slightly more abstract at first.

The attacker knows $n$ salts $s_i$. Passwords have $e$ bits of entropy and are hashed to $h_i = H(s_i, p_i)$. The attacker can calculate $2^c$ hashes $H(s_i, p)$ per second and can query some kind of an oracle $2^q$ times per second for the prefix length shared by $H(s_i, p)$ and the target $h_i$.

Simplest would be if the shared prefix length was known to the bit. In that case when the attacker knows the first $b$ bits of $h_i$, they can look for a $p$ for which $H(s_i, p)$ starts with those $b$ bits ($2^b$ work) and by querying the server would find an expected 2 more bits of $h_i$. Thus, finding the $e$-bit entropy password would take about $2^{e-1}$ hashing work and $e/2$ queries on average.

If the length is known with byte accuracy, the attacker would need to query up to 255 times to go from knowing $b$ bytes to knowing (usually) one more. The hashing work would remain the same at $2^{e-1}$, but about $128(e/8) = 16e$ queries would be required. With $w$-bit words, the number of queries required would be about $2^{w-1}e/w$.

So, in cracking those $n$ passwords, the attacker would spend $n2^{e-1-c}$ seconds hashing and $ne2^{w-1-q}/w$ seconds querying. With your numbers of $n=16$, $c=40$, $q=10$ and assuming $w=8$, cracking even 70-bit passwords would require less than half a minute of queries total, which means it is negligible compared to hashing time for anything remotely secure and the attack is effectively offline. Only with $w = 32$ and larger does it start to matter – each password would require a month or two of queries at that point.

With prefix queries at byte accuracy and 44-bit passwords, the attacker would require 8 seconds of hashing and less than a second of queries to crack all 16 passwords. They might be limited by network latency and need several extra seconds due to that.


How secure is a lagged fibonacci sequence for encrypting brief messages? Say I start with a 26-letter keyword and convert the letters into 26 integers (A=0, B=1...Z=25) nr[0] to nr[25]. Then I create a stream, nr[26] onwards, with a lagged fibonacci sequence where  nr[n]= (sum of nr[n-26] to nr[n-1] )mod 26. And I use the stream to encipher a brief message (no longer than 200 letters) in such a way that the stream is hidden.  How secure is that encipherment?

example of cipher:

ciphertext letter[n] = plaintext letter[n] + key letter[n mod 26] + nr[n+26]

Your key only seems to consist of n, which should be easily brute forced. So not very secure is the only answer that can be given. n could be very large (a 128 bit number or so), but in that case this scheme seems very inefficient.

Please note the remarks on this kind of generator here and here. So even if it is secure, it may be very tricky to show that it is secure (for a large n). There are plenty of better stream ciphers to choose from.


In SSL and TLS, why is there a separate Change Cipher Spec Protocol rather than including a change_cipher_spec message in the Handshake Protocol? In SSL and TLS, why is there a separate Change Cipher Spec Protocol rather than
including a change_cipher_spec message in the Handshake Protocol?

TL;DR
It could be in the handshake, but separating the two makes it easier to enforce the desired behavior in the protocol.
Long Answer
The same question has already been asked at Security.SE.
For your convenience, this community wiki answer provides the related, accepted answer which was provided by Thomas Pornin
:

SSL uses messages which are encoded over records. Encryption is done on a per record basis. However, several messages of the same type (e.g. handshake messages) can be crammed together in the same record. Since the Change Cipher Spec message modifies encryption settings, a new record should begin immediately afterwards, so that the new settings are immediately applied (in particular, it is crucial for security that the Finished message uses the new encryption and MAC).
Using a specific record type for Change Cipher Spec is a way to enforce this property. An SSL/TLS implementation cannot help but begin a new record for the Finished message, since it uses a record type distinct from that of the Change Cipher Spec message. Such a specific record type could be avoided if all SSL/TLS implementations were disciplined enough to begin a new record where they need, and also to verify that the peer also began a new record. It is safer and more robust to make it unavoidable through the record type.


Pailler encryption of small integers to 32-bit integers I want to encrypt very small integers in the range 0-44 using the Paillier cryptosystem. Is there a way to select p, q (g=n+1 anyway) and mostly r in such a way that I can guarantee that the encrypted values are still 32-bit integers?

Also, I have trouble understanding how to select r. According to wikipedia, the random $r \in Z^{*}_{n} $. How can I implement this in a programming language e.g. Java when I will have to select random values of r for more than 100,000 such integers?

Regardless whether input is small, $n$ must be large enough to avoid factorization. Next, $r$ must be sampled from a large space to avoid decryption by trial-and-error. Some crypto and big-numbers library (bouncycastle, openssl, crypto..) might be handy to implement such an algorithm. It would be safe to choose an implementation rather than write it from scratch.


Are there any many to one encryption frameworks available? I am reasonably new to the cryptography. For my use-case I need a method where in I would need a receiver to accept encrypted messages from a range of senders (each having their own, say, public key). My use-case also needs that some of these users only have temporary access which can be revoked externally i.e. without explicitly telling the receiver but ensuring that receiver can no longer honour the encrypted messages from those senders.

Its very similar to the way public wifi hotspots work. Assuming the receiver is the Wifi Router, and each sender has their own passphrase which is short lived for the duration of the subscription.

However in this use-case there is no single receiver, but a network of receivers. All of them talk to each other using a common encryption key. What I am looking for is to have

an encryption key to be a function of multiple sender's public keys.
all of the receivers and the senders can decrypt the messages which were encrypted with that encryption key.
Adding a new sender should be fairly less complex (I guess we need the encryption key to be updated in this case, but if any of the receivers missed the update how can they get attached again?)
Removing a sender should be fairly less complex (Again I guess we need the encryption key to be updated which again comes with the case of how to deal with receivers missing such an update)

Could you please help point such an encryption technique already in place and possibly proven to be secure? Many thanks and please ask if you need further information to answer my query.

What you ask for is possible, but only (I'm pretty certain, although I don't have any sort of formal proof) if there is a central authority who has a separate, secured connection to each user. Also, the concept of public keys becomes unnecessary. If the encryption and decryption key is a function of "public keys", then any user who at any point was a member of the system will be able to encrypt or decrypt messages. To show what I'm talking about, let's build the following system.

We have users $u_1, \ldots u_n$. Let's say that $u_1$ is the authority, and can revoke any user's access to the system. We have a shared encryption key, $k_s$, which is known to all $u_i$ and $k_s$ is determined by some key derivation function $KDER(pub_{u_1}, \ldots pub_{u_n})$.

If $KDER$ is public (i.e., the new key is derived by each user from the public keys), then we have the following problem. Let's say the user getting booted is $u_{n}$. If $KDER$ is public, it is trivial for $u_n$ to attack the system, as they know $KDER$ and know $pub_{u_1}, \ldots pub_{u_{n-1}}$, and can therefore derive the new key.

So the concept of using public keys doesn't quite make sense. So instead of referring to them as $pub_{u_i}$, let's consider them as $tok_{u_i}$, which is private token randomly generated by the central authority. Now, $KDER$ is private, and $u_1$ must distribute the new encryption key using his secure channels. At this point, the users can all use the new key for sending messages, and the booted user won't be able to attack the system.

Having a central authority seems like it should work for you, because of the line:

  My use-case also needs that some of these users only have temporary access which can be revoked externally

Which seems to imply that there is some sort of authoritative actor within or without the system. But if this is not the case I don't believe what you're asking for is possible. For this to be decentralized, every user within the system, including the user who was just removed, must have the ability to create the new key. Crypto has some nice tools for granting access after an amount of time $t$ (proof-of-work systems and so on, see this question), however I do not believe there are any systems which grant access for some amount of time that do not require a central authority.

I really hope I'm mistaken, because such a system would have some very interesting use cases, but if you think about it it doesn't quite make sense. Someone needs to decide when a user's access is up.


Read the result of the hash by SHA-256 as a number I want to read the full output hash of SHA-256 as a number. How I can do it? Is it in the range of 0 to 2^256?

Yes, the output of SHA-256 is well distributed over the entire output of the hash function. That also means that any number generated by unknown input is well distributed, of course.

Which number is represented depends on the number system. If you want to interpret it to be in the range $\big[0, 2^{256}\big)$ then that's certainly possible - and the most likely interpretation by cryptographers (as most cryptographic algorithms use modular operations, and those are most easily defined to use zero- or positive integers).

To use SHA-256 as a positive number you simply interpret it as a statically sized, unsigned number.

Now the fact that it is statically sized doesn't matter much, as any library will likely skip leading zeros. It may however an issue if you want to revert back to bytes.

That leaves the issue of endianness of the number. You can interpret such a value as big endian (network order) number or little endian number. In case of big endian the most significant byte is on the left, while in little endian it is on the right. As the number is well distributed, each interpretation is equally valid - but obviously they will lead to different values with near-certainty for such large values. Generally cryptographers prefer big endian, especially for large number calculations as e.g. in RSA.

One way to do this for C++ is to use a cryptographic library, where such conversions are common. E.g. in Crypto++ there is the Integer constructor with a constructor using the following signature:

Integer::Integer  (   const byte *    encodedInteger,
                        size_t          byteCount,
                        Signedness      sign = UNSIGNED,
                        ByteOrder       order = BIG_ENDIAN_ORDER
                    )

Here encodedInteger would be the hash value of 32 bytes, byteCount would then be set to 32 of course. sign already defaults to unsigned as this is about cryptography and byte order has the right default as well. Beware that not every "BigNum" implementation will have such cryptographically sensible defaults - Java's BigInteger for instance does require you to explicitly indicate that the result should be interpreted as unsigned value.

In the RSA standard the operation is known as the Octet String to Integer Primitive (OS2IP). Please do note though that the formula for that method mathematically describes the usual layout of the bytes in memory. There is no need to perform any exponentiation or multiplication to implement such functionality.


Finding CRC collisions for specific divisor My current textbook (Information Security: Principles and Practice by Mark Stamp) discusses how to determine the CRC of data via long-division, using XOR instead of subtraction to determine the remainder.

If our divisor has N-bits, we append (N-1) 0 bits to the dividend (the data) and then use long-division with XOR to solve for the CRC.

For example:

Divisor: 10011
Dividend: 10101011

101010110000 / 10011 = 10110110 R 1010, where 1010 = CRC

I'm able to perform this computation fine. However, the book mentions that in the case of the divisor being 10011, it's easy to find collisions.

I'm missing something here -- why is it easier to find a collision when the divisor is 10011?

I don't have that book, but I suspect that you are misreading it.

It's always easy to find collisions with CRC, no matter what the divisor (more conventionally known as a polynomial) is.  One easy way is to take the divisor and exclusive-or that bit pattern into an arbitrary place in the message (dividend); as in:

 10011    : Divisor (polynomial)
10101011  : Dividend (message)
11100111  : Modified message

111001110000 / 10011 = 11110110 R 1010

Here, we picked an arbitrary place in the message (starting at the second bit), and bit-wise exclusive-or'ed the divisor there, flipping any bit of the message where the divisor had a 1 bit.  The resulting modified message has exactly the same CRC as the original message.  Also, note that the quotient that we came up with is exactly as the original quotient with the second bit flipped; this is not a coincidence.

Given how easy this is, there wouldn't appear to be an even easier way that is specific to this polynomial.


RSA attack excercise I am a beginner in cryptography. I studied the RSA algorithm and now I want to solve an exercise.

Cipher Text (HEX): 41A387CABD1C144C99E4B44CE2812A7696CE8A9B5941164741E91B82D89886700DD73A61C580BD75DFC0351D3D6BBF644408A77CB421A115C5
Public Key (e, n): (4049, 16395979)

If:

n = p*q
z= (p-1)*(q-1)
e*d mod z =1

And after trying I found:

q = 3659
p = 4481
z = 16387840
d = 10118449

Now,
1) Is it correct value for d(secret key)?
2) I know that I should compute $c^d mod n$, But c is very big hex! How can I do it? Should I split it first?

You could check, if $e\cdot d\equiv 1 (\bmod z)$. [1] Since your $z=\phi(n)$ and you want to do something like $(m^e)^d \bmod n= m^{ed} \bmod n \overset{!}{\equiv} m$. Therefore, $ed\equiv 1 (\bmod z)$

For decryption check cryptool. [2]

[1] https://en.wikipedia.org/wiki/Fermat%27s_little_theorem#Generalizations
[2] https://www.cryptool.org/


Homomorphic cryptosystem with respect to concatenation Are there cryptosystems that are homomorphic with respect to the  concatenation operation? those. there are data q1 and q2, where q3 = q1q2. then the encrypted data f(q1) = c1 and f(q2) = c2 and f(q3) = g(c1, c2) ?
And are there cryptosystems that are homomorphic with respect to data fetch, i.e. reverse operation, with respect to  concatenation?

Yes, we can construct a cipher homomorphic with respect to the concatenation operation (noted $\mathbin\|$ ). In short, we make the encryption of a concatenation the concatenation of the encryptions.

Start from any (CPA or CCA-)secure cipher capable of enciphering into a fixed-size cryptogram a single-symbol plaintext (e.g., an octet or a bit depending on granularity thought). Note $E$ the encryption function, with $c=E(k,r,q)$ the result of the encryption under key $k$ with random nonce $r$ of the single symbol $q$, and $D$ the decryption function $c\mapsto D(c)$ such that $\forall k,\forall r,\forall q,D(k,E(k,r,q))=q$ (for asymmetric cryptography $k$ can be a public/private key pair with the public key used for encryption),  Also assume a public pseudo-random permutation $r\mapsto P(r)$.

Then extend $E$ by stating that when $q$ is the concatenation of more than one symbol, it can be expressed as $q=\hat q\mathbin\|\tilde q$ with $\hat q$ the first symbol of $q$ and $\tilde q$ the rest, and $E(k,r,q)=E(k,r,\hat q)\mathbin\|E(k,P(r),\tilde q)$.

Correspondingly extend $D$ by stating that if $c$ is wider than the (constant-width) encryption of a single symbol, it can be expressed as $c=\hat c\mathbin\|\tilde c$, with $\hat c$ just wide enough for a single symbol, and $D(k,c)=D(k,\hat c)\mathbin\|D(k,\tilde c)$.

Using that operator $\|$ is associative, that construction $E$ can be shown (CPA or CCA-)secure as the original is (we use that applying the PRP $P$ iteratively on random/nounce $r$ generates a pseudo-random sequence); and has the property thought in the question, with $g$ concatenation.

$E$ can for example be AES-CTR with random IV $r$ at the beginning of the ciphertext; or RSAES-OAEP (with symbol a byte, or with encryption of a bit defined as encryption of the byte 00 or FF depending of the bit's value). $P$ can be any PRP independent of $E$.

One drawback of the above simple construction is that it expands ciphertext size considerably. However, that can be fixed, as follows.

we start from any cipher than can cipher an arbitrary string of symbols, and prepend a single 1 bit to its ciphertext in that simple case
we define $g(c_1,c_2)$ with $c_1$ of $k>0$ bits as the concatenation of

as many 0 bit(s) as there are bits in the binary representation $k$
the binary representation of $k$, big-endian (thus starting with a 1 bit)
$c_1$
$c_2$

decryption parses the ciphertext

if it starts with 1 then it is elementary and what follows the 1 is deciphered normally;
otherwise, the ciphertext is composite; the number of initial 0 gives the length of the binary representation of $k$; $k$ follows; then $c_1$ follows on $k$ bits; then the rest is $c_2$; $c_1$ and $c_2$ are then deciphered, recursively.


Whether hash function of two values $h(a,b)=h(b,a)$ are same? If two messages $M_1$ and $M_2$ are given as input to a hash function $h$ is it then true that $h(M_1,M_2) = h(M_2,M_1)$?

I have two messages. I want to know,

Is it possible to apply a hash function to two messages?
If it so is $h(M_1,M_2)=h(M_2,M_1)$ ?

Starting from a normal hash function of $n$ bits $h:\{0,1\}^*\to\{0,1\}^n$, define
$$h(a,b)=h(\;\min(h(a),h(b))\;\|\;\max(h(a),h(b))\;)$$
where $\|$ denotes concatenation of bitstrings, and order of bitstrings for $\min$ and $\max$ is lexicographic.

Trivially, $h(a,b)=h(b,a)$. First premimage resistance is kept. Other security properties (collision resistance, second preimage resistance, security in the Random Oracle Model) need adaptations, but follow from that of the one-argument $h$.

For some uses (including some Proof of Work protocols; see this for more), as well as making proofs stronger/easier, we might need a different inner and outer hash; like
$$h(a,b)=h(\;\;\text{‘1’}\;\|\;\min(h(\text{‘0’}\|a),h(\text{‘0’}\|b))\;\|\;\max(h(\text{‘0’}\|a),h(\text{‘0’}\|b))\;)$$


I want to know difference of calculation cost between SHA(hash) and AES(reversible encryption) I want do detect illegal modification of a string by using HMAC-SHA256 or AES/CBC/PKCS5Padding, with low calculation cost.
Which is the best answer?

I plan to save data in a DB with one of the following format

| METHOD                   | original STRING | VALIDATION BY  |
|--------------------------|-----------------|----------------|
| H:= HMAC-SHA256          | org-string      | H(org-string)  |
| A:= AES/CBC/PKCS5Padding | org-string      | A(org-string)  |

IF A(org-string) cannot be decrypted, the original STRING is modified.

FYI:
 This question well explained difference between SHA and AES.

With AES/CBC mode, an attacker can modify the string, and have the result decrypt without errors; the only thing that can cause a decryption failure is an illegal padding pattern after decryption, and:

If the plaintext string is at least 17 bytes long, then the attacker can modify the string without affecting the padding bytes (and thus leave a valid padding pattern)
Alternatively, changing the entire ciphertext randomly leaves a 1/256 chance that, after decryption, the last byte of the ciphertext is 01 (which is a valid padding pattern)

Hence, to answer your question, HMAC-SHA256 is the best answer, as AES doesn't do the job at all.  If your crypto toolkit provides it, you might want to consider AES-CMAC instead (which is another right answer for this problem)


Encrypt twice with DES using same key ? $\operatorname{DES}(\operatorname{DES}(x,k), k)$ Does encrypting with $\operatorname{DES}$ in the following way $$\operatorname{DES}(\operatorname{DES}(x,k), k)$$ make $\operatorname{DES}$ as strong as $\operatorname{2DES}$ with 2 keys?

Because we have to run $\operatorname{DES}$ twice now for each key in order to find it - first run $\operatorname{DES}(x,k)$ and the output is the input as text for the second round of encryption? So overall $2*2^{56} = 2^{57}$ just like meet in the middle complexity, right ?

Does encrypting with $\operatorname{DES}$ in the following way $\operatorname{DES}(\operatorname{DES}(x,k), k)$ make $\operatorname{DES}$ as strong as $\operatorname{2DES}$ with 2 keys?

No.

  So overall $2*2^{56} = 2^{57}$ just like meet in the middle complexity, right ?

This time estimate ignores the memory requirement that the meet-in-the-middle attack on 2DES requires.

Memory is cheap, but it's not free.  The estimate of $2^{57}$ operations to break 2DES ignores the overhead of both the memory and the interprocessor communication (it's unlikely that a single processor will be able to perform $2^{57}$ DES operations in an acceptable period of time).  As these objections can be addressed, it's not a lie to ignore them, but they are nontrivial considerations.

In contrast, finding the key for $DES(DES(x,k), k)$ requires no memory, and can be trivially parallelized.


How should the length field be handled in a cipher? Suppose that I have a chunked stream. Each chunk is to be encrypted separately. The structure is basically this:

([LEN][DATA])[MAC]([LEN][DATA])[MAC]([LEN][DATA])[MAC]...

How should one handle the LEN field? If I encrypt the whole thing in a (), this encrypts the LEN field as well. So at decrypt, LEN field must be first decrypted, to find out, where the MAC is. Which is considered a bad thing (as I found at several places that the recommendation is: "one should verify MAC before decryption").

The other solution, to pass LEN in cleartext, maybe not a good idea either, as I'd like to encrypt everything.

What's the correct solution for this problem?

It should not be possible to simply remove or add data to a value and come to a valid MAC for a specific key, without knowing the key value. So in that sense you can get away with moving the length out of the encryption.

It would be wise to MAC the length and ciphertext for your authentication tag (MAC value). If you'd be using an authenticated (AEAD) cipher you could put the length in the Additionally Authenticated Data (AAD) input for the cipher.

Generally the length of the plaintext can be easily retrieved or guessed from the ciphertext length; it is for instance identical in CTR mode (and therefore most authenticated modes as well). So in that sense specifying the length is not a security risk. If you want to keep the size secret you must pad the plaintext before using the encryption mode of operation.

Note that you should be aware that without an overall MAC it is possible for an attacker to swap chunks around in your scheme (!). You are also missing an IV value in your scheme, although you could simply count the chunks and use the counter. This would also solve the issue with the re-ordering (but not with truncation!).


Finding the subgroup in isogeny-based cryptography Isogeny-based cryptography is one of the newest post-quantum cryptography. Hardness of this system is based on finding isogeny between two elliptic curves. Also this is theorem:

  Elliptic curves are isogenous over $F_p$ if and only if they have equal
  number of points.

Recently, isogeny based public key methods are widely used in articles.  This methods are implemented in computer systems in milliseconds and in android systems in seconds. This show that in future we can use such post-quantum cryptographic systems in practical world.

I studied many articles about this method, and I saw only mathematical methods, not practical methods or source code. In program such as the MAGMA we can find all isogenous curves with given curves defined over rational field, but I looking for finite field. Also in sage we can find $l$-isogeny with subgroup of order $l$, but in several time our defined curve have not any subgroup with order $l$.

This is one of interesting article. In this article we have some computational example (page $15$). Can you help me fo understand this example. When I send mail to its authors I face with mail error.

How can we find cyclic subgroup of order $l$ of the elliptic curve $E(\overline{\mathbf F_p})$, over the algebraic closure of the finite field?

While there is a sub-exponential attack to compute isogenies on ORDINARY elliptic curves (the basis for the Rostovev and Stulbunov paper that you reference) there is not (yet at least) a sub-exponential attack to compute isogenies on SUPERSINGULAR elliptic curves.  The cryptosystem proposed by DeFeo, Jao, and Plut back in 2011 is based on Supersingular rather than ordinary elliptic curves.  Microsoft Research recently published a paper on this cryptosystem.  The paper contains a good overview of research on this problem to date. An preprint of Microsoft's paper is found here.


What role does the mode of operation play in Veracrypt vs. Bitlocker? There is this VC vs Bitlocker debate . It is always about open source and not open source , alternative algorythms , portability , etc....
That is nothing new , but once I saw someone useing the mode of operation as an argument . VC uses XTS while BitLocker uses CBC . I am not a professional and my experience with modes of operations is very limited . I know that XTS is used for Drives and partitions and CBC is like a default mode for block ciphers .
But does it really count ? Every mode of operation is secure in some way , right ?
And if CBC really is not as secure as XTS , then why does one of the bigges software companies in the world ( Microsoft ) use it in there encryption solution ?

The final part of your question ignores that there are multiple reasons to choose an encryption mode, other than bits of security. Different encryption modes offer different levels of performance, and there is more trust in modes that have been around longer.

The model of an attacker used for disk encryption is slightly different than the model used for other attacks.

To quote wikipedia:

  Disk encryption methods aim to provide three distinct properties:

  The data on the disk should remain confidential.
     Data retrieval and storage should both be fast operations, no matter where on the disk the data is stored.
     The encryption method should not waste disk space (i.e., the amount of storage used for encrypted data should not be significantly larger than the size of plaintext).

  The first property requires defining an adversary from whom the data is being kept confidential. The strongest adversaries studied in the field of disk encryption have these abilities:

  they can read the raw contents of the disk at any time;
     they can request the disk to encrypt and store arbitrary files of their choosing;
     and they can modify unused sectors on the disk and then request their decryption.

  A method provides good confidentiality if the only information such an adversary can determine over time is whether the data in a sector has or has not changed since the last time they looked.

Plain CBC mode is susceptible to a watermark attack in these cases.  When it comes to disk encryption however, normally CBC mode + ESSIV is used which takes care of the watermarking attack. CBC also suffers from the possibility of a malleability attack. (Basically another word for the commonly known CBC bit flipping attacking)

XTS mode offers protection against watermarking built in, but the chief reason to choose XTS is due to its support for ciphertext stealing. Basically ciphertext stealing is a property which allows data sectors whose length is not evenly divisible by the block size to be securely encrypted without expanding the ciphertext.

XTS however has two disadvantages. The size of the key is doubled for the same strength of encryption, and it does not provide protection against data tampering. (Modifying the ciphertext will result in valid decryption to gibberish plaintext) Redundancy for sectors is handled at an application level, and it is needed in both modes. Both veracrypt and bitlocker support XTS mode.


Why does the key for a one-time pad have to be uniformly distributed? I would like an intuitive argument for what goes wrong in the proof that that a one-time pad provides perfect secrecy, if the key $K$ is not chosen uniformly at random from the entire key space.

Intuitively, each key decrypts the ciphertext to a different plaintext.  So if some keys are more likely than others, then some plaintexts will also be more likely than others.  Thus, unless all possible keys (and thus all possible plaintexts) are equally likely, observing the ciphertext will reveal information about the plaintext.

(Note that I'm implicitly assuming above that the attacker has no prior knowledge of what the plaintext might be before observing the ciphertext.  That's fine for a counterexample, since a cipher that provides perfect secrecy must by definition reveal no new information about the plaintext to any attacker.  So if we want to show that a cipher does not provide perfect secrecy, it's enough to show that it can reveal some information about the plaintext to some attacker.)


Why using hash trees instead using a single hash value? If one have files $x_1, x_2, .., x_n$. What are the benefits of using hashing trees $-$ also known as Merkle trees $-$ (for example in git) instead of computing one hash value $h(x_1,x_2,..,x_n)$ ?

A Merkle tree is used for effective retrieving or sending data on the network that you can send/retrieve the data on any order and verify the current data with additional $O(\log n)$-data transmit and in $O(\log n)$-time. Actually, only the root hash is stored $O(1)$. While keeping the root hash any data retrieved/send verified.
\begin{array}{lcr}
 & \text{With Merkle Tree } &  \\ \hline
\text{receiver} & \text{data transmit } & \text{Databank} \\ \hline
\text{keeps the root hash} & & \text{keeps the files}\\
O(1)\text{-space} & & \\
& \xrightarrow{\text{request the ith file }} & \\
& \xleftarrow{\text{sends ith  file with the }O(\log n) \text{ siblings to the root hash}}\\
\text{Verification in} & & \\
O(\log n)\text{- time} & &
\end{array}
The above diagram that you are the owner of the data and outsourced it. If the client wants to upload the data, first they can transmit the root hash digitally signed to the server where the diagram continues.
If you use one hash, then to verify you need to send/receive all of the data and compute the hash all over it $O(n)$-data transmit and in $O(n)$-time. There are also parallel hashing like ParallelHash of the SHA3 or Blake3. This can decrease the hashing time of $h(x_1,x_2,..,x_n)$ if you have more than one core/thread. In theory, this is $O(\log n)$, however, in practice, it may not. Still, to verify, one needs to transfer all at once, i.e.  $O(n)$-data transmit.
\begin{array}{lcr}
 & \text{With Single Hash } &  \\ \hline
\text{receiver} & \text{data transmit } & \text{Databank} \\ \hline
\text{keep hash} & & \text{keeps the files}\\
O(1)\text{-space} & & \\
& \xrightarrow{\text{request the ith file }} & \\
& \xleftarrow{\text{sends all files } O( n) \text{-data transmit}}\\
\text{Verification in} & & \\
O(n)\text{- time} & &
\end{array}
Therefore the benefit is reduced hash time and reduced data transmission.


Searchable Encryption with Substring Search I want to search substrings in encrypted string. To do that I have read “Implement Rabin-Karp Algorithm” and “Substring-Searchable Symmetric Encryption”. After that, I completed the Rabin-Karp implementation. But, those does not answer for my problem. Rabin-Karp requires both main string for searching substrings and substring to be searched. What I want to do is finding patterns in encrypted strings without decrypt it?

There are some works both theoretical and practical that they do solve your problem efficiently and in a secure way. By efficiently i mean the search efficiency is linear on the size of the searched substring. This is achieved by using auxiliary data structures known as suffix tree. Chase and Shen  follow this approach, by encrypting the suffix tree with symmetric primitives.

This work does not use any auxiliary data structure for efficiency. It encrypts consecutive n-grams and their positions.

A theoretical work follows another technique. By altering the subset sum problem to be easily solvable they issue subset sum instances to the cloud, and the cloud solves them polynomially and the solutions are the positions in the original string of the substring.

Stronger security guarantees with oblivious ram are presented here


How is the base64 encoded signature in Craig Wright's proof constructed? Mr. Craig S. Wright might be Satoshi Nakamoto - the inventor of bitcoin. He is currently proving the case.

But how is the base64 encoded proof, that is published by himself on his blog post constructed? Is it random or some sort of collision attack?

My following PHP code "proves" that the signature is valid. It takes the signature, decodes the base64 string and outputs the result in hex. This again is contained in the hex output of a bitcoin transaction from 2009.

$proof = bin2hex(base64_decode('MEUCIQDBKn1Uly8m0UyzETObUSL4wYdBfd4ejvtoQfVcNCIK4AIgZmMsXNQWHvo6KDd2Tu6euEl13VTC3ihl6XUlhcU+fM4='));
echo "proof: $proof
";

$tx = substr(file_get_contents('https://blockchain.info/tx/828ef3b079f9c23829c56fe86e85b4a69d9e06e5b54ea597eef5fb3ffef509fe?format=hex'),86,142);
echo "tx: $tx
";

How do you construct such a string so that this is possible? To me this looks like a very good magic trick, but I can't explain the construction of the input value.

Short version: the signature is correct, it is a real signature and therefore it is possible to verify it with one's favourite software. The scam is not based on a cryptographic attak but on what is signed. Craig Wright has recovered an old (and real) Satoshi's signature and tried to provide it as a new signature to validate his identity. It's, as someone suggested, like to cut out the last page from a contract, paste it to another contract and claim the new contract is ok.

More details:

Wright claimed that he provided a signature on a large file, a text from Sartre. As the text is big, the signature is the decryption of the hash of this text.
The clever move by Wright is to sign the SHA256 of this file, so the final signature is something like:
secp256k1(sha256(sha256(file)))
and one may remark the double use of the hash function SHA256 (while a standard signature would be something like secp256k1(sha256(message)).

The Bitcoin protocol describe how a transaction has to be signed:
secp256k1(sha256(sha256(transaction))).

The algorithm are the same, if the "transaction" and "file" are the same, or better, if their hashes are the same, one signature for the transaction is a valid signature for the file and viceversa.

Wright tried to sell to the world and old signature of a transaction as a signature of the hash of a text.
Why he did it? Because we are not provided of the original Sartre text and therefore is impossible to compute the valid SHA256 image (which text? how is formatted? which charset? newlines? every little change in the text would change the hash) and we cannot search for a given hex string into the blockchain.

A more complete guide to Wright process is available at http://blog.erratasec.com/2016/05/satoshi-how-craig-wrights-deception.html


ECDSA where the group order is larger than the hash size? According to wikipedia, when generating a signature for ECDSA, you do the following (among other things):

  Calculate $e=\operatorname{HASH}(m)$, where $\operatorname{HASH}$ is a cryptographic hash function, such as SHA-2.
  Let $z$ be the $L_n$ leftmost bits of $e$, where $L_n$ is the bit length of the group order $n$.

$z$ is later used to calculate $s$.

Anyway, my question is...  what if $L_n$ is larger than the bit length of $e$?

For example, SHA256 has is 256 bits long. secp384r1, in contrast, has a bit length of 384 bits.

What happens when the hash output is smaller than the group size is perfectly defined by FIPS 186-4; namely, nothing special. The hash output is still interpreted as an integer (using big-endian notation). Yes, that integer is in a range that is naturally smaller than the complete range of integers modulo the group order. For all we know, this does not seem to be that much an issue, from a security point of view (contrary to the generation of the per-signature secret value $k$, which must be uniform among the whole range).

The general process is the following: if the curve (sub)group order is $n$, of length $z = \lceil \log_2 n \rceil$ bits, the hash output, if larger than $z$ bits, is first truncated to its first (leftmost) $z$ bits. The possibly truncated result is interpreted as an integer using big-endian notation; that integer, which is then necessarily less than $2^z$, is further reduced modulo $n$. Thanks to the truncation, this modular reduction is inexpensive, since the value to reduce is less than $2n$, so it can be done with a single conditional subtraction. When the hash output length is strictly less than $z$ bits, e.g. with SHA-256 used with secp384r1, then there is no truncation (it's already small enough) and the modular reduction is trivial (the value is already smaller than $n$).

It shall be noted that FIPS 186-4 and ANSI X9.62 recommend using with each curve a hash function with a somewhat "matching" strength. NIST defines 15 curves: for each of five formal "strengths" (80, 112, 128, 192 and 256 bits), the recommended hash function has output length exactly twice the strength, and there are three standard NIST curves whose subgroup order length is at least twice the strength. Thus, when using the recommended hash function for a curve, there is never any truncation. On the other hand, the curve subgroup order nay be quite larger than the hash output; for instance, curve B-283, the binary non-Koblitz standard NIST curve for strength 128, the subgroup order has length 282 bits, i.e. quite larger than the 256-bit output of the recommended hash function for that curve (SHA-256).