Understanding Password Complexity I’m trying to understand how a program checks for passwords and how fast it iterates through a loop.

I think I understand how to calculate the minimum required strength for my password.

Estimate that an adversary can guess one billion (10^9) combinations a second (Snowden)
Want to make the data safe forever. Let’s define forever as one million years.
That’s (one day $= 86,400$ seconds – say  $10^5$) times $365$ (say $10^3$) times one million ($10^6$)
At minimum my password must be greater than $10 ^{(9+5+3+6)} = 10^{23}$

OK. So far so good.

If we come up with a randomly arrived at password that requires at least 10^{23} then the password is safe.

Now let’s say that we want an algorithm that can be remembered; that can be salted and that one can make different levels of difficulty.

I understand the concept of a dictionary attack but trying to fine-tune my understanding.

Let’s assume that we have a dictionary of words from which to compose the password.
Let’s assume that this dictionary has a length of $1000$.
I’m assuming that a dictionary attack simply loops through an array.

So, if we have selected four randomly selected words {  CORRECT HORSE BATTERY STAPLE } from that dictionary (of a $1000$ words) ones
password strength would be $1000^4$ (assuming random means one can repeat the words) or $10^{12}$.

QUESTION 1: Is each loop through the array one iteration? Does that mean that the password would be uncovered in $10^3$ seconds? (I’m assuming yes. Just affirming)

Say the attacker assumes people may substitute zeros for Os then both HORSE and H0RSE would need to be tried.

QUESTION 2: Has the time iterating through the loop doubled? Would the attacker have to evaluate STAPLE to see if, it too, had an O?

Say I add a character between each of the words {  CORRECTXHORSEXBATTERYXSTAPLE } That would add very little to the difficulty, it would up the complexity by just $26$ but if I used a different letter between each word then the difficulty would increase by $26^4$.

QUESTION 3: How does one calculate the effort required by the attacker?

Take dictionary (assume for simplicities sake)
Iterate through first time (takes $10^{12}$ / $10^9$ seconds)
Iterate through a second time substituting zeros for ohs.  (Assume one oh per word – for simplicities sake) so that takes another $10^{12}$ / $10^9$ seconds
Iterate through a third time substituting @ for ohs
Iterate through a fourth time substituting ! for I
And so on …

Even If the attacker must do $1000$ such substitutions it would turn out to be 1000 iterations. If each iteration takes $10^3$ seconds then the total time is $10^3 \cdot 10^3$ or $10^6$ seconds.

What we get from this is adding complexity by substitution is far less effective than increasing the length of the password.

If we add another dictionary entry to CORRECT HORSE BATTERY STAPLE, for example - CORRECT HORSE BATTERY STAPLE PIANO then the difficultry would have increased to $1000^5$ or $10^{15}$.
$10^15/10^9$ is $10^6$. We keep things simple and have the same defense.

Is the above reasoning correct?  And by the way I’m purposefully avoiding birthday attacks – that will be part of another question. :)

Moderators – I understand that this does not fit in well with the Q/A format expected by StackExchange.

Your counting arguments seem correct but are somewhat moot.

Note that $10^{23}\approx 2^{76}.$ Not even the most optimistic analyses of typical password entropy yield more than $2^{30}$ or so.

Plus there is the issue of what the system does with the password input. All an attacker needs is to find some input into the passwording process that gives the same output as your password.


what are the uses of tweaks in block ciphers? Few block cipher modes has additional parameter , tweaks , especially the ones that are format preserving .

Now the comments section of this blog entry says such tweaks can be used for BIN numbers, expiration dates etc of credit card numbers.

How can tweaks be used to enforce such checks ?

what other ways tweaks can be used ?

There are a couple of related concepts here: Tweakable blockciphers and format-preserving encryption (FPE). It turns out that tweakable blockciphers provide a very natural way of obtaining FPE, but they have other uses as well.

As the blog discusses, sometimes we want, say, encrypted credit card numbers to themselves look like credit card numbers. That is, we want encryption to be an invertible function that takes a 16-digit number and spits out a 16-digit number, and this function should essentially look random to anyone who doesn't know the secret key. In mathematical terms, we want encryption to be a pseudorandom permutation on the set of 16-digit numbers.

But sometimes this isn't enough. For various reasons, it's often the case that only part of your credit card number gets encrypted, while the rest (e.g., the BIN and the last four digits) gets stored in plaintext. This creates a problem: what if two cards share the same 8 encrypted digits? Then if one card is known, the other can be recovered by an attacer. Or worse, what if an attacker has an opportunity to build a dictionary mapping 8-digit plaintexts to 8-digit ciphertexts?

This is where tweaking comes in. Tweaking effectively gives us access to a lot of completely independent pseudorandom permutations --- one for each possible tweak value. So if we encrypt the 8 secret digits using the BIN as the tweak, then the attacks above are no longer a concern. From an attacker's perspective, the ciphertext Encrypt(BIN-1, 01234567) will appear independent of Encrypt(BIN-2, 01234567). This remains true even if BIN-1 is very similar to BIN-2, and even if the attacker knows both BIN-1 and BIN-2. And we don't need to restrict ourselves to BINs -- any cleartext data that can be encoded into a tweak may be used in this fashion.

As I mentioned earlier, FPE is just one use of tweakable blockciphers. Because tweakable blockciphers are so much more powerful than (regular) blockciphers, they are a very nice building block to use when designing other cryptographic algorithms (such as OCB).


Why initialize SHA1 with specific buffer? SHA-1 is initialize with a specific buffer:

h0 = 0x67452301
h1 = 0xEFCDAB89
h2 = 0x98BADCFE
h3 = 0x10325476
h4 = 0xC3D2E1F0?

Why?

The initial values to a Merkle–Damgård type hash function are essentially the plaintext to a block cipher, with the input to the hash function becoming the key. The maximum length of the hash is determined by the amount of bits of initial value. Five 32-bit words gives SHA1 a state size and maximum output of 160 bits. In order for an MD type hash function to output a consistent value, the initial values must be constant.

The first 4 values are those used in MD4 and MD5. They are represented in big-endian format. If represented in little-endian, it can be seen it is a simple 4-bit counter starting at 0000, maxing out at 1111, then stepping back in reverse, in groups of 32 bits:

 0111 0110 0101 0100 0011 0010 0001 0000 = LE 0x76543210 = BE 0x67452301
 1111 1110 1101 1100 1011 1010 1001 1000 = LE 0xFEDCBA98 = BE 0xEFCDAB89
 1000 1001 1010 1011 1100 1101 1110 1111 = LE 0x89ABCDEF = BE 0x98BADCFE
 0000 0001 0010 0011 0100 0101 0110 0111 = LE 0x01234567 = BE 0x10325476

The final big-endian value is an incrementing counter from 1100 for odd 4-bit groups, and a decrementing counter from 0011 for even groups.

These are called Nothing Up My Sleeve numbers, and are chosen as a way of proving the constants are not specially chosen, such as to provide a backdoor to the algorithm. As per figlesquidge's comment as to why these are not simply 0 bits, the average hamming weight of the entire set of initial values is 0.5, half the bits are 1 and half are 0.

The round constants for SHA-1 were also chosen not to be "special", but are generated quite differently. They take the square root of a number in binary, then the first 32 bits, including those before the decimal place, become the round constant. This is the same method used to generate the two round constants for MD4.

0x5A827999 = $\sqrt2$
0x6ED9EBA1 = $\sqrt3$
0x8F1BBCDC = $\sqrt5$
0xCA62C1D6 = $\sqrt{10}$

The design criteria for the first 2 round constants was specified in the original MD4 paper as well as the RFC. The initial value choice was never defined nor explained, most likely because of the obviousness of the pattern. The choices of initial values and round constants were not explained in FIPS-180-1 and later revisions. It is interesting that they chose 10 to generate the final round constant rather than 7, as it is not prime.

One possible explanation for the choice of $\sqrt{10}$ instead of $\sqrt7$ might be that $\sqrt{10}$, along with the other three constants, are the only square roots given in the "Tables of Numerical Quantities", Appendix A Table 2 (ocatal representations), in Donald Knuth’s The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, Second Edition (1981), p. 660, which is referenced in the original RFC 1320 to MD4 (on p. 4) as the source for the constants. In the Third Edition (1997) of the book, these are found on page 727.

SHA-2 (256 and 512 bit digests) in comparison uses the fractional component (after the decimal place only) of the square root of sequential primes 2 to 19 for initial values, and the fractional component of the cube roots of sequential primes 2 to 311 for round constants.


migrate bcrypt -> argon2 We want to migrate our userbase from bcrypt to argon2.

I was planning on an approach that migrates all hashes immediately to argon2; "old" users would have an argon2'd hash of their bcrypt hash of their password.  New users (and users that logged in) would get updated so their argon2 hash of their password was what was saved.

My problem is: to compare hashes in the legacy case, I have to be able to generate a bcrypt hash first then an argon2 hash.  But the bcrypt hash comparison requires information from the password hash itself (salt etc.) to generate a matching value (which can then be hashed with argon2).

If I want to use this approach, do I have any option other than extracting and storing the bcrypt salt somewhere outside the password field?

If I want to use this approach, do I have any option other than extracting and storing the bcrypt salt somewhere outside the password field?

No.  You need to store the bcrypt parameters (salt and iteration count) and the Argon2 parameters.


Order of Edwards curve and its twist In Mike Hamburg's Ed448-Goldilocks, a new elliptic curve (eprint 2015, WECCS 2015) it is studied untwisted Edwards curves in the prime field $\mathbb F_p$
$$E_d:\,y^2+x^2\,=\,1+d\,x^2\,y^2$$
with large prime $p\equiv3\pmod 4$ and the Legendre symbol $\displaystyle\left(\frac d p\right)=-1$.
The matching "twist" is
$$E'_d:\,y^2-x^2\,=\,1-d\,x^2\,y^2$$
Constant $d$ is chosen with minimal $|d|$ such that the curve's order $|E_d|$ is $4\cdot q$ with $q$ prime, the twist's order is $|E'_d|=4\cdot r$ with $r$ prime, and $q<p/4$.
The paper uses prime $p=4^{224}-2^{224}-1$ and gives $d=-39081$,
$q=2^{446}-\mathtt{8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d_h}$,
$r=2^{446}+\mathtt{0335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d_h}$
It holds $|E_d|+|E'_d|=2\cdot p+2$. Update: initially my experiments¹ differed by two but Mike Hamburg kindly pointed my mistake: I did not count the two points at infinity for $E'_d$.
The question (now) boils down to: Why $|E_d|+|E'_d|=2\cdot p+2$ ? And how do we find $d$ given $p$ ?
If the later is by mere enumeration of $d\gets-j\cdot\displaystyle\left(\frac j p\right)$ for incremental $j>0$ and checking $q\gets|E_d|/4$ and $r\gets|E'_d|/4$ are prime, how are these computed²?

¹ With $p\gets4^i-2^i-1$ for $i\in\{4,5\}$, I get
$$\begin{array}{r|rrr}
i&p&d&q&r\\
\hline
4&239&19&59&61\\
5&991&-45&233&263
\end{array}$$
² This may be asking for Schoof–Elkies–Atkin adapted to Edwards curves. Pointer to an implementation also welcome.

Regarding the [B] and [C] parts of the question per the comments:
I'm not sure how exactly did Mike Hamburg find the curve, but from what I know it's usually easier to find the order of the matching Montgomery curve. Recall that Montgomery curves have the form $By^2 = x^3 + Ax^2 + x$. If $B$ is 1, then it fits into the generalized Weierstrass form, and most SEA algorithm implementations work with any curve in the generalized Weierstrass form. (If it's not 1 then you can easily map into a curve with $B = 1$, the same way that short Weierstrass curves can be mapped into $a = -3$)
So basically:

Search for a Montgomery curve matching the criteria;
Then convert it into Edwards form.

One optimization is to instruct SEA to quickly discard curves whose order it knows beforehand that have a small factor (other than 4 or 8), see the tors parameter of the ellsea PARI/GP function, for example.
The paper "A note on high-security general-purpose elliptic curves" has a Magma implementation of the process (though IIRC it uses a slightly different approach). RFC 7748 has a Sage script that also searches for a Montgomery curve (though it will probably be much slower, since it doesn't seem to support that optimization).


Testing PRNG quality from ECC public keys? Having a large set of ECC public keys $P_i = n_iB$ on a fixed curve $E$ over a prime field, is there a way to determine if coefficients $n_i$ were generated using a bad PRNG?

In other words, can a quality of PRNG be tested by knowning the ECC public keys?

No, not in general without a model for how the PRNG might be bad.  If the PRNG is bad, then there is a test to distinguish it from (say) uniform random bit string outputs; you must then adapt that test to work not on bit string outputs, but on the resulting curve points.  How you do this depends entirely on how the PRNG is bad.


How does encryption work in elliptic curve cryptography? So I think I understand a good amount of the theory behind elliptic curve cryptography, however I am slightly unclear on how exactly a message in encrypted and then how is it decrypted.
So my questions are

How are messages encrypted and decrypted?
How are the public and private keys determined?

Thanks for the help

How are messages encrypted and decrypted?

Well, the easiest way to do public key encryption with ECC is to use ECIES.  In this system, Alice (the person doing the decryption) has a private key $a$ (which is an integer) and a public key $A = aG$ (which is an EC point); she publishes her public key $A$ to everyone, and keeps her private key secret.

Now, when Bob wants to pass a note to Alice, he first picks a random value $b$, and computes the points $bG$ and $bA$; he then gives the point $bA$ to a key derivation function $h$, which produces a set of symmetric keys; he then uses the symmetric keys to encrypt (and MAC) the message.  He then sends the values $bG$ and $\operatorname{Encrypt}_{h(bA)}(\text{note})$ to Alice.

When Alice recieves these two values, she first computes the point $a(bG)$, which is the same as $b(aG) = bA$; she then passes that point to the same key derivation function, which produces the same symmetric keys that Bob had.  She then decrypts the value $\operatorname{Encrypt}_{h(bA)}(\text{note})$, recovering the note (and verifying that it wasn't modified in transit by checking the MAC.

If you examine this, you can see what Alice and Bob are effectively doing is performing an Elliptic Curve Diffie-Hellman operation, and then using the shared secret to (symmetrically) encrypt a message.  This might seem like we're cheating a bit, however this meets the criteria for public key encryption (anyone with the public key can encrypt, only the holder of the private key can decrypt), and it also sidesteps the issue of translating the message into an elliptic curve point reversibly (which can be done, but it can be kludgy).

  How are the public and private keys determined?

That's easy; for just about any ECC method, the private key is a random integer $a$ between 1 and $n$ the order of the generator, and the public key is $aG$, the point multiplication of the private key and the generator (which is just a point on the curve that everyone agrees upon).  And, in case you haven't come across this in your studies, the order of the generator $n$ is the minimal value such that $nG$ is the "point at infinity"; when we select the curve, we make sure that this is a large prime.


How to prove that RSA is not IND-CCA2? RSA is homomorphic wrt multiplication and therefore it is not IND-CCA2. But how to show it.
What are the steps to win IND-CCA2 game?

How is the probability of winning calculated?

yes, plain textbook RSA is only OW-CPA (not even IND-CPA).

You can construct an adversary $\mathcal{A}$ which wins in the IND-CCA2 game:

$\mathcal{A}$ sends $m_0=0$ and $m_1=1$ as challenge ciphertexts to be encrypted

$\mathcal{A}$ receives the ciphertext $c_b = Enc(pk, m_b) = (m_b) ^ e \mod N$ for some uniform random $b \in \{0,1\}$.

$\mathcal{A}$ uses the homomorphic property of RSA to obtain a ciphertext for $2\cdot m_b$:

$\mathcal{A}$ computes $c_b' = (2^e \cdot c_b) \mod N = (2 \cdot m_b) ^ e \mod N$

$\mathcal{A}$ sends $c_b'$ to the decryption oracle. and receives the decryption which is either 0 (then $b$ was 0) or 2 (then $b$ was 1).
$\mathcal{A}$ outputs $b$.

$\mathcal{A}$ can query the decryption oracle on the ciphertext $c_b'$ since this ciphertext wasn't received by
$\mathcal{A}$ from the encryption oracle.

The decryption oracle doesn't do any integrity checks, so it will successfully decrypt the ciphertext.

If I didn't miss anything, the probability of
$\mathcal{A}$ winning this game is 1.

You could also beak RSA IND-CPA security by testing which message was encrypted (by encrypting both messages yourself).
This works because textbook-RSA encryption is deterministic.
A scheme that isn't IND-CPA secure, can't be IND-CCA secure.

I hope I could help!


Are there two-way encryption algorithms that include a work factor? I recently learned about the hashing algorithm bcrypt, which allows you to specify a "work factor" for the hash which can be incremented to stay ahead of Moore's Law. I understand there are some other hashing algorithms that also do this.

Are there any two-way encryption algorithms with this property? For example, I'd like to be able to encrypt a file such that it takes a couple of seconds with today's machines to decrypt it using the correct key, and therefore someone who is trying to guess the key will be severely rate-limited.

You can use bcrypt to derive a (long enough) key from your initial secret value, and then use the key for symmetric encryption. "Guessing" the key is an issue only when the key is part of a space of possible keys which is small enough that such guessing is a possibility -- i.e. when the "secret value" is a password. A 128-bit uniformly random key is immune to guessing by virtue of being part of a space of size $2^{128}$. So use bcrypt with your work factor, truncate the result to 128 bits, use AES, and you're done: any guessing will have to work with the password, and will thus greatly suffer from the bcrypt work factor.


The Inverse Affine Transformation of AES Sbox uses different additive constant? The Affine Transformation for AES Sbox is given by (1)

The straight forward reverse to this transformation is (2)

Where as the inverse of Affine Transformation is given as (3)

where (4)

why did the designers preferred the (3) instead of straight forward reverse (2)?

Those are, of course, two equivalent ways of writing the same function, so it really doesn't matter which one you use.  If you're implementing AES, you can use whichever form of the S-box you find more convenient — or even something else entirely, as long as it gives the same results.*

That said, it's often desirable to share as much code and/or circuitry between the encryption and decryption implementations as possible.  Thus, it can be convenient to implement the forward and reverse S-boxes so that they have the same mathematical form.  Thus, if you're going to implement the forward S-box using formula (1), it can make sense to implement the reverse S-box using formula (3), since the only difference between them is the choice of constants.

*) Of course, however you choose to implement the S-box, you'd typically want to make sure that it runs in constant time and doesn't leak any sensitive data via any other potentially exploitable side channels.


running time measured by clock cycle Some literature said the running time of attack algorithm is measured by clock cycles. What is the meaning of clock cycle and why  the running time of attack algorithm is measured by clock cycles?

Some literature said the running time of attack algorithm is measured by clock cycles.

I suspect that either you misunderstood what was written (sometimes we measure the speed of crypto algorithms in terms of clock cycles, because that is somewhat more platform independent than, say, time), or you have taken it out of context.
  I'll assume the literature was discussing the performance of a cryptographical algorithm, rather than an attack (which we generally do not feel the need to define the performance as tightly).

As for what a 'clock cycle' is, well, when we have a computer (CPU), then generally the CPU executes instructions based on a master clock (which runs, at least for periods of time, at a fixed rate); the various operations that the CPU performs to execute instructions are based on this master clock.  One 'beat' of this master clock is termed a 'clock cycle'; that is, if the instructions used to encrypt a byte of data in completed in 10 beats of this master clock, we say it runs in 10 clock cycles.

Of course, it turns out that real computers are rather complicated affairs, and so the above description is both vague and simplified.  They sometimes have multiple independent clock implementing different parts of the processor, and sometimes the rate of the clock will vary (because of a number of reasons).

What 'clock rate' can be used to compare the efficiency of two different algorithms on the same processor, as it (mostly) factors out the differences between absolute clock speed; for example, it can be used even if one processor is running at 2GHz and the other at 3GHz.  However, comparing 'clock rates' between different CPU types (for example, Intel and ARM) makes absolutely no sense; in fact, it makes little sense to compare clock rates of different Intel internal architectures.


Hashing fundamentals I have some ideas floating around my head for exploring hashing functions, but I want to make sure what I think I know is actually true, before basing a house of cards on it :)

Let’s start with some things I’m reasonably sure of, but are still probably wrong:

A hash function is one such that for any given state $S$, and input bit $X$, we generate a new state
   $$S' = H(S,X)$$
This can be generalised into two functions, we’ll call them $F_a$ and $F_b$
   $$H[S,0] -> F_a[S]$$
   $$H[S,1] -> F_b[S]$$
$F_a(X) \ne F_b(X)$, for all values of $X$.
Selecting between different implementations for $F_a$ and $F_b$ each round is equivalent to just adding state bits
Hash functions that work with padded blocks of input rather than single bits are simply a performance optimisation, and can be replicated as a (more convoluted) single-bit hash by adding (blocksize-1) bits of “counter" state.
Any hash algorithm used for cryptographic purposes would be salted with a random initial state, and that not all state bits would be used as output (NIST SHA-3 is 2 state bits for every output bit).

These things I’m not so sure of. Given a state size of $N$ bits:

Recursive application of $F_a(F_a(F_a(F_a(S) \ldots)$ would ideally yield every possible value for $S$ before repeating

Ditto for $F_b$, of course they must be different sequences.
Mixing in length counter state or using a block mode is effectively an attempt to approach this goal

For all values of $S$, $F_a(S)$ and $F_b(S)$ would have ideally different but close hamming distances from $S$, and the average hamming difference between $S$ and $S’$ for both functions should be $\frac{1}2 N$
On average, the hamming distance between $F_a(S)$ and $F_b(S)$ should be $\frac{1}2 N$

I’m not sure if the above list of desirable qualities is correct, and I’m damn sure it’s not complete. I also think they may be contradictory.

Can anybody shed some light on my understanding, and let me know if I'm miles off-base?

Update:

Apologies for my inability to express what I mean more clearly! The answers and comments are a big help in seeing where I'm leaving too much out.
I shouldn't have mentioned the salt side of things, it's clouding the issue, as I was thinking of things like protecting passwords in stolen databases. Forget about the random start state :)
I understand that the high-level definition of a hash concerns an arbitrarily long input message, and also that current hash methods work on a combination of state and padded n-blocks of input. I'm trying to satisfy my intuition that this (and the required padding) are simply internal details, and could all be generalised into a bigger state and a 1-bit block size.
The reason for all this is because I'm going to do some exhaustive exploration of possible hash functions using small state sizes, to see if I can discover some general criteria for evaluating more practical large-state / large block hash functions - and also to satisfy my curiosity :)

I'm not sure if you want to model existing hash functions with a general model, or invent a new one.
The usual general definition of hash function is a function which takes a variable length input bit string and produces a fixed length output bit string: $h : \mathbb{Z}_2^* → \mathbb{Z}_2^n$ ($n$ being the output length).
All real-live hash functions I know have some input block size (often larger than the output size), and process the input in blocks of this size. One could model this as a "processing function"
$$p : S × B → S,$$
i.e. a function which maps a state and a block of input to a new state. Often part of this state is some kind of counter or other bookkeeping information, and another part is what is the cryptographically interesting one, where the pseudo-random shuffling goes on (and where you want to have your hamming criteria going on).
At the end, when we want to produce output, another transformation $o : S → O$ is used, which transforms the state to the output. In some hash functions this is a simple projection (throw away the bookkeeping part of the state and output the rest of it), in other cases it does more processing.
We also need some initial state $S_0$ (usually fixed in the specification of the hash function), and some input padding rule $pad$, to make the input a multiple of the block size.
The whole hash function can then be modeled as this:
$$h(M) = o(p(p(\dots p(p(S_0, M_0), M_1), \dots ), M_{k-1}, M_{k}))$$
with
$$M_0||M_1|| \dots ||M_k = pad(M)$$
and each $M_i$ having the hash input block size.
Due to the iterative nature of the construction, we can process the input as it comes, block by block, assuming $pad$ only changes the end of the message (or at least all changes for a block depend only on the current block (and maybe earlier ones) and not the future ones).
If a programming interface allows supplying the input in smaller chunks, these are stored in some cache until a full input block is filled, and then the processing function $p$ is evaluated. If a programming interface allows supplying the input in larger chunks, these are splitted into the input block size. It is easy to create such interfaces which allow arbitrary sized input chunks, for any input block size, so the programmer (user of the hash function) doesn't even have to know that size.
Of course, we could view a programming interface which allows single-bit input as a "hash function" $H : S \times \mathbb Z_2 \to S$ like in your question, but then in most cases the state would change only by adding this single bit to a cache (and updating some input cache counter) – your hamming distance criteria is not valid at all.
This is not a problem, as long as the internal processing function $p$ comes near it, or the output transformation $o$, which is run at the end. After all, the user of a hash function is only interested in the final output, not in the internal state changes.
So your hash function model is not that useful as you imagine.
About your other points:

For a (cryptographic) hash function to be generally useful, it is important that it produces the same output for the same input. Using a random initial state makes this impossible. So normally some "random-looking" (or simply zero) initial state is fixed in the definition of each hash function.
If you want a random output, you can use different primitives based on a hash function (like a keyed hash, or a hash-based stream cipher).

As the state is finite, if your processing function is defined everywhere, you eventually get into a loop. Usually this loop will not contain every possible state, but be a lot shorter. This is not a weakness, as it is still longer than anyone could possible evaluate in his lifetime, assuming sufficiently random behavior and a large enough state.
In practice often the total input size is limited by some huge number so you actually don't get your loop.


Encrypt challenge instead of storing it on the server My server and my smartcard (MIFARE DESFire) want to establish that they have the same shared AES key. They want to do that with an untrusted client in the middle.

Usually it works like this:

Now this requires that I store RndA on the server between Generate RndA and Decrypt and compare RndA' with Rotate(RndA).

My question is: Instead of storing RndA on the server, can I safely use the same AES key to encrypt RndA and pass it on to the client for storing?

The sequence becomes:

I feel uneasy about providing the Client with both AES(RndA || RndB') and AES(RndA), but I'm not sure if that is justified.

If that is unsafe, what about the alternatives? Encrypt RndA with a fixed key shared among all smartcards? Or store one more key per smartcard to encrypt RndA?

Short version:  No it is probably not safe; it will likely allow for a replay attack.

Longer version:  Defining what "safe" means is always a little tricky and dependent on a lot of other context.  With what you have showing in your sequence diagrams, the approach of sending AES(RndA) and not storing it on the server would allow your untrusted client to reuse that same data in a future transaction.

If the server simply compares the AES(RndA') and AES(RndA) that is receives from the client, there is nothing that ties it to this particular transaction.  Once a malicious client has done a single valid transaction, it can just send back the results for any future transactions.  Because the server doesn't keep the random value, it has no way to tie a given pair of AES(RndA') and AES(RndA) to a particular transaction.

You can add additional data like serial numbers, user ids, timestamps, etc to the encrypted values so that there is some state.  Those will help in some scenarios as supplemental checks, but they will never be as strong as simply keeping the full random value.


salsa20 is invertible, useless in CTR mode? I'm reading the salsa20 spec (sorry for the newbie question, i'm really a newbie here). Every paragraph ends with : "this operation is invertible", I suppose the whole salsa20 algorithm is.

If I use salsa20 in bloc cipher CTR mode, this property does not seems mandatory to me, am I right?
As such, any cryptographically-robust hash function (one-way only) could be used for CTR encryption?
Isn't it easier to design a robust hash than a robust cipher?

Every paragraph ends with : "this operation is invertible", I suppose the whole salsa20 algorithm is.

The Salsa20 quarterround, and thus rowround, columnround and doubleround are invertible. However, the whole Salsa20 core is not because the initial state is added to the state after iterating the rounds (cf. page 6 in the spec).

  If I use salsa20 in bloc cipher CTR mode, this property does not seems mandatory to me, am I right?

If the whole cipher core was invertible, then a known plaintext attack would reveal the key. So not being invertible is a requirement, somewhere along the line.

  As such, any cryptographically-robust hash function (one-way only) could be used for CTR encryption?

This is correct. See, for example this question.

  Isn't it easier to design a robust hash than a robust cipher?

Maybe, but block ciphers are usually much faster than a hash function in CTR mode. Hash functions are optimized to consume data, not output it. Stream ciphers, OTOH, are occasionally even faster, like you can see if you compare Salsa20 and AES in software implementations.


What's the reasoning behind the design of the TLS 1.2 PRF? TLS 1.2 defines a PRF-like construction $P_{hash} : \{0,1\}^* \times \{0,1\}^* \rightarrow \{0,1\}^l$ for key derivation, etc. To quote the spec:

  We define a data expansion function, P_hash(secret, data),
  that uses a single hash function to expand a secret and seed into an
  arbitrary quantity of output:

P_hash(secret, seed) = HMAC_hash(secret, A(1) + seed) +
                       HMAC_hash(secret, A(2) + seed) +
                       HMAC_hash(secret, A(3) + seed) + ...

  where + indicates concatenation.

  A() is defined as:

A(0) = seed
A(i) = HMAC_hash(secret, A(i-1))

Why does $P_{hash}$ invoke HMAC twice per block of output? Are there valid security arguments for doing so?

In particular, why not a simpler, faster, counter-based scheme such as:

  $P_{hash}(\text{secret}, \text{seed}) = B(\text{secret},\text{seed},0) \| B(\text{secret},\text{seed},1) \| \dots
\\ B(\text{secret},\text{seed},i) = \text{HMAC}_{hash}(\text{secret}, \text{to_byte}(i) \| \text{seed})$

If there is no technical advantage, what are the historical reasons behind this design?

Read Marsh Ray's analysis. PRF in TLS is designed to be the most conservative aspect of TLS (the last part of TLS to break). Mr. Marsh calls it "the slowest, most conservatively designed stream cipher in common use".

TLS PRF seems to be NIST sp800_108 in "Double Pipeline Mode". What Tim McLean contemplates above as a potential alternative is sp800_108 in "Counter" mode.

The "Double Pipeline Mode" is the most conservative sp800_108 mode, and is also subject to several papers (ex. by Koutarou Suzuki and Kan Yasuda) that prove certain "feel-good" properties about it that are not present in other modes.

TLS (IMHO) is trying to ensure that its PRF survives even when the underlying hash function gets utterly broken (ex. assume something even more broken than MD5).


BCrypt vs Key Stretching MD5 Ars technica posted an article about the latest in cyber warfare from the stuxnet crew.

They key stretched MD5 by iterating it 10,000 times.  It seems to be effective at handicapping HashCat's gpu acceleration.  Had I been them I would have used bcrypt instead.

Why/When would someone prefer streched-md5 over bcrypt?
How is bcrypt superior to a strectched-MD5?

If you've got the math power $MD5(password)^n = bcrypt(password)$ solve for $N$.

Any time there is a choice and password search is an issue, one should prefer scrypt or perhaps bcrypt to stretched-md5, or even PBKDF2.

The reason is that scrypt and bcrypt provide better security, by requiring a bigger investment in hardware (in particular, RAM) for the would-be password cracker, assuming parametrization yielding the same runtime for legitimate use. If enough RAM is available in legitimate use, the additional security obtained by using scrypt can be quite dramatic. See the following table from the paper Stronger Key Derivation via Sequential Memory-Hard Functions defining the Scrypt Password-Based Key Derivation Function.


Is AES/CBC/NoPadding vulnerable to padding oracle? If we used Cipher.getInstance("AES/CBC/NoPadding"), will it be vulnerable to padding oracle attacks?

If there is no padding then the cipher is not vulnerable to padding oracle attacks that originate from the cipher implementation. The cipher expects full blocks of ciphertext and simply decrypts them to whatever information, even if that seems random.
However, padding oracle attacks are part of a larger set of attacks called plaintext oracles. Plaintext oracles react to information that is released by an implementation when the plaintext is altered. As CBC doesn't provide message integrity the attacker can perform any kind of change.
The most simple example is if the code itself pads / unpads the message using e.g. PKCS#7 padding. In that case, the padding oracle is not present in the cipher, but present in the code surrounding the cipher. It would be just as bad as a padding oracle attack that was created by using the cipher implementation.
Another, less obvious examples of plaintext oracles are the attacks on the XML-encryption standard. Those are at least as efficient as padding oracle attacks.

Of course, as always, the plaintext oracle must need to be present; for instance, local file encryption may not expose an online oracle. And as always, plaintext oracles are best avoided by adding a message authentication tag for message integrity (such as a HMAC calculation over the IV and  message, or by using an authenticated / AEAD cipher such as GCM).


Here is the solution to M^e is less than N:

http://asecuritysite.com/encryption/crackrsa2

An alternative method is here as a fun article:

http://asecuritysite.com/encryption/crackrsa5

Do you have the Cipher value?


can anyone explain inversion per byte? I am designing the truncating block of SHA3 algorithm , there its given that first we need to do the inversion per byte of the 1600 bit output and then truncating it to give 512 bits output.

Can any one briefly explain this whole step of SHA3.

As far as I know, some people use the term inversion per byte for the conversion functions of section B1 of the standard, i.e. h2b and b2h, which convert from the unusual (i.e. different than as in SHA1, SHA2 ) NIST bit encoding to Hex bytes.

This is relevant only if you implement the API for hashing bit-string messages
with non-zero bit length mod 8.

The concluding paragraph of the 'Conversion Functions' section of FIPS 202  is: The formal bit-reordering function that was specified in
[12] for the KECCAK submission to the SHA-3 competition gives
equivalent conversions when the message is byte-aligned, i.e.,
when n is a multiple of 8.

If you work with byte messages this whole stuff adds some confusion but is not really necessary (and therefore it is no surprise that is not met often in actual implementations.)


Multiplicative sharing of 1 Let R be a ring.

Is there a known/standard way for N parties to perform some exchanges, such that at the end each party holds an element $r_i\in R^\ast$ and $r_1r_2\dots r_N=1$ (and each party $i$ does not know $r_j$ for each $j\neq i$)?

(Or equivalently, share 0 additively?)

If the ring is multiplicatively commutative, the obvious way to do this is:

Have each pair $a, b$ create a secure connection, and jointly select two random invertible elements $r_{ab}$ and $r_{ba}$ with $r_{ab}r_{ba} = 1$ (that is, they're inverses of each other).
Then, $$r_a = \prod_{b \ne a} r_{ab}$$

This is secure (in that any group of parties know nothing about the shares that everyone else has, except the product of their shares), however it does require $O(N^2)$ communication.

If we reduce the requirement to "no single party can deduce anything about any other party, then we can reduce the communication to $O(N)$ (by having $a$ exchange with $a+1$ and $N$ exchange with $1$).


Key derivation for AES-Encryption key and HMAC Okay so I have two options for how I would derive two keys for AES encryption and HMAC they are as follows:

Run BCrypt on a users passphrase and then use the bouncy castle implementation of HKDF in java to extend the key from 31-bytes to 64-bytes before then splitting the result into two 32-byte keys.
Run Bcrypt twice on a users passphrase with a different salt and then use the bouncy castle implementation of HKDF in java to extend both keys from 31-bytes to 32-bytes.

My question is which way is better? (more secure)

Note: If you do have a answer please leave your reasoning in a way that is easy to understand.

In both options, if the adversary has a way to check either AES key, then a brute password guessing attack can be attempted, and BCrypt is the main line of defense against that.

For constant effort, option 2 force to halve the cost parameter in BCrypt, and is thus twice more vulnerable to password guessing than option 1 is.

BCrypt's output is described as 31 byte, and likely has 192 bits of entropy excluding cost and salt. If so, this is more entropy than needed for security in the foreseeable future, and acceptable baring a diktat requirement that all keys have some larger size.

Thus option 1 is decidedly the best of the two; however a proper implementation of scrypt would be considerably safer, and as a bonus there is no need for something extra in order to generate the desired amount of key material.


Diffie-Hellman computing public key with a large private key Given is Generator $g = 5$, Multiplicative group $F_{10007}^*$, Private key = 7347.
Then public key is $5^{7347} \bmod 10007$ right?
On a calculator this gives an overflow error, how am I supposed to calculate the public key when a private key is a large number?

On a calculator this gives overflow error, how am I supposed to calculate the public key when a private key is a large number?

A standard calculator cannot handle that, and we don't expect it. If you have a programmable one you can use square-and-multiply as in levgeni's answer. This, however, will fail when the calculator cannot handle integers (the modulus) larger than the calculator's word size.
There are better and easy approaches

Use WolframAlpha 5^7347 mod 10007
Use SageMathCell 5^7347 % 10007
Use Python's pow that takes a third parameters as modulus pow(5,7347,10007) and uses modular-square-and-multiply. Online


Figuring out key in hill cipher (chosen-plaintext attack) I have been wondering what approach to take in order to figure out what key was used to encrypt a message using the hill cipher.
I know it is possible to obtain it even if it were just a known-plaintext attack, so it should be fairly possible for a chosen-plaintext one.
I'm trying to figure it out with just intuition, but since I know freq. analysis won't be of help, I don't know what else to try. I want to get my head around this, but could someone point me in the right direction?

Sure.  Assuming that you're using the encoding $A = 0$, $B = 1$, etc., just choose your plaintext messages to be the one-block strings:

$$
BA \dots A \\
AB \dots A \\
\vdots \\
AA \dots B
$$

The encryptions of these strings will then directly give you the columns of your key matrix.


Reusing IV in AES for encrypting file Everyone says that you shouldn't use the same IV and Key.

Is it safe to use the same IV and Key on only one file. EDIT: I will be using CBC or CFB encryption modes so the IV will be updated based on previous block.
Is it safe to use the same IV (EDIT: Same first IV, which will then be updated with each block.) each time I access and add data to the file.  Each time this happens, there will only be one encrypted file so multiple files with same IV and Key will not happen.

Edit: The program using the file will just add data to the end of the file.  From what I could find, this will not change the encryption of the first sections of the file, as the IV is changed based on what was done in the previous block.  Is that correct?

Edit 2: For simplicity, let's say this is a log file that I want encrypted for some reason.  I want to be able to add on to the end of this log while not needing new key/IV.  Since it is the end of a file, I was thinking while decrypting, I will have the next IV for CBC or CFB and use it to begin encrypting the next entry.  As for mutability, I will never have a reason to change anything in the middle of the log/file, only to add on to the end.  I don't know how that lines up with cryptographic mutability/immutability, but that is what I want to do.

Final: I am using CBC.  At the beginning of every line I have a new IV (first 16 bytes are the IV) and the rest of the line is encrypted using that IV.  Thanks for all the pointers.  If anyone sees any major thing wrong with this, please let me know.

You aren't telling us exactly what you plan to do, but plenty enough that we can tell you: no, just no.  The first mistake you're making is that you're talking about "files" in a way that's worrisome in the context of cryptography.  In modern programming parlance, cryptography by default deals with immutable values, not with mutable objects.  But when you talk about "files" in this question it is evident that at least on some occasions you mean a mutable object, one into which different values are written and overwritten at different points in time.

So the cryptographic requirement that you never use the same key+IV pair to encrypt more than one value then applies not to the file as a unit, but to each operation that encrypts a value to be written into the file.

  Is it safe to use the same IV and Key on only one file.

Generally, no.  There are special cases where it's safe, if for example you're using files in a strict write-once never-modify manner, where you're only ever writing to a file at the time you create it.  But that's not what you're proposing to do:

  Is it safe to use the same IV each time I access and add data to the file. Each time this happens, there will only be one encrypted file so multiple files with same IV and Key will not happen.

No.  Each time you wrote to this file you'd be encrypting a different value with the same key and IV, and that violates the IV reuse condition.  Note that the likely practical consequence of this is that your file format will need to be structured to support encryption—for example, you might need to build some notion of "data block" within the file format, so that each data block can be encrypted with a different IV, and the metadata necessary to identify block boundaries and their IVs is present.

  The program using the file will just add data to the end of the file. From what I could find, this will not change the encryption of the first sections of the file, as the IV is changed based on what was done in the previous block. Is that correct?

It sounds like you're looking at some materials that describe CBC mode encryption.  This idea that the IV changes based on what was done in the previous block is likely not something that happens automatically, it'd be something you'd have to understand and implement—which is an error-prone and risky undertaking.  CBC also doesn't provide authenticated encryption, which means that you likely would need to add some sort of message authentication, which makes the whole thing even harder to get right—for example, the recent Efail vulnerability on GPG and email clients hinges on this.

Whatever you're thinking of doing is likely a minefield.


Is it possible to perform a rudimentary asymmetric key encryption algorithm by hand? I have at least three, distinct motivations for having a simple way to use asymmetric key encryption by hand or without modern computers.

First, I was recently demonstrating to a 12-year-old how encryption works. I created some basic cyphers and had him figure them out. (I recommend this; it's quite fun.) Wanting to up the ante, I looked for ways to send messages back and forth using public-private key encryption, and I failed with flying colors.

Second reason for wanting this is that it would really help me understand how asymmetric encryption works. At the moment, I can't figure out a way to do solve this on my own, and I feel that betrays my lack of understanding in the subject.

Finally, (this one may be a stretch) I'm writing a fantasy story, and I'd like to do something unique with the form of exchange. One thought was to have a memorized key that the owner held, which she would use to sign her (paper) payment of 30 units for a loaf of bread, or whatever, combining her key with the shopkeeper's public key. (UPDATE: Note that this gets into digital signatures, rather than asymmetric key encryption. I'm hoping they are related, but if they're not, forget it.)

Any ideas how to accomplish this? If it's simply not feasible, I would appreciate an explanation as to why.

There are two similar questions on this site, but neither of them address asymmetric key encryption, unless I'm more misinformed than I thought:

Is there a secure cryptosystem that can be performed mentally?
What is the most secure hand cipher?

Yes, you can perform rudimentary asymmetric encryption or signing by hand, but no it won't be secure.

Textbook RSA with small enough numbers is easy to do by hand. Diffie-Hellman to exchange a symmetric key is even easier. However, the kinds of numbers for which this is feasible are far from those needed for real security.

There are a lot of other asymmetric systems, but those tend to use even more complicated (to humans) math. Generally asymmetric encryption on a computer is something like an order of magnitude slower than symmetric and like the question you linked shows even secure symmetric encryption is barely doable, maybe, by hand.


Enigma ring settings - is the relative location of the turnover all that matters? I understand that the ring setting of an Enigma rotor changes the alignment between the internal wiring and the letters on the ring. For example, in the diagram below, rotor I has ring setting 2 (B), which causes current entering at position A (the center) to flow through the wiring from Z to J (internal positions) which corresponds to A -> K based on the visible indices on the rotor.
However, we could achieve the same result with ring setting 1 by using Z as the top character, which would cause current to flow from Z->J (internal positions) corresponding to Z->J on the visible indices.
This leads me to believe that the only real impact the ring setting has on the encryption is that it changes the location of the notch (that steps the next rotor) relative to the internal wiring. For plain texts that are long enough to step at least one rotor this will result in a substitution that cannot be recovered by permuting the rotor starting positions alone.
Is there anything else I'm missing?

Mechanically the only effect of the Ringstellung is to determine the rollover points as you surmise. This is easily inferred from descriptions of Enigma models in Alan Turing "Prof's Book where "comic strip" and paper Engimas only use the Ringstellung information to determine rollovers.
Cryptanalytically the effect is that if the message indicator or "window position" of the machine is known but the Ringstellug is not, then nothing is revealed about the "wheel position" or "rod position" as it was referred to at Bletchley Park. There were instances when such information was known, but it was not always easy to bring to bear on the cryptanalysis. A notable exception was the Herivelismus exploitation of human error that noted that common message indicators were often correlated with Ringstellung settings. This was a very useful step in separating out one part of Enigma settings and solving for it separately early on in the war.


Does adding more letters provide added security compared to a standard substitution cipher? Let's say that a substitution cipher had 52 symbols instead of 26. For this, we would include all lower case and upper case letters. This creates a key space of 52! wehere the cipher text can contain both lowercase and uppercase letters. Would this provide more security to a standard substitution cipher?

I would say yes because it's an extra amount of symbols one would have to use and thus creating more options of how many keys can exist. However, I am doubtful because It's still just letters being used. Can anyone explain?

If I understand you correct you mean with "standard substitution cipher" one which has a mapping from one letter to a specific other letter with case being ignored (mapping 26 to 26). And your improved version would map one letter to another letter with case not being ignored (mapping 52 to 52).

This would only be a very marginal improvement if at all. Given how words are structured (upper case almost only at the beginning) the necessary search space could be easily reduced to find out which target characters are mapped from lower case and which from upper case characters. The rest of the analysis can stay the same, i.e. looking for for characters and character combinations which are more common in the original language and mapping these to similar repetitions in the cipher text and thus quickly reversing the mapping.

In short: the system stays broken even if marginally improved.


Is the subset of hash digest collision-resistant if hash function is collision-resistant? Let $H(\cdot)$ be a collision resistant hash function,
$H:\{0,1\}^{\mathsf{poly(n)}} \rightarrow \{0,1\}^n$,

We define a new $H':\{0,1\}^{\mathsf{poly(n)}} \rightarrow \{0,1\}^k$, where we randomly pick $k$ bit positions of $H(\cdot)$.

If we let the adversary, $\mathcal{A}$ , know those $k$ positions, does finding a collision for $H'(\cdot)$ still require $\mathcal{A}$ to ask $2^{k/2}$ queries to $H(\cdot)$ ? Can she do better? Also, if we hide those $k$ positions from $\mathcal A$, is it harder for her?

OK, assuming a setup whereby even if the location of the $k$ bits are unknown the guess or is told by an honest party whether his guess is correct, one can say the following.

Define a collision resistant hash with $n$ bit output as one which requires $O(2^{n/2})$ guesses before finding a collision.

If there was a way of finding a collision in an arbitrary $k$ bit subset in time strictly less than $O(2^{k/2})$ the the overall time would be reduced by attacking, say the $k$ bits and the remaining $n-k$ bits separately (in time strictly less than $O(2^{(n-k)/2})$) getting an overall attack time strictly less than $O(2^{n/2}).$

If $k$ needed to be bounded by some function of $n$ you could get the same result by partitioning into $\lceil n/k\rceil$ subblocks of length $k$ each.

If the multiplicative speedup factor for a k bit block was $2^{-\theta k}$ with $\theta \in (0,1),$ your overall speedup would be
$$
2^{-\lfloor n/k \rfloor \theta k}
$$

approaching

$$
2^{-  \theta n}.
$$
If the weakness was local for a specific $k$ bits, the saving would only be

$$2^{-  \theta k}$$
but still contradict the definition of collision resistant $n$ bit hash function.


Secure way to hash a lookup value I want to securely store a database table that consists of an account ID and a few columns of sensitive data. The data only has value if it can be associated with the account ID. My thinking is to hash the account ID so it can't be associated with the sensitive data.

What hashing algorithm should I used for this situation? Is there an alternative way to store the data that would provide stronger security?

Simply hashing the account ID will not prevent people from associating the account because they can just hash the ID themselves assuming they know the ID and have access to the table.

If the data is so sensitive, you need to encrypt the entire table regardless of how you hide the ID. As I don't know your intentions, it's possible to associate an account entirely on the sensitive data.

If encryption of the table still doesn't suit you, and you are just toying with the idea of trying to disassociate an ID with the table entry, you can try a HMAC (Hash-Based Message Authentication Code) which can take an ID with some secret key to make a difficult to reverse hash. Good Luck!


AES-256 password cracking time My question is kinda simple.

I want to use AES-256 encryption to encrypt my backup.
Using a password like this:
7okufZ308@lB$^KTINX1NWbpdw6rkysxv@giMW5jgI#ZaX*#YwloT3Y$*c*2qVCW

This has 64 chars and I wanted to know what is the possible cracking time for a password like this?
The software I will be using has a custom iteration configuration so I set it to 20,000.

(The server running the encryption software has a lot of cpu power)
Running a quad Xeon with 128GB of ram so I am not really worried about the encryption time.

I am more worried about how long will it take to crack a password like that?

It will happen immediately, because you just posted your password to the internet, where the adversary is watching.

On the other hand, if you can describe the procedure you used to generate it, we can quantify the adversary's probability, knowing only the procedure and not the specific outcome, of guessing the password in one trial.  From there one can quantify the expected cost of an attack that finds it, or the number of trials to find it with any prescribed probability.

For example, if you picked it uniformly at random out of a hat containing

7okufZ308@lB$^KTINX1NWbpdw6rkysxv@giMW5jgI#ZaX*#YwloT3Y$*c*2qVCW
aqfSLH4)K{*zDH:$t6(G^alcSEN\Tbc#8X)W3P[whp%kC@Kn>T#.Q8BQ6=q+![/>
D%]Auqkuel:W4l(/YqBuXSTx7Oh.0]Wq"jly>["t?8wVmUnR+ivCS?<)}+P=-:1N
I am the very model of a modern major passphrase

then the adversary has a 1/4 probability of getting it right in the first trial, and the expected number of trials before the adversary will get it right is 2.

I recommend picking it uniformly at random out of a hat containing at least $2^{128}$ possibilities.

For example, you could flip a coin 128 times and use the outcome as a seed for a CSPRNG from which you sample octets, rejecting those that do not encode graphic characters in US-ASCII, until you have collected 64 of them.

That's not a very efficient use of the password space, though: the adversary's most efficient attack is probably on the 128 coin flip outcomes rather than on the password.  So you could safely bring your password down to 20 US-ASCII characters.

Alternatively, if you want it to be more memorable, you could pick a sequence of 10 words independently and uniformly at random out of a list of 7776 of them, with the help of diceware and a standard household appliance, or with the same rejection sampling technique on a CSPRNG if your name is not Raphael Weldon.

Note that for a uniform distribution on $2^{128}$ possible passwords to be safe against multi-target attacks, you must be sure to combine your password with a hefty salt.  Otherwise, or if you are concerned about quantum computers, it may be prudent to double these numbers (256 coin flips, 40 US-ASCII characters, 20 diceware words) to bring it up to $2^{256}$ equiprobable possibilities, or at least bring it up to $2^{192}$.


CPA vs CCA attack of an encryption scheme Semantic Security is a concept that made New Cryptography, (that is Cryptography invented after 1975) into a rigorous science. It connected old cryptography (that is Shannon's information theory-based cryptography) to New Cryptography.

Suppose that we use a randomly chosen 128-bit IV  to encipher a 128-bit message $m$, and AES with a randomly chosen key $k$, to generate a 256-bit cipher-text computed as: $IV \| \mathrm{AES}(k,(IV \oplus m))$. Here $\|$ means concatenation and $\oplus$ means exclusive or.

Why is this scheme semantically secure against an eavesdropper, but not  against an active attacker? -- i.e why is it secure against Chosen Plaintext Attack, but not against Chosen Ciphertext Attack?

To answer the question, its necessary to invoke the following security definition, which requires that for any encryption scheme $\pi$ to have indistinguishable encryptions under chosen ciphertext attack (viz., for the scheme to be CCA secure), the following condition, which I'll describe, must hold in the so called "CCA distinguishing game" (throughout, I'm using the notation of Katz and Lindell, and the CCA property is more expansively described in their text Intro to Modern Cryptography, 2nd ed. CRC Press):

$\textbf{Pr}[\textbf{PrivK}_{\mathcal{A},\pi}^{cca}(n) = 1] \leq 1/2 +  \text{negl}(n)$

Here $\textbf{Pr}[E=e]$ denotes the probability that experiment $E$ has outcome $e$, and $\textbf{PrivK}_{\mathcal{A},\pi}^{cca}(n) = 1$ denotes the outcome where the CCA adversary $\mathcal{A}$ wins the CCA distinguising game ($K$ is an encryption key of length $n$ and $\text{negl}(n)$ is a "negligible'' function in $n$). Also, throughout we assume $\mathcal{A}$ is PPT.

(this definition needs to be expanded to allow for encrpytions and decryptions of multiple messages in an analogous vein to the "Left-Right" or LR-Oracle CPA security game described here - https://cseweb.ucsd.edu/~mihir/cse207/w-se.pdf, but the above definition is sufficient for illustration purposes)

So to restate, the CCA security definition requires that the above condition for the scheme $\pi$ must hold in the CCA distinguishing game $\textbf{PrivK}_{\mathcal{A},\pi}^{cca}(n)$ in order for the scheme to be CCA secure. The rules of the game are that the adversary $\mathcal{A}$  has oracle access to the encryption and decryption functions, and it proceeds by her selecting 2 equal length messages $m_0$ and $m_1$  and submitting them to the encryption oracle, which flips a coin and based on the outcome sets a bit $b$ to either 0 or 1. Based on the value of $b$, the oracle encrypts either $m_0$ or $m_1$ and returns the resulting ciphertext $c$ to $\mathcal{A}$ (which is also called the challenge ciphertext). $\mathcal{A}$ can continue to invoke the encryption and decryption oracle on any messages other than the challenge ciphertext. At the end, $\mathcal{A}$ outputs a bit $b^{\prime}$. The adversary wins the game, which is denoted by the condition $\textbf{PrivK}_{\mathcal{A},\pi}^{cca}(n) = 1$ when $b^{\prime} = b$.

Now consider a CPA secure counter mode encryption scheme such as AES-128-CTR. $\mathcal{A}$ can choose messages $m_0 = 0^{128}$ and $m_1 = 1^{128}$ and submit them to the encryption oracle. Suppose that the oracle sets $b = 0$ and returns the challenge ciphertext $c$. The adversary can then flip the first bit of c resulting in a ciphertext $c^{\prime}$. Since $ c^{\prime} \ne c$, $\mathcal{A}$ can legitimately submit this to the decryption oracle which returns the plaintext $10^{127}$, at which point $\mathcal{A}$ outputs $b^{\prime} = 0$ and can trivially win the game every time thereby violating the CCA security condition $\textbf{Pr}[\textbf{PrivK}_{\mathcal{A},\pi}^{cca}(n) = 1] \leq 1/2 +  \text{negl}(n)$


Encrypting decryption key What's that property called when a scheme is secure even if you encrypt the decryption key? Some schemes have problems when your plaintext is the decryption key (or just the key if symmetric).

It is called circular security. It is problematic because it is not captured by the usual security definitions. I.e., even if an encryption scheme is proven secure by some regular definition, it is usually not a given to be circular secure.

To see why consider, for example, the usual definition of semantic security for a public-key encryption scheme $\Pi = (Gen, Enc, Dec)$: We say that $\Pi$ is semantically secure if all adversaries $A$ has at most negligible advantage (in security parameter $\lambda$) in the following security game:

We sample $(pk, sk) \leftarrow Gen(1^\lambda)$, and send $pk$ to $A$ (here $pk$ is the public key and $sk$ the secret decryption key).
$A$ outputs messages $m_0$ and $m_1$.
We sample $b \leftarrow \{0,1\}$ (a random bit), and send $c \leftarrow Enc(pk,m_b)$ to $A$.
$A$ outputs a bit $b'$ and wins if $b = b'$.

The problem here is that this only talks about security for some messages $m_0$ and $m_1$ that $A$ can pick. However, since $A$ does not know $sk$ there is negligible probability that she will pick $sk$ as a message (in fact if $A$ could pick $sk$ with non negligible probability the scheme would not be secure!). So using this definition we cannot say much about the circular security of the scheme.


Serpent vs AES,, theoretical security In the lets-choose-the-next-aes contest in 1998, they chose Rijndael because of speed. Now, not taking speed into account, is Serpent more secure or not? Since it has 32 rounds (of course that's not that useful if the round algorithm isn't secure,) I thought it's more secure, since it has the same block size, key sizes AND more rounds. But I really don't know the details, so if you threw away efficiency on x86 CPUs and ease of implementation, then Serpent would be more secure, right? If yes, is it superior, or just a tiny bit more secure?

The number of rounds does not directly influence security; it depends at least as much on the complexity of those rounds. That said, it is possible to use the percentage of rounds for which there are attacks as an indication on how much crypt-analysis has advanced (disregarding those attacks that are worse than brute force, of course).

One tricky thing with this is memory usage; many attacks are still better than the time-complexity of brute force, but have impossible memory requirements. I don't think there is any objective way to weigh memory-complexity and time-complexity.

Another thing to notice is that these attacks are far from practical; you can possibly see them as indication if other / more advanced attacks are possible. Of course, if this is true cannot be predicted, but for sure some attacks are more likely to be "extended" than others as well.

Still, with that said, for Serpent-128 it seems that 11 out of 32 rounds have been shown to be weak in an attack. For AES-128 there is the biclique attack on the full cipher. This attack however only brings down the attack complexity to $2^{126.1}$; having a complex attack that has a smaller than 4 times advantage over a brute force attacks doesn't say much. Otherwise, there are attacks for at least 7 rounds out of the 10 used for AES-128 (the other key sizes use a larger number of rounds).

So in that sense Serpent should be considered to be much more secure than AES; $\frac{11}{32} \ll \frac{7}{11}$ after all. AES is however also more than twice as efficient. In that sense Serpent with 16 rather than 32 rounds would probably have fared better at the competition. However, that's just for the minimum key sizes. If you look at AES-256 then you would have all the security you may need (9 out of 14 rounds or $2^{254.3}$ for the biclique attack) - and still be faster than even Serpent-128. And that's without hardware acceleration. Note that I've disregarded related key attacks on AES-256 in this scenario.

The notion on Serpent that "It is build like a tank" (Cryptography Engineering: Design Principles and Practical Applications) still seems to hold. Note that there haven't been many breakthroughs on either cipher in the last couple of years; research seems to have moved on.


Generating Private Keys First of all I want to say that I have exactly 0 knowledge how I can write something in Python. But I have some knowledge in math especially finite fields.
That's why I want to learn more in writing tools for a Project.

This is the list what the tool should do:

generating random private keys.
in a range ( which I can change )
give out the hex X Point
compare with given X Point

Now the question: is that too difficult for a newbie? And is C++ better for that instead of Python?

You should definitely stick with Python or my fav, SageMath (which is Python based) when playing with elliptic curve crypto.

The private key is generally just a large scalar value, which when multiplied with the curves base point (in other words when we repeatedly double the base point) the resultant point is the public key.

There are subtleties that aren’t captured here, that vary across curves and production implementations.

I’d start in SageMath it’s an easy place to begin. Check out this link for a starter.


How to calculate random factor in Paillier cryptosystem? I am currently learning paillier cryptosystem,and have two questions about random r.I use the characteristics of homomorphic addition to obtain the product of two ciphertexts C and the corresponding plaintext P.

Assuming I know the private key,how can I calculate r？(I want to know more details about how to calculate r)
If I get r and send it to another person who only knows the public key, can he use (P,r) encryption to get ciphertext C to prove that my decryption operation is correct?

Let $C$ be the ciphertext and let $N$ be the public key. Thus, $C=(1+N)^m \cdot r^N \bmod N^2$ for some message $m$. We want to recover $r$ given the private key $\phi(N)$. This can be achieved by first computing $C'$ as an encryption of 0. To do this, decrypt to get $P$ and then take $C'=C\cdot (1-P\cdot N)\bmod N^2$ (this is scalar subtraction). Next, compute $M = N^{-1}\bmod \phi(N)$ and finally we have $r = {C'}^M\bmod N$. This works since ${C'}^M = r^{N\cdot M} = r^{1+k\cdot\phi(N)} = r \cdot (r^{\phi(N)})^k= r \bmod N$ since the order of $\mathbb{Z}_N^*$ is $\phi(N)$.

Regarding your second question, if you give someone $P$ and $r$ then they can just re-encrypt using $r$ and compare to $C$. This would prove that decryption is correct, but is not zero-knowledge. In case zero-knowledge is needed, this is also possible (and very efficient) in Paillier.


What EC curve is used by Apple iOS platform? I can't find information about EC curve used by Apple's iOS platform. The algorithm name that I could see in their docs is:
eciesEncryptionCofactorVariableIVX963SHA256AESGCM

However, there is no any explanation what it refers to. I've tried to find info about cofactor IVX963 with n/a so far. I read somewhere that Apple has adopted DJB's Curve25519. Is this the one that iOS uses as well?
If not, probably you can provide some pointers like NIST refs or anything else in public domain explaining what this is exactly.
Answer below is good (I've accepted it) and it does provide a lot of information, but clarification is still required.
The only ref that links curve in question with p256r1 is from a private blogger who primarily talks about generating curves of different types. While p256r1 has been generated in the demo, he doesn't know what other curves can be generated this way, nor it's clear how his curve generating scripts are related to the curve in this post.

This rough demo script isn’t set up to handle curves other than P256v1

More information is needed

A more official link that explains what this curve is
Equation type, domain parameters, etc.

I hope, it's not P256r1/v1
Please also note that the recommended curve is not even available in iOS 14.1, which is very recent

Type 'SecKeyAlgorithm' has no member 'kSecKeyAlgorithmECIESEncryptionCofactorVariableIVX963SHA256AESGCM

UPDATE I found the new link provided by @kelalaka very useful and practical, especially this part of it:

import Sodium

let sodium = Sodium()
let curve25519KeyPair = sodium.box.keyPair()
let privateKey = curve25519KeyPair!.secretKey
let publicKey = curve25519KeyPair!.publicKey

This is what everyone should use in EC domain, not the old and obscure Apple's CommonCrypto

Apple's CryptKit Suite
Since Apple's actual documentation is sparse we need to look for all available source;
There is apple/swift-crypto Github page that we can find the source code and cryptokit page also provides only a list.

Swift Crypto is an open-source implementation of a substantial portion of the API of Apple CryptoKit suitable for use on Linux platforms. It enables cross-platform or server applications with the advantages of CryptoKit.

ECDH.swift implements the below standard NIST 800-186 curves

P256 + Signing
P256 + KeyAgreement
P384 + Signing
P384 + KeyAgreement
P521 + Signing
P521 + KeyAgreement
P256 + DH
P384 + DH
P521 + DH

The curves P256 (secp256r1 in SECG, prime256v1 in ANSI X9.62 and P-256 in NIST) and 384 (secp384r1) are in NSA Suite B
The Secp means: Standard for Efficient Cryptography Elliptic Curve Domain Parameters

The key derivation is HKDF

Signing

ECDSA Signing with NIST curves P256|P384|P512.
EdDSA Signing EdDSA signature over Curve25519. Not a standard naming there. I should be Ed25519.

Keys

Curve25519 key agreement

From the BoringSSL support lists

Curve25519 key agreement

For the security of these curves ( possibly a backdoor) see these questions from our site.

Should we trust the NIST-recommended ECC parameters?
Is there a feasible method by which NIST ECC curves over prime fields could be intentionally rigged?

The below from the iOS page SecKeySizes

secp192r1: 192-bit ECC Keys for Suite-B from RFC 4492 section 5.1.1.
secp256r1: 256-bit ECC Keys for Suite-B from RFC 4492 section 5.1.1.
secp384r1: 384-bit ECC Keys for Suite-B from RFC 4492 section 5.1.1.
secp521r1: 521-bit ECC Keys for Suite-B from RFC 4492 section 5.1.1.

There is also iOS-compatible ECIES implementation in Java

kSecKeyAlgorithmECIESEncryptionCofactorX963SHA256AESGCM
Little digging about the constant;

If we take a look at the corresponding constant kSecKeyAlgorithmECIESEncryptionCofactorX963SHA256AESGCM defined in SecKey.h (see here for example) then we can see that this algorithm is considered “legacy” and the recommended one is SecKeyAlgorithmECIESEncryptionCofactorVariableIVX963SHA256AESGCM instead (in Swift it’s eciesEncryptionCofactorVariableIVX963SHA256AESGCM).

and the below from darthnull.org/security

ECIES: Elliptic Curve Integrated Encryption System - an open standard that defines exactly how to do what we’re about to do
Cofactor: Include the elliptic curve’s “cofactor” when completing the Diffie-Hellman key agreement process
X963SHA256: Use the ANSI x9.63* key derivation function (KDF), with SHA-256 as an underlying hash function
AESGCM: For the final symmetric encryption, use AES in Galois Counter Mode (GCM), a form of authenticated encryption

The curve is SecP256R1 (This claim needs to be verified!!!)
The Secure Enclave
Apple describes the Secure Enclave as "a representation of a device’s hardware-based key manager. Secure Enclave only have

NIST P-256 signatures and key agreement as of 2020.

*real ANSI X9.63 is here


Homomorphic encryption for vector addition Building on the question and answer from Addition-only PHE in F# which ponders homomorphic cryptosystems to navigate, relatively, a single dimension without revealing absolute position (an encrypted counter?), I am now interested in extending this to multiple dimensions, the ability to do vector addition in HE.  i.e. $\varepsilon((x, y, z)) \oplus \varepsilon((a, b, c))$.

As in the referenced question, it is desirable to me that $\oplus$'s time complexity is just hyperlinear to the distance $|| (x, y, z) - (a, b, c) ||$.  One way to enforce this (but not the only way, perhaps) is to provide only 6 pre-computed $\varepsilon((a, b, c))$ ciphertexts representing unit relative moves.  If this is complete, then it seems to me that the key, whether symmetric or asymmetric, can be discarded.  I don't particularly like this because it has a bias in moving parallel to axes.  This paragraph has been causing a lot of confusion in the comments, but I'm too dense to understand the confusion.

If all 26 precomputed "cell" moves are provided, then moving diagonally has the bias.  Ideally, the time required should be proportional to the distance moved.  The complication here is that the time complexity for $\varepsilon(\overrightarrow{X}) \oplus \varepsilon(\overrightarrow{A})$ likely equals $\varepsilon(\overrightarrow{A}) \oplus \varepsilon(\overrightarrow{X})$, and of course since we'd know the magnitude of $\overrightarrow{A}$ then the time of the $\oplus$ operation would indicate the magnitude of $\overrightarrow{X}$ which is bad and would already be absent from any cryptosystem.  The only improvement I can think of is an FHE encoded custom $\oplus$ routine that cleverly incorporates the appropriate penalty.

The system should be deterministic - that is, there is only one ciphertext of any absolute position.

Is there an upper bound on the size of the ciphertext for, say, any 192-bit vector?  I believe that ciphertexts will not necessarily be the same width as the plaintext.  But then maybe that's only true for non-deterministic systems.

(... Otherwise,) if only the ciphertexts are seen, how easy is it to discover the bit width of the vector? (short of finding the periodicity which is not practical)

I assume that any $\oplus$ is blind to arithmetic overflow and just wraps around, which is desirable here.

I think the function I'm asking for is just a scrambled/hidden mapping between $\mathbb{Z}^3$ spaces.  Is this an unnecessarily complicated way of going about that?

$\varepsilon((0,0,0))$ cannot be obtained from  $\varepsilon(\overrightarrow{X}) \oplus (\varepsilon(\overrightarrow{A}) \otimes -1)$ or $\varepsilon(\overrightarrow{X}) \ominus \varepsilon(\overrightarrow{A})$ if $\ominus$ and  $\otimes$ are not available.

Thanks!

Edited to incorporate some of the comments discussion

New approach?

What about this new Indistinguishability Obfuscation (1, 2)?  Could a quine-like program, but one which takes a direction symbol as input, do the trick?  Each executable contains an embedded (and now secret) "point".  When the program is run, it outputs itself but with a modification of the resulting "point" instead of the exact original.  The program would have to also know how to indistinguishably obfuscate itself.  Are all the necessary operations bootstrappable like that?  The obfuscated programs are the coordinates.

How compact could they be?

A very simple way to do something like this is by using the following construction:

$$E^*(\langle x,y,z \rangle) = \langle E(x), E(y), E(z) \rangle,$$

where $E$ is an additively homomorphic cryptosystem.  (To avoid attacks, use three different public keys to encrypt the three components.)  Now $E^*$ has your desired homomorphic property.

I don't understand what the hyperlinear business is, so I've ignored that part.

The problem with this construction is that the three components are separable.  For instance, given $E^*(\langle x,y,z \rangle)$, it is possible to recover $E^*(\langle x,0,0 \rangle)$.  Or, given $E^*(\langle x_1,y_1,z_1 \rangle)$ and $E^*(\langle x_2,y_2,z_2 \rangle)$, it is possible to compute (say) $E^*(\langle x_1+x_2,y_1,z_1 \rangle)$.  These are values that it might not be possible to derive with just $\oplus$.

So, can we do better?  That's what I'll answer next.

Can we do better?

The answer is probably, it depends.  There are a bunch of situations where it is simply not possible to do better -- it's not possible to achieve what you want.  To identify whether it will be possible to achieve what you want, we need to dig a bit deeper into the specific details of exactly what you want, in greater precision.

Suppose we want an encryption scheme

$$E^*: \mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/q\mathbb{Z} \times \mathbb{Z}/r\mathbb{Z} \to R$$

that is additively homomorphic on $\mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/q\mathbb{Z} \times \mathbb{Z}/r\mathbb{Z}$.  In other words,

$$E^*(\langle x_1,y_1,z_1 \rangle)\oplus E^*(\langle x_2,y_2,z_2 \rangle) = E^*(\langle x_1+x_2,y_1+y_2,z_1+z_2 \rangle),$$

and $\oplus$ is the only method we have for combining ciphertexts.

If $p,q,r$ are three different numbers that are pairwise relatively prime, it is definitely not possible to do what you want.  Here's why.  Given $E^*(\langle x,y,z \rangle)$ and an integer $n$, it is always possible to efficiently compute $E^*(\langle nx,ny,nz \rangle)$ using just $\oplus$ (use repeated doubling).  Set $n_1=r \times (r^{-1} \bmod q)$.  Then given $E^*(\langle x,y,z \rangle)$, we can compute $E^*(\langle n_1 x,y,0 \rangle)$ via the formula

$$E^*(\langle n_1 x,n_1 y,n_1 z \rangle) = E^*(\langle n_1 x,y,0 \rangle),$$

using that we know how to get the left-hand side of the formula above from $E^*(\langle x,y,z \rangle)$ and $n_1$.  Next, set $n_2 = q \times (q^{-1} \bmod p) \times (n_1 \bmod p)$.  Now given $E^*(\langle n_1 x,y,0 \rangle)$, we can compute $E^*(\langle  x,0,0 \rangle)$ using the formula

$$E^*(\langle n_2 n_1 x,n_2 y,0 \rangle) = E^*(\langle x,0,0 \rangle).$$

So in this case, given $E^*(\langle x,y,z \rangle)$, we were able to compute $E^*(\langle x,0,0 \rangle)$ using just the operation $\oplus$.  This shows that if $p,q,r$ are mutually co-prime, then it's guaranteed that the three components will be separable, no matter what we do.  So, in this case you might as well use the very simple construction shown at the top of my answer.

What if $p=q=r$?  This looks like one case where it might be possible to achieve your desired property.  However, we have to be a bit careful.  If we know ciphertexts $E^*(\langle x_1,y_2,z_3 \rangle),\dots,E^*(\langle x_k,y_k,z_k \rangle)$ where the linear span of these three vectors is all of $\mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/p\mathbb{Z}$, then we can separate the three components and we're back to something that is no better than my very simple construction at the top of the answer.

In conclusion, it's only going to be possible to achieve what you want if you pick $p,q,r$ very carefully and if you severely limit what ciphertexts are available to the eavesdropper.  Moreover, the specific construction might depend on your specific choice of $p,q,r$.  Did you have a strategy to deal with these challenges?  You might want to edit your question to tell us about what values of $p,q,r$ you had in mind and how they'll be chosen and how they're related (mutually different, mutually co-prime, all the same, whatever).


Is there any Information on the "Modular Approximate Greatest Divisor" problem? The Approximate Greatest Common Divisor (AGCD) problem is the difficulty of obtaining the value $\ p\ $ when given samples of $\ pq_i + e_i$ for secret values $p, q_i, e_i$.

I would like to know how the difficulty of the problem changes when modular reduction is incorporated.

Specifically: is the problem of obtaining $\ p\ $ from samples of $\ pq_i + e_i \bmod x$ with secret $\ p, q_i, e_i$ and public $x$ equivalent in hardness to the previously mentioned variant of the problem that operates over integers?

I could not find information on this version of the problem when searching for the term "Modular AGCD", but I am not sure what to refer to it as. It may a negligible difference between the two that does not warrant classification as a separate problem, but I am not sure. Intuitively, it seems that the variant with the modulus would be more difficult to solve. But I would like quantitative details on any differences, if there are any.

Edit

Poncho's answer highlights the fact that the sizes of the parameters are important when discussing the hardness of the problem. I am interested in the problem with the following parameter sizes:

$x$ is a 1792-bit prime
$p$ is a uniformly random 1792-bit integer
Each $q_i$ is a 1536-bit integer with the 1280 most significant bits uniformly random

The next lower 255 bits are set to 0, and the least significant bit is set to 1

Each $e_i$ is a 1024-bit random integer

Specifically: is the problem of obtaining $\ p\ $ from samples of $\ pq_i + e_i \bmod x$ with secret $\ p, q_i, e_i$ and public $x$ equivalent in hardness to the previously mentioned variant of the problem that operates over integers?

Actually, if $p$ is relatively prime to $x$, and the $q_i$ values are uniformly distributed over $[0, x-1]$, then it is strictly harder than the AGCD problem, in that it is informationally secure (rather than computationally secure), that is, even if we assume that attacker has unbounded computational capabilities, he still cannot recover $p$.

The demonstration is actually fairly simple; even if we assume that attacker knows $e_i$, then for any sample value $s = pq_i + e_i \bmod x$, for any potential value $p'$, there exists a unique $q'_i$ value, namely, $p'^{-1}(s - e_i) \bmod x$ that would yield the observed sample $s$, hence the attacker gains no information about the relative probability of any candidate value $p$ (except for whether it's relatively prime to $x$)


HW acceleration for Camellia cipher (x86_64/AES-NI/AVX2) Modern processors support hardware acceleration for various crypto functions such as AES directly, or general vector operations which can be used in crypto functions, such as SSE SSE2 SSSE3 AVX.

On my machine, I can see the difference in speed between AES in software and in hardware, which gives speeds up to 5 times faster:

openssl speed -evp aes-256-cbc
openssl speed      aes-256-cbc

(Note: I am using OpenSSL here only as an example, because it is easy to demonstrate.)

Also, the Linux kernel can be compiled with support for these functions as well. If so, all encryption in kernel space (for example IPsec, dm-crypt) can take advantage of these fast hardware instructions.

Again, the kernel compiled with AES-NI support is many times faster when uisng aes in software only.

I have noticed that there is also hardware support for the Camellia cipher and it looks as if Camellia could use the same instructions as AES, namely AES-NI and AVX.

However, I am unable to test/confirm this.

openssl speed      camellia-256-cbc
openssl speed -evp camellia-256-cbc

I see no difference in speed when tested with OpenSSL and I suspect the hardware acceleration is not being used for Camellia.

My cpu supports all above mentioned instructions: AES SSE SSE2 SSSE3 AVX.

Is it possible to speed up Camellia by using hardware instructions on supported cpu, same as with AES?

The obvious answer to your question is "yes". The kernel mode implementation pointed to by otus clearly shows that it can be done.

That it can be done doesn't mean it gets done however. Many Google searches for sourcecode don't show any OpenSSL code that implements this functionality. In general, OpenSSL doesn't rely on the crypto code of the kernel. So, that means the hardware acceleration is not available. In general you should not expect that hardware-crypto availability is automatically reflected in (higher level) API's.

To resolve this you could either implement an engine yourself or ask for a feature request at OpenSSL. Note that Camellia interest seems to be dwindling. Nobody picked up the - relatively new - feature request for Camellia in authenticated ciphers or ciphersuites so they got closed.

It seems that Camellia is seen as a "vanity algorithm" by many; let's not do AES because it is too American, but do something almost identical instead.


How secure is a password generator that runs SHA256 on a passphrase I was looking into how password managers work and it seems to me that they all store the passwords (albeit encrypted).
How secure would a scheme be where the password manager always generates the password when you ask for it based on your master password and some salt that can be generated from the website name. For example something like
password=sha256("mymasterpassword"+md5("facebook"))
Trivially it seems no more vulnerable than the normal scheme, the attacker still needs to guess my master password, so what security flaw am I missing?

Password managers with similar schemes do exist, and are called "deterministic password managers". While the idea does generally does work, this blog post names some rather big practical disadvantages, two of which I'll summarize:

Possibility of master passphrase compromise: If your master secret is ever compromised, all your passwords are now immediately compromised. Compare a classical, disk-based password manager: Here, an attacker would need access to the file as well as to the master passphrase.
Also, with just access to a single password (as well its seed, i.e. which site is was used for), an attacker can start trying to crack the master passphrase by brute-force. Especially a fast hash function like SHA256 instead of a purposefully slow key derivation function like Argon2 or PBKDF means that your master passphrase better be really good - so it would be advisable to use a randomly generated cryptographic key instead of a human-generated password*. This key would need to be stored somewhere, defeating the whole point of the scheme.

Without stored state, you loose some very important functionality: Once generated, it's now impossible to change a password, without memorizing a changed seed. For example, if your facebook password got compromised, you'd now have to remember typing in "facebook1" instead of "facebook". This is bad, because it discourages users from changing passwords they suspect might have been compromised.
Additionally, password requirements differ from site to site. Some might require special characters, some might forbid them altogether. To accommodate this, you'll also have to remember the exact password generator settings for each website.

In conclusion, your idea is probably sound from a cryptographic standpoint, but only as long as the master passphrase contains enough entropy (that amount being substantially higher than for online-brute-force-only attack scenarios). But in the real world, there are a lot of security and usability considerations making it generally not very practical, compared to a normal password manager.
* Of course, one could generate a rather long random passphrase that is both high-entropy and human-readable. But it might very well exceed your expectations for what is a reasonable length for a password.


How to break an unknown ciphertext - transposition of some kind I've been challenged to crack a code. All I know about it is that is was hand-enciphered, and that it is a transposition cipher of some kind. When I was given it, I started plugging it into my permutation decryption engine. As you can guess, when I realised that the ciphertext was 26 letters long, meaning permutations numbering $26!$ I stopped the program and scratched my head. What would the most efficient way to crack this be?

Unable to find an answer, I turned to Crypto.SE. Can anybody explain an efficient way to crack the cipher?

If you know for sure that it is a transposition of some kind you can chek
the average frequency with which the various letters appear in the natural language of the plain text and then compare them to the frequencies of letters in the cyphertext. You can easily find this data on google, here is the example for english.
This method works only if the transposition of the letters is always the same, for example: letter $n$ of the ciphertext = letter $n$ of the plain text + 10.
If your key use columnar transposition you need to work out the column lengths by dividing the message length by the key length. Then you can write the message out in columns again, then re-order the columns by reforming the key word.


Protection of Elliptic Curve Implementations against side-channel attacks Recent fast elliptic curve implementations, for example a presentation at Eurocrypt 2014 (earlier presentation slides, the paper) talks about protection against only timing attacks. Why only timing attacks?

If these methods are implemented in hardware then I think it should have been protected against power attack and fault attack also.

It all comes down to your threat model, right? Just because an implementation is done in hardware does not mean that power and fault attacks must be considered. If I host the hardware in my secure facility with armed guards at the door, but the hardware is connected to a machine which is connected to the internet, I might feel that it is okay to not be concerned about power and fault injection attacks. On the other hand, if my hardware is being deployed "behind enemy lines" where it could be captured, you better believe that I should be worried about those sorts of attacks.


Why does LastPass hash their passwords with PBKDF2 this way? LastPass is a password manager that I am sure many of you are familiar with. I have been studying LastPass's source code a bit. From their FAQs and what I can gather from their source code, the way they derive and store your encryption key is as follows:

The client application derives your encryption key using standard PBKDF2 with your master password, a variable number of iterations (5000 is the default, but you can set whatever you like), and your email address as the salt.

The resulting encryption key is used for encrypting and decrypting your vault information.

For the purposes of authentication with their servers, they then take that encryption key and hash it using PBKDF2 again, this time using the previously generated encryption key as the password input and the user's master password as the salt. This is done with just 1 iteration.

The resulting hash is then transmitted to the LastPass servers where (according to their FAQs since I cannot see their server source code) they again use standard PBKDF2 with a random salt and 100,000 iterations.

Pseudo code

pbkdf2(algorithm, password, salt, iterations, bytes)

Client

enc_key = pbkdf2(sha256, master_password, email, client_iterations, 32)
key_hash = pbkdf2(sha256, enc_key, master_password, 1, 32)

Server

stored_hash = pbkdf2(sha256, key_hash, random_bits, 100000, 32)

Questions

I am confused about the key hashing process that they are doing. It appears that they are using PBKDF2 as a means for computing a SHA256 hash to protect it during transmission to their servers.

Can you explain what using PBKDF2 with 1 iteration is doing in the above?
Is this the same as just doing something like a HMAC SHA256 hash?
Are there any concerns with something like a compromised server receiving this hash and being able to derive anything from it about the original encryption key or master password (prior to the stored hash being computed)?

Can you explain what using PBKDF2 with 1 iteration is doing in the above?

  Is this the same as just doing something like a HMAC SHA256 hash?

This is mostly HMAC-SHA256, but you can declare how many bits of derived key you want. I assume it is used this way for ease of implementation (it's easier to have one working implementation of PBKDF2 than many primitives arranged in complex way).

  Are there any concerns with something like a compromised server receiving this hash and being able to derive anything from it about the original encryption key or master password (prior to the stored hash being computed)?

No, this is nearly impossible to do because as long as SHA256 is one way. It is very unlikely that SHA256 will be broken in such way (MD5 and SHA-1 have collision attacks only). If anything, this will leak if password was changed, because there is no random part added before it is sent to server, which is design flaw (unless they do something extra which you omitted).

Also, as SEJPM noticed, it is weird that only 5k iterations are done on user device and 100k iterations on their server. This would put server in better position to perform a brute-force attack. However, 5k iterations on client seem very low for most computers, and probably should be adjusted anyway.


Does any popular symmetric cipher allow for direct re-ciphering? Let's say I have some data ciphered using key, $K_1$, in to format $D_1$, which I want to convert into format $D_2$ that can be decrypted using $K_2$.

So I know $D_1, K_1$ and $K_2$.

I want to convert $D_1$ to $D_2$ but I want to avoid actually decrypting the data $D_1$ into its plaintext form. Is it possible to do so for any of the popular symmetric encryption algorithms such as DES, 3DES, ARCFOUR, AES, Camellia, RC2, IDEA, SEED? I am guessing it's not possible, but still thought I'd ask, since I don't know much about most of these methods.

A reason for doing something like this may be in an enterprise setting  where companies typically create their own https proxies and act as MITM. If they only want to analyze the headers of the http packet but not the body itself then they could only decrypt a portion of the data and pass on the rest of it. This way they can be minimally invasive given their security policies.

Yes, this is possible for all synchronous stream ciphers where your plaintext $M$ is simply XoRed with a keystream $K_1$ to produce the ciphertext: $D_1=M\oplus K_1$ because then you can simply XoR again the ciphered data $D_1$ with $K_1\oplus K_2$ together to get: $$D_2= D_1 \oplus K_1\oplus K_2 = M \oplus K_1\oplus K_1\oplus K_2 =M\oplus K_2.$$

So modern stream ciphers such as Chacha20, but also older such as AES-CTR, support this.

This also means that you can also use this with any block cipher in CTR mode of operation, so Camellia, IDEA, AES etc. are all fine.

However, other stream cipher have ciphertext dependent operations, like AES-CFB, and won't allow for it as easily. Besides, if you want to have actual security you should also worry about authenticity and integrity of your data, which means you have to HMAC (or CBC-MAC) again with the new key afterwards... AEAD schemes won't typically support "re-keying" of the cipher.

It might also be possible for other ciphers, in ways similar to those explained in this recent answer.

There are also other malleable schemes which might allows you to change a part or all of the secret material without decryption, provided you know both the old and new secret material, for instance it is easy in RSA to change the public & private exponents, but then you need to use the same $N=pq$, so anybody knowing the factors $p,q$ would still be able to crack both private exponent, being given the public exponents.