Encryption using deterministic CSPRNG as secure as CSPRNG

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

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

And the additional step:

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

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

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

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

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

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

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


What is wrong in the following algorithm for computing a hash function using RSA?

Hash functions must be public, so if you want to use RSA as a hash function you should fix $K$. Now let $n$ be the RSA modulus and $H$ denote an RSA hash function. We have

$$H(M)=H(M+n)$$

so this function is not second preimage and collision resistant.
Also, this system is not first preimage resistant (with known public and private key):
Let $M^k=h \pmod n$ and $h_t$ denote the first $t$ bit of $h$, so $H(M)=h_{240}$.
Now suppose $e$ is the public key and $M'={h_{240}}^e \pmod n$. We have:

$$H(M')=h_{240}$$

So we found an inverse for this hash function and this is not preimage resistant.


An unpredictable PRG is secure (Theorem Yao'82)

This lecture  (PDF) has the solution in section 3.

Here's my informal explanation of the proof:

We have an unpredictable PRG $G$. We want to show that $G$ is secure, or in other words indistinguishable from $R$ (I'll use = to mean indistinguishable whenever referring to two distributions for the remainder of the proof).

Using the notation that $G_k R_{n-k}$ means get the first $k$ bits using $G$ and generate the last $n-k$ bits totally randomly, it suffices to show that $G_{i-1} R_{n-i+1} = G_{i} R_{n-i} \ \forall i$, since then $G_n = G_{n-1} R_1 = G_{n-2} R_2 ... = R_n$ by a trivial induction, and $G_n$ is $G$, $R_n$ is $R$ by definition.

So we want to show that for all $0 \le i \le n-1$, $G_{i-1} R_{n-i+1} = G_{i} R_{n-i}$.

Assume for sake of contradiction that this doesn't hold for some $i$. That means there is some statistical test $A$ which can distinguish $G_{i-1} R_{n-i+1}$ from $G_{i} R_{n-i}$, or a statistical test where the advantage is non negligible. This means that either $A$ is more likely to equal $1$ when using $G_{i} R_{n-i}$, or more likely to equal $0$ when using $G_{i} R_{n-i}$, without loss of generality let's say $1$. So pick a random bit $b$ and run $A(G_{i-1} b R_{n-i})$.

If it returns $1$, then we'll guess that $b = g_i$ (since $A$ is more likely to equal $1$ when the first $i$ bits come from $G$); if it returns $0$, we'll guess that $b \neq g_i$. This is just a guess, but since there's a non-negligible advantage, the odds that we guessed correctly are greater than $\frac 1 2$ by the same non-negligible factor.  This means we can predict the $i$th bit from the first $i-1$ bits, which contradicts our assumption that $G$ is not predictable.


Why Authenticated Encryption the same message again is not secure?

Recall the definition: a cipher is AE-secure iff it is secure against chosen ciphertext attacks and has ciphertext ingegrity. Try going through the attack games with $(E_1,D_1)$ and $(E_2,D_2)$: if the adversary succeeds, can he succeed for $(E,D)$?

It's fairly easy to see that $(E_1,D_1)$ and $(E_2,D_2)$ are CPA-secure. If the adversary can distinguish between the encryption of two messages under either cipher, then he can play the CPA game against the original cipher, submit all the outputs of $E$ from the original game, and win the CPA game against the original cipher. This means that the CPA security of $(E_1,D_1)$ and $(E_2,D_2)$ reduces to that of $(E,D)$.

Let's look at the ciphertext integrity game for $(E_2,D_2)$. If the adversary can craft a valid ciphertext $(c,c)$, then $(c,c)$ is not any of the previously obtained ciphertexts by definition of the attack game, which means that the adversary has obtained a new ciphertext $c$ for the original cipher $(E,D)$. So the ciphertext integrity of $(E_2,D_2)$ reduces to that of $(E,D)$.

Now let's look at the ciphertext integrity game for $(E_1,D_1)$. Suppose the adversary has obtained a valid ciphertext $(c^1,c^2)$ by encrypting one message $m$. Recall that the objective of the adversary is to create a valid ciphertext that he hasn't seen before. Can he do that?

   Yes, easily: $(c^2,c^1)$ is a valid ciphertext, and with overwhelming probability $c^1 \ne c^2$ so this is a distinct ciphertext from the one the adversary has already seen.

Now suppose the adversary submits $m$ again, and obtains a second valid ciphertext $(c^3,c^4)$ for the same plaintext $m$. Can the adversary create a new valid ciphertext?

   Yes: mix and match. For example $(c^1,c^3)$ is another valid ciphertext which is distinct from the previous ones with overwhelming probability.

The first counterexample is easily fixable: you could modify $E_1$ into $E_3$ which

   sorts the two ciphertexts, and $D_1$ into $D_3$ which checks whether the ciphertexts are in the correct order. The cipher $(E_3,D_3)$ doesn't suffer from the first counterexample, but is still vulnerable to the second counterexample (either $(c^1,c^3)$ or $(c^3,c^1)$ is a new valid ciphertext).

The second counterexample is more interesting because it shows that both $(E_1,D_1)$ and $(E_3,D_3)$ are fundamentally broken. Their weakness is that they allow the adversary to test whether two ciphertexts are the encryption of the same plaintext. Suppose that the adversary wants to know what a certain message $m$ is for a given ciphertext $(c^1,c^2)$, and they manage to guess that the message is in a small set $\{m_1,\ldots,m_n\}$. He can submit each of the $m_i$'s for encryption, getting ciphertexts $\{(c_1^1,c_1^2), \ldots, (c_n^1,c_n^2)\}$. If he can then test which of the ciphertexts $\{(c_1^1,c^2), \ldots, (c_n^1,c^2)\}$ (or the appropriate swapping of each pair for $(E_3,D_3)$) is valid, for example by observing the result or the timing of an attempted decryption, that lets the adversary find out what the message was.


Order-Preserving Encryption (OPE) and leakage

I do work in this area. OPE and ORE are important primarily because of their tremendous utility in building systems which can perform some computation on encrypted data. Contrary to general-purpose solutions like fully-homomorphic encryption, OPE and ORE can be used to provide drop-in (with no code change) security in applications like databases. They can do this with only a small decrease in efficiency of the application.

OPE and ORE are used in practice. Companies like CipherCloud and Skyhigh Networks deploy encryption software for cloud applications like Salesforce that use OPE heavily. Other major tech companies are also looking at OPE and ORE, though I can't say which ones for confidentiality reasons.

The 'but' (in cryptography there's always a 'but') is that all practical OPE and ORE schemes leak some information about the plaintext. This may seem obvious - to have order-preserving encryption you kind of need to, you know, preserve order. The hitch is that most actual deployable OPE and ORE schemes leak more than just the order of the plaintexts, and in some sense this is unavoidable because of a well-known impossibility result by Boldyreva et al. Further, nobody in the research community really knows how bad this leakage even is for real applications of OPE and ORE - we have precise simulation-based proofs which bound the leakage, but these proofs assume uniformly-distributed plaintexts. It seems like most use cases of OPE and ORE do not involve uniformly-distributed values, though. Extending and generalizing these analyses is a major (and important) open question right now.

I should note that when research papers talk about the "leakage" of OPE, it's not quite the same "leakage" discussed in leakage-resilient cryptography (LRC). LRC is attempting to provide a formal framework for reasoning about the effect of side-channel attacks which leak bits of the secret key, but in analyses of OPE and ORE the key is assumed to be fully hidden from the adversary.


AES vs other types of encryption such as Twofish

Rijndael (aka AES) and Twofish were both candidates and finalists for the Advanced Encryption Standard contest, a three year selection process which yielded the selection of Rijndael as the standard.

Contest submissions were required to be block ciphers of block size 128 bits and support key sizes of 128,192 and 256 bits. Submissions were put through rounds of cryptanalysis and assessment by prominent members of the cryptographic community. NIST, the competition organiser, made the final decision that Rijndael would become the AES.

At a high level both AES and Twofish are 128 bit block ciphers supporting 128,192 and 256 bit key sizes. Both ciphers are (despite a small number of theoretical attacks) secure in the computational/pragmatic sense that nobody has yet found a way to break them. Both ciphers are based on heuristic constructions, meaning that we don't have a proof of security showing a reduction to some known hard problem, instead their security is based on the fact that nobody has broken them yet. Both ciphers satisfy the pseudorandom permutation (PRP) function model in that their output cannot be distinguished from a random permutation in the block size.

High-level differences between the ciphers are that AES and Twofish are based on a substitution-permutation network (SPN) and a Feistel-network respectiveley. These networks are applied in rounds where AES has 10,12 or 14 rounds depending on the key-size, Twofish always applies 16 rounds.


Is it hard to get Least Significant Bit for Elliptic Curve Discrete Logarithms?

For any discrete log problem where the order of the generator is even and known, then the lsbit is easy to recover.

Notation I'll use:

I'll be writing things in additive notation (the notation we typically use for Elliptic Curves).  This is just notation; these ideas translate directly to multiplicative groups.
I'll designate the generator used as $G$, and the order of $G$ as $n$; the problem we're given is, given $H$, find $x$ (or the lsbit of $x$) with $H = xG$

And, in this subcase, we assume $n$ is even.

So, to recover the lsbit of $x$, we just compute $(n/2)H$; if this is the identity element, this $x$ must be even; if this is not, then $x$ must be odd.

Next case; for any discrete log problem where the order of the generator is odd and known, then the lsbit is a 'hard bit'; that is, recovering that lsbit is as hard as recovering the entire exponent.

We show this by demonstrating that, if we were given an Oracle that gave us the lsbit, we can use that to recover the the entire exponent.

We start by finding the lsbit of $x$; given $H$, we can query the Oracle directly, giving us $x \bmod 2$.

Now, to find the next bit; we compute $H' = (2^{-1} \bmod n)(H - (x \bmod 2)G) = (\lfloor x/2 \rfloor) G$; we can then query the Oracle with $H'$; this gives us the second bit of $x$.

We can repeat this process, and read all the bits of $x$ in succession.

(This is a bit more complex if the Oracle we get is probabilistic; I won't bother you with the details)

The last subcase is if the order of the generator is unknown.  If we're talking about multiplication modulo a composite, then if the generator has a Jacobi symbol of -1, then it is easy (compute the Jacobi symbol of $H$; if it is 1, then $x$ is even, if it is -1, then $x$ is odd).

And, as Geoffroy Couteau points out, in the case that the Jacobi symbol is 1, this is reducible to the quadratic residuosity assumption:

If the generator $G$ is a quadratic nonresidue, then $H$ will be a quadratic residue iff the lsbit of $x$ is even; an oracle that is able to determine the lsbit of $x$ will allow us to the test whether $H$ is a quadratic residue.
If we had an oracle which worked in the case that $G$ is a quadratic residue (but not if it is a QNR, as above, that's a hard problem), then that could be used as a test to determine whether $G$ is a quadratic residue; generate a random value $x$, compute $H = G^x$, and give $G, H$ to the oracle; if it gives us the correct lsbit of $x$ on a consistent basis, then $G$ must be a quadratic residue.


No, GCM does not require padding, nor does it require plaintext to be a multiple of the block size.

GCM is a mode that combines CTR, which is a stream cipher mode, with GMAC authentication, which dave has pointed out does require its inputs to be a multiple of its block size, 128-bits. However the GMAC process simply null pads the ciphertext input, then processes the length of the data as an additional input, to eliminate issues relating to that padding method.

CTR mode turns a block cipher into a stream cipher by encrypting an incrementing counter. GCM is only used with a 128-bit block cipher by design, so the stream cipher outputs are generated in 128-bit increments, and only the needed bits are used to encrypt the plaintext. If the plaintext is 136 bits, 256 bits of stream cipher output is generated, and the first 136 bits are used.

Because GCM is based on CTR, the length of the ciphertext is the same as the length of the plaintext, plus the GMAC authentication tag length, plus the length of the Nonce.


There are two requirements here:

Anonymity - the two end points must not be able to discover the other's location or identity, nor must any other party be able to identify either endpoint.
Plausible Deniability - both parties must be able to plausibly deny that they participated in the conversation.

The problem with this type of communication over the Internet is that packets must be routable. You need a way to ensure that messages can be passed between the two end points.

I'm not sure there is a protocol for this per se, but you should definitely look into anonymity networks such as Tor. These work by creating a network of nodes that facilitate anonymous communication.

Tor's anonymity works on the principle that information about a particular conversation is only partially known by any node.

A conversation is created by chaining a number of nodes together, between a source and client. The message is encrypted using EndPoint2's public key. The public keys of Node1, Node2 and Node3 are used to encrypt the identity of Node2, Node3 and EndPoint2 respectively, to produce a chain.

EndPoint1 <---> Node1 <---> Node2 <---> Node3 <---> EndPoint2

From this, we can construct a list of what each participant knows:

Node1 knows EndPoint1's identity and Node2's identity
Node2 knows Node1's identity and Node3's identity
Node3 knows Node2's identity EndPoint2's identity
EndPoint2 knows Node3's identity and the message

Notice that no single node knows about both EndPoint1 and EndPoint2, and only EndPoint2 knows the message. The communications between each node are encrypted, so it is impossible for an attacker to know if a node is the originator of a message or just a node in the chain.

When it comes to the final destination of the message, Tor can use both hidden services (Tor nodes with services running on them) and normal internet services. In the latter case, the message is encrypted with the final node's key, so that it can read the message and talk to the target. If the target is a plaintext service, a compromised node might perform a MitM attack. As such, it's best practice to use SSL or a similar secure protocol when talking to non-Tor services.

For a slightly more in-depth review of how Tor works and how it might be attacked, see my answer to another Tor-related question on Security.SE


Why should a signature use PSS padding in RSA?

RSA-OAEP is an encryption scheme that is CCA secure in the random oracle model (http://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding).

You are talking about encrypting/decrypting hashes with some private/public key, but I don't think you're actually talking about encryption schemes. What you probably mean are digital signature schemes (http://en.wikipedia.org/wiki/Digital_signature). RSA-PSS is not an encryption, but a signature scheme and therefore you use that to sign the message.
Signatures and encryptions have different security requirements.

Since you are using a private key encryption scheme it seems that the authenticity of your communication partner might already be ensured (since you already established a common private key). In this case a message authentication code (http://en.wikipedia.org/wiki/Message_authentication_code), which provides integrity guarantees could be sufficient for you.


Can a cryptographic hash be used as a cryptographic RNG?

Yes, the output should have an entropy of 512 bit (or slightly less). Using it as a key is a good idea. If you want to generate more than 512 bits of key material out of the 512 bit you need to use a Key Derivation Function (KDF). You do not need to stretch the key, because it is no password and has a high amount of entropy - enough to make any brute force attempt impossible.

To do this, you can take the HMAC algorithm. Use a unique number (you can use a counter, it doesn't need to be random) as the message and the original key as the HMAC key. The result is your first real key material. If you need more, use another unique number (you can increment the counter for example) and compute the HMAC with this new number. Do this as long as you want, until you got enough keys. If you do this, don't use the original key material for anything else. If it ever leaks to an attacker, he/she can construct every other key with this original key material.


Would A5/1 with a much larger state be a good choice of stream cipher for hardware?

I have argued so 15 years ago, and not been proven wrong since. Basically, A5/1, with a $n$-bit state, offers a resistance of roughly $2n/3$ bits of security. With $n = 64$, the resistance is very low, thus amenable to not only direct breaking, but also all kinds of trade-offs.

All the attacks published so far are dances around that resistance level of about 43 bits, the point being to make it so that actual instances can be broken "in real time": a 43-bit brute force can be done in relatively little time with a modern PC (in a matter of hours), but if you want to indulge in actual GSM spying you need a much faster break so that you can follow the target phone while it hops frequencies. Various methods have been proposed, that combine some possibly large precomputations with a wait for the algorithm to be in a state that is part of that precomputation; this is the idea in the original attack by Biryukov, Shamir and Wagner. Depending on the writing skills of whoever describes an attack, it is often possible to play between elementary operations, bit operations, CPU opcodes and other measures to get the complexity figure as low as possible, e.g. down to $2^{40}$ for A5/1, but that's just marketing.

At its core, there is always the brute force on the clocking sequence: you need to guess two clocking bits, one way or another, to inject one bit of known output.

As such, an A5/1-like design boosted to a 192-bit internal state ought to offer a resistance of about "128 bits" and, to my knowledge, would not be substantially broken -- as far as we know. One might need to expand the size a bit (say, to 210 bits) to avoid academic trickeries resulting in attacks in cost $2^{126.3}$ or similar nitpicking. How many "blank rounds" should be run after injecting the key is an open question (the original A5/1 runs 100 blank rounds).

Though an "extended A5/1" would be implementable in hardware with very few gates, it would not have been extensively reviewed, and experience shows that extensive review is not optional in the design of cryptographic algorithms. As such, it cannot be recommended "as is". I suggest that you consider instead using one of the eSTREAM portfolio algorithms, especially those that follow the "hardware profile". In particular, MICKEY 2.0 has a variant with a 128-bit key.


Why can't we construct a PRG from a one-way function and hc, but only one-way permutation

The proof of Theorem 7.19 explicitly uses that $f(r)$ for a uniformly random bitstring $r$ is distributed like $r$ when $f$ is a permutation*. I don't have the energy to reprint the proof here to show exactly how the distribution of $f(r)$ is used, but it should be clear that it can be useful to know this about $f(r)$ when arguing that $G$ is a PRG.

If you want a counterexample when $f$ is not a permutation you can see this answer.

*This is the part of the proof that says

  using the fact that  $f$ is a permutation for the second equality

for those who have access to the book.


In Pedersen Key Distribution, can the public key be persistent?

This question probably goes much deeper than what you actually aimed for. Simply speaking: If you use $(p,g,h)$ just a couple of times, where $x$ is not revealed in any way, then yes you can reuse it. If you reuse it very often you might run into trouble. However in a general ElGamal-like encryption system, you can use a single public key as often as you want.

The tricky part in the security proof is, when you have to deal with security under "selective openings", where you consider a larger number of private/public keys, and grant the attacker the ability to open some of them and want to know if the remaining ones are still secure. A paper about this is e.g. "Encryption Schemes Secure under Selective Opening Attack" (Bellare, Yilek, 2009) or "Possibility and impossibility results for encryption and commitment secure under selective opening" (Bellare, Hofheinz, Yilek, 2009)


Should I be worried about XTS tampering when encrypting backups using VeraCrypt?

With XTS mode encryption data can be "tampered with" with the caveat that any changes to the data are random and unpredictable to an attacker. Since encryption acts as a pseudo-random function for any secure encryption you end up with a secure scheme:
Note that for each block there is a unique 128-bit block id according to XTS mode. This ID needs not be random.
XTS mode takes ENC(block XOR block_id) XOR block_id

If XTS was only ENC(block XOR block_id) an attacker can control the value block XOR block_id used to encrypt. This can be potentially useful if the attacker wants to convert it to ECB mode encryption allowing them to run other attacks; but only works in a chosen-plaintext case. This assumes the attacker knows the block id.
If XTS was only ENC(block) XOR block_id an attacker can XOR the block ID manually from the ciphertext to reveal ECB-mode encryption. This assumes the attacker knows the block id. This works in a ciphertext-only attack.
If the attacker can perform #2 they can extend that to ENC(block XOR block_id) XOR block_id. This yields an attack where they combine attacks #1 and #2.

... Or can they?
If an attacker tries the composite attack they'll be restricted by their knowledge of the block id. But in XTS mode the block id is kept secret by encrypting another key, and using that to create the block id. If the attacker knew the block ids used, they could use the outlined composite attack.

If the scheme was ENC(block) XOR block_id the attacker could find the block ids used via the same cryptanalysis that breaks ECB mode, if they knew the pattern between block ids; effectively yielding an obfuscated ECB mode encryption in any case there the block ids are predictable (eg. each block id is the previous id + 1).

If the scheme was ENC(block XOR block_id) the attacker would be unable to recover the block ids, since they would be unable to determine from the ciphertext which ids are likely to be correct.

In the actual XTS mode, since it combines both of those simplified cases the attacker is SOL. Plus, you may have noticed neither of those cases allow an attacker to intelligently modify the plaintext from the ciphertext.

Those attacks can reveal patterns in the information but neither allows (intelligent) data tampering.

CBC mode allows tampering because each block is XORd with the ciphertext of the previous block (the block id is known simply by looking at the ciphertext).

The attacker can modify the ciphertext of the previous block to change the data in a specified block.
The previous block, after tampering, becomes meaningless; but the block the attacker wanted to change is intelligently modified.

In CTR mode tampering is possible because the plaintext/ciphertext isn't passed through the encryption function, at all; it's simply XORd with a random stream (the random stream is generated by the encryption function).

In a secure block cipher, any change to the ciphertext yields random and meaningless plaintext once passed through the encryption function. Therefore, any attempt at tampering would yield that result.
In short,
XTS mode does allow tampering in a certain sense, but the attacker cannot know or predict what the data will become. They can only say "F**k you, your data is meaningless!"


$\newcommand{\concat}{\mathop{\Vert}}\newcommand{\AES}{\mathrm{AES}}$You are asking whether you can take a secure—specifically, IND-CPA—message cipher $E_k$, say AES256-CTR, and a fixed public collision-/preimage-/2nd-preimage-resistant hash function $H$, say SHA-256, and compose them in the form $$c \concat E_k\bigl(H(c)\bigr), \quad \text{where} \quad c = E_k(m)$$ to encrypt a message $m$ with a key $k$, and get a secure authenticated encryption scheme—specifically, IND-CCA3.  (I'm eliding details of nonces and input separation for the moment.  Figuring out how to fit them into this post is left as an exercise for the reader.)

This looks awfully close to encrypt-then-MAC, with the putative MAC $(k, c) \mapsto E_k\bigl(H(c)\bigr)$.  Unfortunately, on its own, that is not a secure MAC.  However, the input $c$ is an encrypted message, so that analysis doesn't end the discussion.

This also looks close to encrypt-and-MAC with the putative MAC $(k, m) \mapsto E_k\bigl(H(E_k(m))\bigr)$, which maybe is secure but it would take careful analysis to say, partly because it's not used in isolation—you also reveal $E_k(m)$ to the attacker.  I haven't done the analysis and I don't know anyone who has, so I won't say one way or another whether this is secure.

All that said, if you change this a little bit by using a secret choice of hash function $H_r$, giving $$c \concat E_k\bigl(H_r(c)\bigr), \quad \text{where} \quad c = E_k(m),$$ then you get the structure of, e.g., AES-GCM, which is a secure authenticated encryption scheme.

The family of functions $H_r$ in AES-GCM is called GHASH, and it isn't even preimage-resistant, let alone collision-resistant, to anyone who knows the index $r$—but $r$ is secret, perhaps derived alongside $k$ from some master key $k_0$.  Since its security requirements are more modest—in technical jargon, it must be an $\epsilon$-almost-universal hash family—GHASH is very fast and cheap to evaluate compared to SHA-256 or any other collision-resistant hash function, as long as you have fast binary polynomial multiplication and reduction.

(In software, you need special CPU instructions to do this fast in constant time, which are not widely consistently adopted in CPU instruction sets or standard programming languages, just like you need special CPU instructions that aren't widely consistently adopted to evaluate AES fast in constant time.  But you could use another stream cipher such as Salsa20 and another hash family such as Poly1305 which works in a prime field—these require no special CPU instructions to evaluate fast in constant time.  Note, however, that this is a little different from NaCl crypto_secretbox_xsalsa20poly1305, which is structured to also defend against a reforgery attack on Carter–Wegman many-time authenticators like AES-GCM uses.  For an even more variegated menagerie of authenticated encryption schemes, check out the CAESAR competition.)


Is every point on an elliptic curve of a prime order group a generator?

This is true of any group of prime order, over elliptic curves or not. This is due to Lagrange's Theorem which states that the order of a subgroup $H$ of group $G$ divides the order of $G$.

Since orders are elements of the ring of integers and since this is a principal ideal domain, unique factorization exists and primes make sense. Or put another way, primes behave how you've been taught they do. Therefore the only possible subgroups of a group of order $p$ are the trivial group of order $1$ and the group of order $p$, i.e. the group itself.

This has a consequence, usually presented as a lemma of Lagrange's theorem - no element can generate a subgroup, so it must generate the full group.

For elliptic curve groups, there is a valid proper subgroup, the trivial subgroup consisting only of the identity, in this case $\mathcal{O}$.


Counting points on elliptic curve over binary field

Counting number of points on elliptic curve over $\mathbb F_2$ is very easy.For extension of fields we can use of this theorem:

Theorem : Let $E$ be an elliptic curve defined over $F_q$, and let $\#E(F_q ) = q +1−t$.
Then $\#E(F_{q^n} ) = q^n + 1 − V_n$ for all $n ≥ 2$, where $\{V_n\}$ is the sequence defined
recursively by $V_0 = 2, V_1 = t$, and $V_n = V_1V_{n−1}−qV_{n−2}$ for $n ≥ 2$.


What is the simplest digital signature algorithm known?

Let's first clear up one thing. We want a secure signature scheme. (And by secure, we mean a scheme that is widely accepted as being secure by experts in the field, that is, cryptologists.) That means we can restrict attention schemes from the cryptographic literature that have reasonable security arguments, which rules out most stuff based on cellular automata etc.

There are as you say many notions of simplicity.

If you want to measure lines of code, you could begin by noting that any reasonable signature scheme will almost certainly employ a hash function. Which means that signature schemes based on hash functions should be fairly compact, especially schemes like Lamport one-time signatures. If you want to move beyond one-time schemes, things become more complicated, but perhaps not too much as measured by lines of code.

However, many languages today provide built-in (or nearly built-in) bignum arithmetic, which means that a scheme like Schnorr suddenly becomes extremely easy to implement, once you have a hash function implementation.

An even simpler scheme (probably) is RSA-FDH, which is nearly trivial once you have a hash function implementation and bignum arithmetic.

Another interesting metric is understanding, either the mechanics of the system or its security. On both of those metrics, RSA-FDH scores extremely high. All you need to understand the mechanics of the system is basic number theory. The intuitive security argument is easy to understand. The security proof is also fairly easy to understand (once you understand the intuition behind security proofs and random oracles).

The mechanics of Schnorr signatures are somewhat more complicated, especially if you use elliptic curves. I hesitate to say anything at all about the intuitive security of Schnorr signatures (I find that the only intuition is that its security is non-obvious). The security proof is much more complicated than the RSA-FDH proof.

Some schemes based on bilinear pairings are deceptively easy to describe, but only if you hide most of the complexity involved.

The mechanics of hash-based signatures are often fairly involved and complicated, and the security proofs I have seen have been fairly complicated.

A third metric is how easy it is to make a secure implementation. This is equivalent to a huge can of worms, which among other things involves your entire tool chain. You may suddenly find that your actual cryptographic schemes matters much less than the language you write in. Historically, Schnorr-like schemes have proven very difficult to implement, while something like RSA-FDH should be much easier. (However, I am not an implementation expert, so don't trust me here.)


What is the difference between "Linkable" and "Traceable" Ring Signatures?

The Wikipedia Article on Ring Signatures, though, suggests Linkable Ring Signatures can't be used for that purpose.

The Wikipedia article doesn't say or imply that. It lists possible applications:

Linkable Ring Signatures: "... One of the possible applications can be an offline e-cash system."
Tracable Ring Signatures: "... An e-voting system can be implemented using this protocol."

First, neither claims explicitly that you can create ballots with it, which is only a part of an e-voting system. And then if something is listed for one of them, it doesn't mean that you can create that only with this one.

And then, you have the wrong source for link signatures. Liu and Wong also wrote Linkable ring signatures: Security models and new schemes just one year later, which builds upon your linked paper but refines it. (although I can't find a publicly available version atm)


Best differential characteristic for this PRF

The function $f$ is biased towards the complement of the input $c_{i,j}$, assuming the other two inputs are approximately randomly distributed.

As all the values $c_{i,j}$ are public, this means that the output of the function $R_i$, and hence the function $F$ is strongly distinguishable from random (being biased towards a known bit pattern). This isn't an answer the specific question you've asked, however it would appear to be a more severe weakness than a high-probability differential would be.


Mathematical checks of the consistency of an RSA key can include:
$$\begin{align*}
e&\text{ odd}\\
n&\text{ odd, and of prescribed bit size (if any)}\\
p&\text{ odd, and of prescribed bit size (if any)}\\
q&\text{ odd, and of prescribed bit size (if any)}\\
n&=p\cdot q\\
1&=(d_p\cdot e)\bmod(p-1)\\
1&=(d_q\cdot e)\bmod(q-1)\\
1&=(q\cdot q_\text{inv})\bmod p\\
d_p&<p-1\;\text{ [redundant with }d_p=d\bmod(p-1)\text{ ]}\\
d_q&<q-1\;\text{ [redundant with }d_q=d\bmod(q-1)\text{ ]}\\
q_\text{inv}&<p\\
d_p&=d\bmod(p-1)\\
d_q&=d\bmod(q-1)\\
\end{align*}$$
All parameters must be non-negative. In the above, $\bmod$ is akin to the %operator in C or java, extended to large integers. The upper range checks for $d_p$ and $d_q$ (and to some degree $q_\text{inv}$) are not mathematically indispensable, but are very customary and simplify the check of $d$, hence are included.

As pointed out by Maarten Bodewes, a primality check of $p$ and $q$ could also be performed; that will catch most random errors on these parameters. This will involve operations on large numbers though. And, chances that an accidental modification of the private key cause $p$ or $q$ to become composite while passing all the above checks is low.

In addition, some devices have extra requirements or/and perform extra checks that are not mathematically necessary. When not met, this could cause the observed device panic; in that case it would be a good idea to identify these requirements/checks, and externally check that they are met. Here is a list, believed exhaustive for industry-standard devices/libraries that I have happened to meet:

$d<n$, or perhaps the stronger $d<(p-1)(q-1)$, or the even stronger $d<(p-1)(q-1)/\gcd(p-1,q-1)$; that later one might be gaining traction since it is in FIPS 186-4, Appendix B.3.1 additional requirement 3(a) (at least for key generation).
$2^{2k-1}<n<2^{2k}$ for some specified values of $k$ (like $k\ge512$ with $k$ multiple of $2^w$ for some $w\ge7$, as in ANSI X9.31:1998; I have also seen lower minimum $k$, and lower $w$ down to 3); FIPS 186-4 requires $2k\in\{1024,2048,3072\}$ (at least for key generation).
If the above applies, that $2^{k-1}<p<2^k$ or the stronger $2^{k-1/2}<p<2^k$ (same bounds for $q$); FIPS 186-4 specifies the later, stronger bounds (at least for key generation).
That $|p-q|$ is above some threshold; FIPS 186-4 uses $2^{k-100}$. Notice that proper random generation of $p$ and $q$ makes this overwhelmingly probable, so much that this check is often (safely) skipped at key generation.
$e$ less than some threshold, like $2^{32}$ in an old Windows cryptoAPI, or $2^{256}$ in FIPS 186-4, or $n$ (that one is commonly specified), or $2^{2k}$ with $k$ as above.
$e\ge3$ (necessary for security), or $e\ge2^{16}+1$ (helping towards security of some variants of RSA with questionable padding), or $e=2^{16}+1$ (the most common value), or $e=3$ (the value leading to the simplest and fastest implementation of the public-key function, and believed safe for proper RSA padding).
I've seen code that requires some special condition on the high order bits of $n$ or/and $p$ and/or $q$ for reliable estimation of quotient in some modular reduction; or have other odd requirements on the public modulus; if that's not well documented, that's a bug.
I've once seen an implementation with a tendency to fail for large values of $q_\text{inv}$, and wondered if forcing $p<q$, or vice versa, would prevent that failure (note that exchanging $p$ and $q$ changes $q_\text{inv}$, though).

Various conditions beyond being prime are often specified for $p$ (and similarly $q$) at key generation; like, $p-1$ or/and $p+1$ having a large prime factor (a requirement in FIPS 186-4 for 1024-bit $n$); but I have never seen that checked after key generation (and such check would be uneasy). Similarly, I have seen requirements for a minimal value of $d$, but have never seen that enforced after key generation.

Note: it is rarely made actual use of both $d$ and $(p,q,d_p,d_q,q_\text{inv})$ for the same private key; sometime things will work without $d$, or with only $(n,e,d)$; that would simplify external checks.

A check that $n=p\cdot q$ can be conveniently performed modulo one auxiliary modulus $r$ (or a few relatively coprime moduli). We compute $\widehat n=n\bmod r$, $\widehat p=p\bmod r$, $\widehat q=q\bmod r$, and check that $\widehat n=(\widehat p\cdot\widehat q)\bmod r$. Convenient values of $r$ are $2^{32}-1$ (because modular reduction is easy; like casting out nines, only in base $2^{32}$ rather than base 10), and $2^{32}$ (which operates only on the low-order 32 bits of $n$, $p$, $q$; and thus should not be the only $r$ used for a check). As a consequence of the Chinese Remainder Theorem, these heuristic checks modulo $r$ become a proof if enough $r$ are used that the Least Common Multiple of all the $r$ is at least $n$.

An equivalent shortcut for operations involving $\bmod$ with a large right-hand operator is much more complex. It seems to involve computing the quotient. Assuming $e$ is less than 32-bit, to check that $1=(d_p\cdot e)\bmod(p-1)$ we might compute $x=\lfloor(d_p\cdot e)/p-0.05\rfloor$ using 64-bit floating point ($x$ will be less than $e$, thus fit 32 bits, and most often the correct quotient), then check that $x\cdot(p-1)+1=d_p\cdot e$ using reduction modulo a small $r$ (or a few ones), as above; if that check fails, we increase $x$ by one (always finding the right quotient if $d_p$, $e$ and $p$ are consistent), then repeat the check. But when the quotient gets large, basically we need full blown bignum arithmetic.

CAUTION: beware that most of the above checks (except those manipulating only $n$ and/or $e$) manipulate secret material, and thus can be vulnerable to side-channel attacks. These checks must be done in a safe environment (or protected against side channels such as timing or power analysis, which is complex).


Change initial hash value of SHA-512/$t$

Can someone explain me how the t actually affects the outcome of the procedure (which, as far as I understand, just calculates the eight 64-bit words xor with "a5a5a5a5a5a5a5a5")?

That's not right.

Both hex 5 and A are encoded setting two bits out of 4; a5 translates to 1010 0101 in bits. I.e. half the bits are flipped. This kind of XOR value is often used (see e.g. HMAC).

The XOR calculation just creates the internal IV for the SHA-512 calculation over the ASCII value of "SHA-512/<t>" where T is a number expressed in normal digits. It is not possible to use a black box implementation of SHA-512 as it would not allow changes to the internal IV. The same goes for the SHA-512/t calculation after that.

How the result of the SHA-512 hash with the special IV is used can be seen in section 6.4 of the document referred to. Basically first initialize SHA-512' with the XOR'ed values. Now calculate the result of SHA-512'("SHA-512/<t\>"). That in turn is used as initial value for SHA-512/t.

Note that the result of SHA-512'("SHA-512/<t>") remains static for a given t. The internal IV values for SHA-512/224 and SHA-512/256 are actually given in the document in section 5.3.6.1 and 5.3.6.1. SHA-384 uses otherwise defined IV, see section 5.3.4.

  Furthermore I don't understand how to pass the new calculated initial hash values to the hash function instead of the default values for SHA512. Can someone explain how to do it in java using the java.security.MessageDigest class (or something else)?

This is not possible because the IV (the initial $H^0_x$ values) is fixed for SHA-512. It is required to use the code of the implementation instead. In principle you can use the GPL'ed OpenJDK source for that, but that might get you in trouble because of Oracle's antics.

Fortunately Bouncy Castle already has an implementation of org.bouncycastle.crypto.digests.SHA512tDigest. I would not take the implementation of that class - and especially of the method tIvGenerate - as prime example of good coding practices, but it does clearly implement the scheme described above.


Groups for which DDH is easy but CDH is hard

Of course, computing the Legendre symbol won't always help differentiate right? But it'll work enough times to beat the DDH assumptions ("non-negligible probability"?)

Yes, if $g$ is an element with Legendre symbol -1, then a simple test of the symbols of $g^a, g^b, g^c$ will show that $ab \ne c$ half the time for random $a, b, c$.  That is certainly non-negligible, and is sufficient to invalidate any proof of a cryptosystem that assumes that DDH is hard.  However, depending on why you want the DDH problem to be easy, it might not be non-negligible enough.

  Are there any more examples?

If you need a group with a more reliable test, we can consider a group with a nontrivial bilinear pairing, in particular, one where $G$ and $e(G, G)$ have the same order.  In that case, we have a test that always gives the correct answer to DDH; $e( aG, bG ) = e( G, cG )$ will hold if and only if $ab = c$


A password manager that produces 16-character passwords is sufficient for most cases. Users who go for 100-byte passwords are usually overly-paranoid, since the actual security benefit is outweighed by the inconvenience. Therefore, limiting a password to 72 characters, while in theory reducing the number of possible passwords, is still very reasonable.

That said, hashing a hash is a bad idea if the hashes are related. sha512(sha512(password)) is more prone to collisions than sha512(password). However, bcrypt (being built with blowfish) is different enough from sha512 that this doesn't apply (not to mention bcrypt is salted). While you're still reducing a user's password from 72+ bytes to 64 bytes, the expected entropy of a user password is orders of magnitude less than 512 bits. It is safe to assume that sha512(password), while technically shorter than password, has much entropy as the original password.

Your second idea seems to be reusing a part of the password, so I don't see much of an increase in security. The entropy from p[0:8] will be spread out with sha512 sufficiently enough already.


Removing some verbosity:

  I'm interested if data that is encrypted and decrypted will always come back in the same state as before the encryption process.

Yes, it's actually one of the first things you learn in Crypto 101: if $e$ is the encryption function of a cryptosystem and $d$ is its decryption function, then $d(e(m)) = m$ for all valid messages $m$. Any system which does not satisfy this property cannot really be called a cryptosystem.


In R-LWE, is there any advantage to generate secret from normal distribution instead of uniform distribution

Neither the secret nor the error in Ring-LWE (or LWE) encryption needs to be generated from the normal distribution.  Only to get the tightest security proofs does one care about the "shape" of the distribution.  For practical cryptanalysis, this does not matter -- only the size of the secret (and noise) does.

Having said this, there is an advantage to the normal distribution.  During decryption, terms that look like $\langle s,e\rangle$ (inner product of the secret vector $s$ and error vector $e$) appears in the decryption.  What we want for security is that $s$ and $e$ have large norms.  What we want to avoid decryption errors is that $\langle s,e\rangle$ is small.  And if one wants to have vectors $s$ and $e$ of a particular $l_2$ norm and have their inner-product be as small as possible, then these vectors should be chosen from a normal distribution.

The binomial distribution is a very good approximation to the normal and is much easier to generate.  This is why it's a good choice for practical applications.

Edit:
My original answer was incomplete.  Actually, the uniform distribution is just as good as the binomial one if one only cares about the above two properties.  The main advantage of the binomial distribution is that it has more entropy.  This is important to prevent brute force and man-in-the-middle attacks.


What's the difference between confusion/diffusion and mode of operation?

AES is a mode of operation, and confusion/diffusion are what we use to achieve a certain mode.

AES is a block cipher, which replaces one fixed-length block of bits (plaintext) with another fixed-length block of bits (ciphertext) according to the key. A block cipher is not a mode of operation.

Confusion and diffusion are a description of how AES behaves to ensure that given a/many plaintext-ciphertext pairs, you cannot recover the key, as well as given a ciphertext, you cannot recover the plaintext.

"Confusion" basically means that the equations that represent the ciphertext are too complicated and cannot be worked with, while diffusion means that each bit of the plaintext influences many (half) of the bits of the ciphertext. These two properties help to ensure that extracting the key from plaintext-ciphertext pairs is difficult or infeasible.

Since AES only operates on blocks of 128-bits, you require a mode of operation to encrypt plaintexts of size > 128 bits. So a mode of operation is a way of using a block cipher to encrypt (effectively) arbitrary length messages.

Since for a fixed key AES is deterministic, a mode of operation also provides a means to randomize plaintext-ciphertext pairs, so that multiple encryptions of a plaintext cannot be distinguished from each other. This is necessary to properly provide confidentiality of the plaintext.


In which cases should the IV be kept secret?

Normally, in a properly designed cryptographic system, everything that must remain secret is either actual data (and the system exactly aims at preserving that confidentiality) or a key. Everything else ought to be public or at least publishable with no ill effect, as per Kerckhoffs' principle.

Now it so happens that a number of cryptographic systems are expressed as iterative processes, starting with an "initial value" (or "initialization vector"), i.e. an "IV". It is conceivable that in such a system, the IV is a key. A contrived example would be a hand-made stream cipher with a hash function:

A state s is initialised to some value.
The stream cipher produced pseudo-random bytes by repeatedly hashing s: the first bytes of output are H(s), then H(H(s)), and so on.

Such a stream cipher is then an iterative process that repeatedly produces the next value of the "running state" by hashing that state. The starting value for the state is thus an initial value in the strict sense of the term, and is also the key for the stream cipher, hence the need for secrecy.

This is, however, a quite contrived example. This stream cipher is atrociously weak in several ways (don't use it!). In a properly designed cryptographic system, we really prefer it when keys are reusable: keys that can be used only once tend to imply issues (it was one of the problems with RC4). Instead, we prefer keys that can be used several times (e.g. to encrypt several messages), possibly along with other values that need not be secret, but must be changed each time. This is what normally happens with encryption system: a secret key, that can be reused for several messages, and a per-message "nonce" that must be generated anew for each message, but needs not be secret; hence, the nonce can be transmitted along with the message. The "IV" in most encryption systems fulfils this "nonce" role.

In a more conceptual point of view, the notion of "IV" is not precisely defined. Thus, expressing an absolute such as "IV never need to be secret" is bound to anger somebody, somewhere, would used an IV in a slightly exotic way and found a situation where something can be called an "IV" and still requires secrecy. Using a phraseology like "usually" or "in most cases" is a simple way to avoid triggering an acrimonious debate.


How are precision and security related in a Gaussian Noise Sampler for R-LWE?

The discrete Gaussian distruibution have the most entropy at the same standard deviation compared to other discrete probability distributions. It's important in some LWE/SIS digital signature algorithms because it helps reduces the signature size (most notably in BLISS and FALCON), but otherwise not so essential in key exchange or encryption (and has been replaced with binomial distribution in NewHope).

The reason using Gaussian distribution reduces the signature size, is because it allows certain entries in the signature to be represented with shorter codewords using e.g. Huffman coding. But doing it right can be difficult, as slightest observable difference from true discrete Gaussian distribution can lead to leak of private key information.

Take a Fiat-Shamir signature scheme as an example, the signature $z$ is calculated as:

$$u=Ay$$

$$c = H(u,m)$$

$$z = y+sc$$

Where $A$ is a component of the public key, $m$ is the message, $s$ is a private key component, and $c$ is the output of hash function and $y$ is randomly generated according to discreate Gaussian distribution.

We want $z$ also be in discrete Gaussian distribution, becuase

since we've added $sc$ to bind the private key to the signature, and
$c$ is a public component,

we have to hide the private component with $y$. And here, in order to achieve the expected distribution, rejection sampling is used.

See also: How would low-precision Gaussian sampling impact the security of BLISS?


Can I connect the hardness of a linear short integer solution problem to that of SIS problem?

I would say that, in general, your problem is actually easier than $SIS$.

Let's call your problem $LSIS_{n, q, B, m, b}$. First of all, notice that if you can find a solution $s$ to $SIS_{n, q, B, m}$, than $s_1 = s_2 = s_3 = ... = s_b = s$ is a solution to $LSIS_{n, q, B, m, b}$, which already means that your problem cannot be harder than SIS.

Furthermore, notice that for fixed parameters $n, q, B, m,$ and $b$, there are several easy instances for $LSIS$. Some examples,

if some $a_i$ is equal to some $a_j$, then $s_i = -s_j = (1, 0, 0, ..., 0)$ and $s_k = 0$ for $k \not \in \{i, j\}$ is a very short solution to your problem;
if there is short pair $a_i \ge a_j$ such that $B \ge a_i$, then $s_i = a_j\cdot (1, 0, 0, ..., 0)$, $s_j = -a_i\cdot (1, 0, 0, ..., 0)$, and $s_k = 0$ is a solution to your problem, since $||s_i|| \le ||s_j|| \le a_i \le B$;
if there is a pair $(a_i, a_j)$ such that $a_i^{-1}$ and $a_j^{-1}$ are small, then $s_i = a_i^{-1}\cdot(1, 0, 0, ..., 0)$, $s_j = -a_j^{-1}\cdot(1, 0, 0, ..., 0)$, and  and $s_k = 0$ is a solution to your problem.

Notice that for $b = 2$, if you choose the values $a_1$ and $a_2$ uniformly at random from $\mathbb{Z}_q$, then that first easy case will already appear with probability $1/q$, which means that if $q$ is polynomially big in $n$, then a random instance of your problem can be solved trivially with non-negligible probability. But $SIS$ is hard in average for $q = poly(n)$. Therefore, at least for these parameters, you cannot reduce $SIS$ to an average-case version of your problem.


Building index for Bloom filter using cryptographic hash functions

At a glance, it seems that the paper you linked to does not actually specify how to convert the PRF outputs to Bloom filter indexes.  As far as I can tell, however, any scheme that does not introduce a significant bias should be fine.  For example, if the Bloom filter array size $m = 2^b$ is a power of two, simply taking the first (or last, or any) $b$ bits of the PRF output should be fine.  For non-power-of-2 array sizes, reducing the $s$-bit PRF output modulo $m$ should also be acceptable, at least provided that $m \ll 2^s$.

Indeed, the method used to convert the PRF output to the Bloom filter array index should not have any effect on security, since the conversion is only applied to PRF outputs which, by definition, are effectively indistinguishable from random.  However, obviously, a highly biased conversion method could reduce the entropy of the index distribution, and thus increase the false positive rate.

BTW, looking at the scheme presented in the paper, the use of $r$ separate PRF invocations seems somewhat inefficient, both in terms of processing speed and in terms of the size of the "trapdoor" representation.  As far as I can see, a more efficient variant of the scheme would look something like this:

  Let $m = 2^b$ be the array size and $r$ the per-element index set count of the underlying Bloom filter, and let $s$ be an arbitrary security parameter (say, $s = 256$).  Choose the PRF families $f_T : \{0,1\}^* \times \{0,1\}^s \to \{0,1\}^s$ and $f_B : \{0,1\}^* \times \{0,1\}^s \to \{0,1\}^{rb}$ (where, as in the paper, the second argument denotes the key input).

  For example, for $s = 256$, we could choose $f_T(w,k) = \text{HMAC}_{\text{SHA256}, k}(w)$ and define $f_B(d,k)$ as the first $rb$ bits of $$\text{HMAC}_{\text{SHA256}, k}(1 \,\|\, d) \,\|\, \text{HMAC}_{\text{SHA256}, k}(2 \,\|\, d) \,\|\, \dots \,\|\, \text{HMAC}_{\text{SHA256}, k}(\lceil rb / 256 \rceil \,\|\, d),$$ where the numeric prefixes are all padded to some fixed length.  Alternatively, we could just instantiate both $f_T$ and $f_B$ with KMAC (possibly with different customization inputs, although that shouldn't actually be necessary).

  Define:

  $\textsf{Keygen}(s)$: Choose a random $s$ bit master keys $K_{priv}$ and return it.
  $\textsf{Trapdoor}(w, K_{priv})$: Given an arbitrary word $w$, output its trapdoor representation $T_w = f_T(w, K_{priv})$
  $\textsf{BuildIndex}(D, K_{priv})$: Given a document $D$ with unique ID $D_{id} \in \{0,1\}^*$ and a list of distinct words $(w_1, w_2, \dots, w_t)$, initialize the $m = 2^b$ bit Bloom filter array $B$ to all zeros and, for each word $w_i$:

  Compute the trapdoor token $x_i = f_T(w_i, K_{priv})$.
  Compute the $rb$ bit codeword $f_B(D_{id}, x_i)$ and split it into $r$ indices $(y_{i,1}, y_{i,2}, \dots, y_{i,r})$ of $b$ bits each.
  Set the bits $y_{i,1}, y_{i,2}, \dots, y_{i,r}$ of the Bloom filter array $B$ to $1$.

  Finally, to hide the number of distinct words in the document, pick (with replacement) $(u-t)r$ additional random bits of the Bloom filter array $B$, where $u$ is some publicly known upper bound on the number of words in the document $D$, and set them to $1$.  Output $(D_{id}, B)$ as the index of the document $D$.
  $\textsf{SearchIndex}(T_w, D_{id}, B)$: Compute the $rb$ bit codeword $f_B(D_{id}, T_w)$ and split it into $r$ indices $(y_1, y_2, \dots, y_r)$ of $b$ bits each.  Output $B_{y_1} \land B_{y_2} \land \dots \land B_{y_r}$, where $B_i$ denotes the $i$-th bit of the Bloom filter array $B$, and $\land$ denotes bitwise AND.

With these modifications, the "trapdoor" tokens are only $s$ bits long (rather than $sr$ bits as in Goh's original scheme), and computing them requires only one PRF invocation.  Similarly, e.g. using the HMAC-based construction of $f_B$ above, an insertion or a lookup of each word requires only $\lceil \tfrac{rb}\ell \rceil$ HMAC invocations, where $\ell$ is the HMAC output length, rather than $r$ invocations as in the original scheme.  Since typically $b \ll \ell$, this also saves considerable computation time.

BTW, note that this "double PRF" design looks quite similar to the "extract and expand" paradigm used in some key derivation functions like HKDF.  Indeed, we could implement $f_T$ as HKDF-Extract (which is really just HMAC) and $f_B$ as HKDF-Expand (which is similar to the simple concatenated HMAC scheme described above).  In effect, the client wishing to query the index for a word extracts a pseudorandom key (PRK in HKDF terminology, trapdoor in Goh's terminology) from their private key using the query word as the salt, and then sends this PRK to the index server, which expands it into a distinct Bloom filter index set for each document (using the document ID as the "context specific information" to make the index sets distinct).

Also note that the scheme described above can be modified to support hierarchical indexing, arbitrary updates, occurrence search, IND2-CKA security and/or boolean (or limited regexp) queries in exactly the same ways as Goh's original scheme.  However, the shortened trapdoor tokens do prevent the use of the "heuristic security increase" technique (i.e. sending only part of the token to the server to hopefully disguise the word being queried) described in section 5.1 of the paper.

Of course, I cannot guarantee that I haven't made some silly mistake above that somehow compromises the security of the modified scheme, nor have I carried out a detailed security analysis like the one given for the original scheme in the paper.  All I can say is that, as far as I can tell, it looks to me like it should be just as secure as the original scheme.


Does SHA-1 hash have quasi commutative property?

No, $\operatorname{SHA-1}$ does not have any property remotely similar to the quasi-commutative property, that
$$\forall x,\forall  y_1,\forall y_2, f(f(x,y_1),y_2)=f(f(x,y_2),y_1)$$

That's for that natural mapping of $f(x,y)$ to $f(x\|y)$, where $\|$ stands for concatenation. No function (except trivially narrow) can exhibit such property and also aim at being similar to a random function. And the only striking property distinguishing $\operatorname{SHA-1}$ from a random function (beside being $\operatorname{SHA-1}$) is that it has the length-extension property (which allows, given $\operatorname{SHA-1}(x)$ and the length of $x$, to exhibit non-empty $y$ such that $\operatorname{SHA-1}(x||y)$ is known).


Uniqueness of representation of $y$ to the bases $g$ and $h$

This representation is not unique. If $k$ is the discrete logarithm of $h$ with relation to base $g$, then $$y = g^{x_1}h^{x_2} = g^{x_1}(g^{k})^{x_2} = g^{x_1 + k \cdot x_2}$$

Then for any $m$, $$x_1' = x_1 + m \cdot k,$$ $$x_2' = x_2-m$$ is another pair such that $y=g^{x_1}h^{x_2}=g^{x_1'}h^{x_2'}$.

We can reduce the discrete logarithm problem to finding a second pair $x_1', x_2'$. Given a second pair, we can efficiently compute:

$$ m \equiv x_2 - x_2' \mod n$$
$$ k \equiv (x_1' - x_1) \cdot m^{-1} \mod n$$
$$ k \equiv (x_1' - x_1)(x_2 - x_2')^{-1} \mod n$$

So finding a second pair is at least as hard as solving the discrete logarithm problem.


How does the process of creating a new secure Elliptic Curve look like?

As you said, you need to define the goals. You can take a look at SafeCurves, which is a joint work by Bernstein and Lange to help choose/construct elliptic curves w.r.t. ECDLP difficulty and ECC security. Note that if you need a pairing-friendly elliptic curve you need to look at other criteria related to the embedding degree. You can read this paper by Freeman et al. for different constructions. Now talking about Curve25519, Bernstein explained his choices in his paper. These are some of the main points he mentioned in a talk:

Curve25519 has a large prime char field because current CPU multipliers include fast floaing-point multipliers and extension fields punish CPUs with another multiplier size.
Curve25519 has a Montgomery shape $y^2=x^3+Ax^2+x$ with tiny $A \in 2+4\mathbb{Z}$ because one can do projective $x$-coordinate doubling and addition together using 1 field multiplication by $(A-2)/4$, 4 field squarings and 5 extra field multiplications without needing $y$ coordinate.
Curve25519 uses prime very close to a power of 2. Specifically, $2^{255}-19$ instead of a Solinas prime like $2^{256}-2^{224}+2^{192}+2^{96}-1$ because repeated addition is more costly than multiplication by 19.
Curve25519 uses a secure curve of order $8 \times \text{prime}$ with a secure twist $y^2=x^3+486662x^2+x$ of order $4\times \text{primes}$.
The $A$ is chosen so that $(A-2)/4$ is a small integer to speed up multiplication by $(A-2)/4$ (formulas here) and so that the twisted curve order is either $4 \times primes$ or $8 \times primes$. The smallest positive choices were then 358990, 464586 and 486662. Bernstein rejected 358990 and 464586 because one of their prime factors is slightly smaller than $2^{252}$ and discussing the question on how one should handle the theoretical possibility of a secret key matching the prime is harder than simply moving to the last choice $A=486662$ (Nothing up my sleeve).


AES S-Box: How is value for 01 mapped to 7c?

$00000001$ is its own inverse in the Rijndael field, because polynomial multiplication by itself gets $00000001$ and is unchanged by the modulo operation.  This will always be true in any ring, as noted in a comment above.

However, the specification of the Rijndael S-box is that after taking the inverse of the number in the Galois field, you have to multiply the result by a matrix then add (XOR) a constant: the "affine transformation".  That is what makes 0x01 map to 0x7C.

Note that for the purposes of the Rijndael S-box, zero's inverse in the field is considered to be zero.  The affine transformation is applied to zero, getting the expected 0x63.


Randomize (encrypted) data to hide the behaviour of the data source

I assume that you meant to xor the message with the LSFR state, and not with the fixed key.

Even in that case, one problem that you don't cover is that if the attacker knows/guesses that the data between two different exchanges is the same, he can recover the LSFR state (and from that, he gets everything).

What he would do is xor the two ciphertexts $LFSR^k \oplus P$ and $LFSR^{k+n} \oplus P$; that gives him $LFSR^k \oplus LFSR^{k+n}$; if he knows how large $n$ is (the number of times you cycled the LFSR between the two messages), then recovering the original LFSR state is a simple exercise in linear algebra.

Designing such a system really isn't a task for amateurs; it's far too easy to come up with a system with subtle vulnerabilites such as above.  Instead, I would suggest you use a system designed by an expert.

I was going to write some advice here about how to sketch out such a system; however I realized that I don't know enough about your system constraints and required security model to do it justice.  However, someone needs to do it, and you're not the right person.

I'm not criticizing you; actually, your list of requirements ("the messages need to be randomized", "no security by obscurity", "no reliable timesync", "message loss may happen") shows you've thought about it.  It's just that making an efficient and secure encryption system is a lot harder than it looks.

As for some of the constraints that would need to be considered by an expert:

You mention potential evesdroppers; do you also need to worry about someone modifying the ciphertext (perhaps in hope of making predictable changes in the decrypted data)?
How large can the ciphertexts be?
You said that you had constraints in both time and memory; how tight are those constraints?  Is the memory constaints on program size or data size?  If you're on a CPU, is that an 8-bit CPU, or a 32-bit CPU?
If someone recovers the key somehow, they can read all the data; are you OK with that?


Differences between the terms "pre-master secret", "master secret", "private key", and "shared secret"?

Simplified SSLv3/TLS from this book Note, $R_{(Alice|Bob)}$ is a random nonce chosen by Alice or Bob respectively, and $\{S\}_{Bob}$ is encryption with Bob's public key.

pre-master secret

As stated in one of the answer you link to, "The point of a premaster secret is to provide greater consistency between TLS cipher suites."

In the figure above, the premaster secret is $S$ (in message 3). In this case, it is randomly generated. It could come from a diffie-hellman exchange, or some other method, depending on the agreed upon cipher suite.

It isn't really "related to the private keys" but how it is generated/agreed upon depends on the cipher suite chosen in the second message of the figure.

master secret

In the figure above, the master secret is $K$. Shown on the sides, it is a function of the pre-master secret and the two random values sent in the first two messages.

private key

I'm not really sure where this comes from. It could refer to the Bob's private key for the certificate sent in message 2. It could also refer to private keys used in a diffie-hellman key exchange. If doing client authentication, it could refer to the client's private key associated with their certificate.

shared secret / session key

This is what is referred to in the last step of the figure. The session key is referred to as "keys derived from K". Many keys are actually derived from K. This could be the encryption key, integrity protection keys (for say HMAC), IVs for the ciphers, etc. And, it is usually a different set for each direction.


Can we do better?

Yes. See: On Ends-to-Ends Encryption: Asynchronous Group Messaging with Strong Security Guarantees.

To support significantly larger groups?

  Our results demonstrate that ART is practical for reasonably-sized groups, with key tree setup and message sending both taking a few milliseconds for groups of size ten and on the order of one second for groups of size 1000.

While maintaining end to end encryption? Will we be able to still maintain other properties, like forward secrecy?

The important property that we care about here is Post-Compromise Security (PCS), defined as:

  Moreover, some modern messaging protocols offer a property called Post-Compromise Security (PCS), sometimes referred to as “future secrecy” or “self-healing”. For PCS, even after Alice’s device is entirely compromised by an adversary, she may later be able to establish secure communications with others after a single unintercepted exchange.

These trees establish new group shared keys when any member joins or leaves the group, or when each member decides to rotate their key. In double-ratchet keys usually rotate after the first message from each user since the key changed, although some implementations, specifically Matrix' Olm, opt to be less noisy; re-keying every N-messages or after T-seconds.


Does stronger cryptographic hashes also imply being better at verifying integrity?

1) All common cryptographic hash functions are better than CRC, even MD5. This is due to the fact that they are designed to detect malicious tampering, whereas CRC is not. MD5 is still crackable, but CRC can be trivially manipulated.

2) hash function collision resistance determines how "good" they are at integrity verification, as there are more possible unique outputs, bigger is better, however even 64-bit collision resistance is enough to detect non-malicious data corruption in most cases unless you are dealing with large files. SHA256 has 128-bit collision resistance, which is a lot, that is 340 billion billion billion billion, which is more atoms than contained in all of the human beings on the planet combined. The collision resistance of a 512-bit function such as SHA512 is just nuts, almost matching the amount of atoms in the entire universe.


Is there confirmation blocks in Proof-of-Stake Blockchain?

For a proof-of-work blockchain, say Bitcoin, the confirmation length is 6, just to make sure any adversary doesn't create any additional blocks and make a new fork that's longer. That's possible because all you need is more computation, and no proof of identity.

However, in proof-of-stake blockchain protocols, you often need to provide a new block with some kind of proof that you are eligible to propose the new block. This instantly creates a confirmed block because for a particular slot, another party cannot create a valid block and proof later in time.

Take a look at the Algorand protocol for more details.


GCM is an algorithm for building an "authenticated encryption with associated data" (AEAD) scheme. The ADATA in the spec refers to associated data. Associated data is auxiliary information or metadata that needs to be in plaintext for functionality reasons (for example, headers in an IP packet) but which needs some integrity guarantees. The idea of AEAD was folklore, but Phil Rogaway introduced it as a design goal for symmetric encryption and formalized security notions for it. See this paper for more details.


Is digest=HASH(HASH(a)+HASH(b)) equivalent to publishing two digests?

If I get the suggested construction correctly, it is to

1) hash n values (with SHA-256);

2) add theses hashes, perhaps mod 2256;

3) hash the sum (with RIPEMD-160).

This would be potentially unsafe: creating a collision or even second pre-image at step 2) reduces to a knapsack problem, and this has a poor safety record; it might be workable when the number n of inputs allowed gets above some threshold, with some relation to the number of bits in the first hash.

There is a simple, safe solution: at step 2), instead of adding the hashes, sort them, then concatenate them; sorting keeps the associativity and commutativity of addition (and is otherwise unnecessary). The construction becomes essentially as resistant as the weakest of the hash functions against collision (second pre-image resistance is the weakest of that for the first hash function for n preimages, and the second hash function).

Note: I see no good reason to use two different hash functions.

-

Here is an attack against a slight modification of the proposed construct, with addition replaced by XOR. It is a second-preimage attack: the attacker has a set of valid input values, and wants another set with the same overall hash after step 3).

In a preparatory step, she generates random values (all distinct from each others and valid input values), hashes them with the first hash, until a basis of 256 hashes emerges from the accumulating hashes; that is, until each of the values 20, 21, .. 2255 can be expressed as a linear combination of XOR of some of the 256 hashes in that basis. This is simply a matter of adding the newly generated hash to the basis, unless it turns out to be a linear combination of the ones already in the basis, which can be checked by Gaussian elimination. The basis is complete when it contains 256 hashes, which will happen shortly after the 256th random value.

To obtain a forgery, she performs steps 1) and 2) normally with the valid input strings. She expresses the result as a linear combinations of the hashes in her precomputed basis, again by Gaussian elimination. It will consist of the XOR of about 128 hashes from the basis. The random strings that generated these hashes form a set which is a forgery. Step 3) is not necessary. It is easy to markedly reduce the number of strings in the forgery.

If addition modulo 2256 is used, or worse with straight addition, things are markedly more difficult, but conceivably still manageable (with more vectors in the forgery, and in the case of straight addition more vectors in the original); it is a knapsack problem, with a nearly unlimited supply of values.

-

I do not know how safe the system is with the number of elements limited to 20 (which I now realize is part of the statement); but at any rate, the addition step potentially is a weak spot.


Can you help me find a cryptanalytic way to attack a simple monoalphabetic substitution cipher algorithm?

In the absence of clues, I think you might be left with trying to brute force the ciphertext. However there are ~ $26^{26}$ (maybe it's $26!$ which is still a big no) possible permutations of a 26 character alphabet. That's something that would require enormous computing power.
Brute forcing then might be impractical.

You mentioned the Key is a permutation of the alphabet, the word key sort of suggests a vigenere cipher and the key length is 26 Scrambled up letters. As a general rule, Keywords are shorter. The longer the Keyword, the tougher the Vigenere cipher is going to be to crack. I'm thinking that a key word consisting of the alphabet scrambled is going to be incredibly difficult.

I'ld question what you mean when you say …The key is a permutation of the alphabet… because as a general rule, university professors set difficult problems – not impossible ones. I'm guessing, with my limited knowledge of the subject that greater clarification is needed.

The other thing you can do is carry out a frequency analysis of the letters in the ciphertext, see if there are clear differences in frequency between some letters and others.

Also look for recurring sequences of letters, the distance between these recurrences in the Vigenere is indicative of the key length.
For example, some way in to the ciphertect there may be a three letter sequence like YDS if this occurs later, maybe several times, the distance between those occurences can give away the key length.

So, Three suggestions.

Frequency analysis… Recurring sequences of letters…

Get a second and third opinion from a specialist in Cryptography as I'm merely a beginner and a hobbyist.


How secure is this use of Ziv-Lempel encoding?

Ziv-Lempel is a data compression algorithm, so in general it doesn't protect your data. As for your question:

  More generally, how difficult is it for an adversary to distinguish two strings which have been Ziv-Lempel encoded but not encrypted?

An adversary just can decode two strings and compare them. Due to the fact that Ziv-Lempel is an encoding algorithm, if you send your data to somebody then you have to send the other information needed to decode your data by the receiver. So, in this case an attacker can easily get access to the transmitted data.


Is this an acceptable implementation of ARC4 encryption for my system?

There are a bunch of problems with this protocol.

First of all, the way you generate your RC4 key (concatenate a secret key with a public nonce) is known to be weak.  The one thing that saves you is that you only do it 256 times before generating a fresh secret key; however it is known that if you were to do it, say, 2000 times with a secret key, you would have a small probability of leaking the secret key.  In my opinion, that's close enough to be scary; I'd rethink this.

Now, on to your actual question:

  I think this is not a very smart way to implement MAC

That's putting it mildly; it's a very bad way to implement it.  The problem is that CRC-8 is perfectly linear; someone who intercepts a packet can flip bits in the ciphertext, and then predict which bits in the CRC-8 he would need to flip to compensate; the decrypted plaintext will have precisely those bits flipped.  The only thing that can save you is you will reject the same message twice; an inventive attacker can get around this by causing the reception of the authentic message to fail.

It would appear that the main restriction you have is on memory (for the program and data), and not so much on execution speed. If so, I would suggest you look at small AES implementations, such as talked about in this stack exchange.  They would appear to fit well within your budget, and can be used as the basis for a truly secure protocol.


The purpose of the  bitcoin block chain is to provide an imitable public ledger.

If you read the original bitcoin paper you will see that the block chain is but one component of a larger whole that provides public trust that coins were not double spent. See section 2 "Transactions" that states this explicitly.

Within a traditional bank the ledger is private and transactions are not signed by the owner. The trust in this case is somewhat blind but revolves around a promise by the bank that it will handle transactions on your behalf with care, and after all it is in the banks own best interests to prevent double spending.

Why don't banks use a bitcoin style ledger, well a few spring to mind but I will admit to a little speculation here.

Block-chains are computationally expensive to check continuously and their are much faster book keeping methods borrowed from traditional accounting practices.
Database transaction logs and transaction hashing is available to prevent corruption of data in storage.
The ledger is private so the only entity the bank needs to satisfy the correctness of transactions is itself.
If the bank were to use a Block-chain then where are the private keys to sign transactions going to come from? Is the bank going to store them for its customers?

Lets now look at the article you cite from Iron Mountain. This is a slightly different kettle of fish. They store data that you CAN sign and while we expect that data to be private between the owner and storage provider the trust equation here is different. The bank was self incentivized not to duplicate or modify transactions because it would directly loose money, in the IM storage case - aside from paying them monthly fees and perhaps reputation - we have no implicit reason to trust that they will not modify information. So for IM storage we do have a case for the use of a block-chain.

The question of 'are digital signatures enough' depends on

You use a decent key size sufficient to provide perfect forward security.
You trust all members of your organisation that have access to the private keys.

For archiving purposes a block-chain can also prove that one document preceded the next, something that digital signatures alone can not do. It can also show that no record has been tampered with by users with access to the private keys.


Why is Shamir Secret Sharing not secure against active adversaries out-of-the-box?

Here is an active attack on the privacy of out-of-the-box SSS.  For this attack, we'll assume that the attacker (without a valid share) is allowed to participate (with $T-1$ friends with honest key shares), jointly use the protocol to recover a 'shared secret' (which might not be the real shared secret); we'll assume that this shared secret recovery process is done by some MPC-secure method so that the attacker learns nothing other than the final value.  We also assume that everyone's $x$ coordinate is public.

First off, the attacker picks a value $x_a$ which is an $x$ coordinate which is not the $x$-coordinate shared by anyone else.  If the dealer were to generate a share with that $x_a$ value, it would generate a $y$-coordinate that we'll call $y_a$; obviously, the attacker does not know this $y_a$ value.

Then, the attacker then gets a set of $T-1$ friends, and have them recover a shared secret value using their shares (and the attacker will contribute the value $(x_a, 0)$; (actually, a nonzero value for the $y$ coordinate would work, but make the explanation slightly more involved); they'll go through the SSS recovery process, and obtain a value which we'll denote as $S_0$.

If we call the real shared secret $S$, then what the attacker can do is derive a value $T_0$ (which depends on the $x$-coordinates of him and his friends), and derive the linear equation:

$$S = T_0 y_a + S_0$$

This is a linear equation in two unknowns ($S, y_a$), and $T_0 \ne 0$, and so the attacker cannot derive any information about $s$ from it.  This can also be derived from the security properties of SSS; the attacker and his $T-1$ friends only have $T-1$ valid shares, and so of course they cannot recover $S$.

What the attacker then does is get together a different set of $T-1$ friends (there can be some overlap, but there must be at least one difference), and do the same thing again (with the attacker using the same $(x_a, 0)$ share.  They do the same thing, deriving a 'shared secret' value $S_1$, and the attacker ends up with a second linear equation:

$$S = T_1 y_a + S_1$$

Now, if $T_0 \ne T_1$ (which is likely if the two sets of friends are distinct), the attacker has two linear equations in two unknowns; it's trivial to solve for $S$.


Different tools return different ciphertext value for equal input

Let me try to provide an answer for your question (despite the answers in the comment section). Some research showed that a recently discovered vulnerability allowed to extract the keys from SafeNet HSM (which the Luna G5 is). Therefore it should under normal circumstances NOT be possible to extract any private keys from the HSM.

To your question in the comments:

  I checked getattribute command for RSA Keypairs on the the HSM. It
  seems that the device show the Modulus and public Exponent. Is it
  unusual and strange too?

Compared to 3DES, RSA is an asymmetric encryption scheme, meaning that you have a public and a private key. While data is ENcrypted with your private key, it can be DEcrypted with your public key. The modulus and public exponent are the public key of the private key which is stored in your HSM.

To sum it up: The purpose of a HSM is that no one should be able to extract any keys from it. In this case you may have to trust the implementation of the vendor.


What does $\to$ mean in the following definition of a block cipher?

That definition is a standard definition which defines encryption as a function $E$. That function takes two inputs, a $\kappa$ bit key and a $n$ bit message.  Hence it is defined over the cartesian product - denoted as $\times$ - over these two sets, i.e. all bitstring of length $\kappa$ and $n$ respectively. It maps - denoted as $\rightarrow$ -  to an $n$ bit output (the ciphertext).


Is this a secure keyed hashing construction?

If you want to construct a PRF for arbitrarily-long inputs using AES, then just use CBC-MAC (while prepending the message length in the first block). I don't see any advantage in what you are proposing and therefore don't see any point in trying to analyze something non-standard.


I'll assume a system as follows

$N=p\,q$ is the public product of two large secret primes, chosen about uniformly randomly and independently, thus distinct (with overwhelming odds). Such $N$ is believed hard to factor.
the signer chooses a meaningful message $m$ independently of $p$ and $q$, expressed as a non-negative integer verified to be less than $N/256$, and somewhat finds $k\in[0,255]$ and $c\in[0,N)$ so that $256m+k=c^2\bmod N$ (there are four such $c$ for $s\approx64$ values of $k$, and no $c$ for the others $k$, with high odds).
the verifier receiving an alleged $c$ computes $m=\lfloor(c^2\bmod N)/256\rfloor$, and trusts that message if it makes sense.

The chances to forge a signature depends tremendously on what the verifier considers "makes sense". For example, the adversary could set $c=37152$, yielding $c^2=1380271104=\mathtt{52454400_h}$, $m$ is $\mathtt{524544_h}$, which in ASCII is RED. Similarly, $c=33360$ yields BUY. We can't pull that trick for many english words, but that counts as forgery unless we better define "makes sense". And for large $N$, if "makes sense" means that the low-order byte of $c^2\bmod N$ is set to zero to create a terminating character, and the whole thing passed as first argument to puts for display and must be something precisely specified, it is still trivial to forge anything desired up to about half the size of $N$. That can be next to any 127-byte string for 2048-bit $N$ (the lowest recommended minimum these days).

Update: We learn that "The meaningful bytes of $m$ (are) coupled together by (a) checksum" of unspecified size. Forgery can be attempted by trying various $c$ until finding one such that $c^2\bmod N$ pass the checksum check. Expected number of trials is $2^s$ (for optimal checksum), where $s$ is the number of bits in the checksum. For up to 32-bit checksum, we are talking at most seconds of computer time. There's nothing to force us to have $c>\sqrt N$, thus we can make the attack without using $N$ or example messages. Incremental $c$ will do, thus with mild optimization the cost is dominated by the computation of the checksum, at least if there is no other constraint on $m$ beyond the checksum. Even with such extra constraint, it still is possible to choose many bytes of the forged message without much increase in search cost. The high-order ones are particularly malleable: we choose $c$ such that the high bytes of its square are as desired, which merely requires computing a square root.


By what modulo calculations with discrete logarithms are performed?

Neither of the question's alternative hold.
For any $n>1$, and any $a$ with $\gcd(a,n)=1$,
$$a^k \equiv b \pmod n\quad\iff\quad k \equiv \log_a b \pmod{\text{ord}_n(a)}$$
where $\text{ord}_n(a)$ is the order of $a$ in the multiplicative group $\mathbb Z_n^*$, that is the smallest $r\ge1$ with $a^r\equiv1\pmod n$.
The order of an element divides the order of the group, which is $\varphi(n)$ for group $\mathbb Z_n^*$, where $\varphi$ is Euler's totient function. Therefore
$$k\equiv\log_a b \pmod{\varphi(n)}\quad\implies\quad a^k \equiv b \pmod n$$
When $a$ is a generator of $\mathbb Z_n^*$, which is testable as $a^{\varphi(n)/q}\not\equiv1\bmod p$ for every prime $q$ dividing $\varphi(n)$, we simply have
$$a^k \equiv b \pmod n\quad\iff\quad k \equiv \log_a b \pmod{\varphi(n)}$$

Restating this for prime $p$, and any $a$ with $a\not\equiv0\pmod p$,
$$k\equiv\log_a b \pmod{(p-1)}\quad\implies\quad a^k \equiv b \pmod p$$
and, for the lowest $r\ge1$ dividing $p-1$ such that $a^r\equiv1\pmod p$,
$$a^k \equiv b \pmod p\quad\iff\quad k \equiv \log_a b \pmod{r}$$
When $a$ is a generator of $\mathbb Z_p^*$, which is testable as $a^{(p-1)/q}\not\equiv1\bmod p$ for every prime $q$ dividing $(p-1)$, we simply have
$$a^k \equiv b \pmod p\quad\iff\quad k \equiv \log_a b \pmod{(p-1)}$$


Increase number of rounds for SPN and Feistel ciphers

Usually, more rounds increase security as long as subkeys are independent of each other. That's a critical point.

Consider AES-128 as currently defined, with its ten rounds; that's eleven 128-bit subkeys. Adding six rounds means adding six extra 128-bit subkeys. The original AES-128 is still there. If the six extra subkeys are generated independently of the first eleven subkeys, then they cannot decrease security. Security can thus only increase. However, there are important caveats:

In practice, subkeys are not independent of each other. They are produced from the encryption key using a process (the key schedule) which is rather simple and cannot be considered to be a reasonably secure PRNG by itself. The AES key schedule is known to be somewhat weak to analysis, when pushed outside of its intended usage scenario (e.g. it has non-fatal related-key attacks).
If extra rounds do not decrease security, there is no guarantee that they will increase security. Personally, I tend to refuse to consider an algorithm stronger than another as long as both are in the "cannot break it" zone. Such comparisons rely on prophetic assumptions on how technology will evolve in the far future, sometimes quite far in the absurd (it makes little sense to compare 230-bit keys with 260-bit keys while still using an hypothetical classical computer, since it would require eating full stars to power it).

Increasing the number of rounds is more about building trust. That's still science, but not computer science; rather psychology. Increasing the number of rounds gives the feeling that "we are doing something against attacks". It is like making some offerings to Nammu, Sumerian goddess of the sea, before going on a cruise; at least, it won't harm -- except for the off-chance that Poseidon gets displeased at your allegiance to the competition... In the case of AES, increasing the number of rounds does lower performance, although this is not significant in most contexts (AES encryption speed is rarely a bottleneck; e.g. Microsoft measured that applying AES-based Transparent Data Encryption on SQL Server implied an average CPU overhead of 3 to 5%, no more).


Exponentiating big numbers for RSA operation

The basic algorithm is square and optionally multiply.
start with 1 as your accumulator and then for each bit of exponent from MSB to LSB you square your result and if the bit is set multiply by base and appy modulus after each operation.
For any leading zeros you are just squaring 1 which doesn't do anything, just like we want. Then after the first set bit you get your base. After a 10 for example you get your base squared and so forth.

Edit: following fgrieu's comment I will add a second Right to Left method.
When looking at the exponent in binary we see it is the sum of powers of 2, and the result of the exponentiation is the product of the exponent by these powers. The resulting algorithm is:

Initialize acc=1, power=base //123
For each bit b from right to left do:

2.1. If bit is set: acc = acc * power % mod

2.2. power = power * power % mod

result is in acc


We have given $c = m^{17} \bmod (N=pqrk)$ with $k = p+q+r$
We can write this as $$m^{17} =  c + \ell (pqr)k$$ for some integer $\ell$.
Now consider this as $$m^{17} =  c + (\ell pqr)k$$
if $m < k$ you can find the $m$ if not information is lost and the answer is not unique.


Symmetric encryption construction (meet-in-the-middle attack)

The CBC ciphertext $C_1 \mathbin\| \cdots \mathbin\| C_\ell$ for plaintext $P_1 \mathbin\| \cdots \mathbin\| P_\ell$ under key $K_1$ is $$C_i = E_{K_1}(P_i \oplus C_{i-1}),$$ where $C_0 = \mathit{IV}_1$.  If you then apply ECB decryption under $K_1$, you'll get the ‘ciphertext’ $C'_1 \mathbin\| \cdots \mathbin\| C'_\ell$ where $$C'_i = E_{K_1}^{-1}(C_i).$$  If you then use CBC encryption with a different key and IV, you'll get $C''_1 \mathbin\| \cdots \mathbin\| C''_\ell$ where $$C''_i = E_{K_2}^{-1}(C'_i) \oplus C'_{i-1},$$ where $C'_0 = \mathit{IV}_2$.

If you simplify by canceling inverses, do either of the keys $K_1$ or $K_2$ still figure into this?  If yes, can you find a plaintext/ciphertext pair with an unknown intermediate quantity on which you could apply a meet-in-the-middle attack?  If no, do you even need to apply a meet-in-the-middle attack at all?


What is the most popular cipher suite used in TLS 1.2 for HTTPS?

The first web search hit I find is:

https://scotthelme.co.uk/alexa-top-1-million-analysis-february-2018/

This claims that the most widely supported cipher suite among the Alexa top 1m sites is ECDHE-RSA-AES256-GCM-SHA384, supported by 147 985 servers.  Raw data and methodology are at the link.

Other links found by a quick search that may have similar data about HTTPS servers:

https://jve.linuxwall.info/blog/index.php?post/TLS_Survey
https://www.ssllabs.com/ssl-pulse/

(This answer will be outdated within a year or two, if not in months.)

If you are trying to decide what cipher suites to configure your HTTPS server to use, based on what browsers you want to support and what software you're running on the server, you should use this tool: https://mozilla.github.io/server-side-tls/ssl-config-generator/

If these don't answer your question, you'll need to be more specific about why the quick web search results aren't what you're looking for.

Beware that AES, GCM, RSA, and ECDH in that cipher suite are likely to be vulnerable to timing side channel attacks if implemented in software!


Does key authentication in SSH protect from MitM?

How do cryptography in SSH(2) work?

This is a very broad question. If you're interested in the details, then read the relevant RFCs that describe the SSH protocol. In particular:

RFC 4253 - The Secure Shell (SSH) Transport Protocol
RFC 4252 - The Secure Shell (SSH) Authentication Protocol

  Does key authentication in SSH(2) protect from MitM by providing authentication and integrity and why?

Assuming you're referring to Public Key Authentication (where a client authenticates by proving they hold the private key of a pre-shared public key), then not directly/entirely. Public key authentication is a feature of the SSH Authentication Protocol, which runs on top of the SSH Transport Protocol, and generally assumes that the transport protocol provides confidentiality and integrity.

The Public Key Authentication does provide some protection against mitm attacks (by associating the proof of the private key with the SSH session ID), which will prevent the mitm passing on the private key proof as an authentication credential, but won't prevent an attacker using other credentials to access the target system.

The primary mechanism for man-in-the-middle prevention in the SSH Transport Protocol is the verification of pre-shared (or otherwise verifiable via some trusted channel) host keys.

RFC 4251 - The Secure Shell (SSH) Protocol Architecture discusses potential Man-in-the-middle attacks on the SSH protocol and the approaches taken to prevent them.


Hash algorithm strength is important, but it is not so important in key derivation functions. It is unlikely that even if SHA-1 is broken that it would influence the security of PBKDF2. You are better off using SHA-1, and increase the iteration count up to a level that is tweaked for your specific configuration.

If you must, you could use Bouncy Castle to create an implementation of PBKDF2 with SHA-256. The internal security of the algorithm is not that important, if your server is relatively safe against side channel attacks (and for PBKDF2 it likely is). So using a non-certified open source solution would probably not compromise your security.

Your efforts are probably better spend elsewhere. Congratulate yourself on choosing a relatively good password based KDF, choose a 64 bit random salt and use a higher iteration count, and move on...

Note: if you want to protect against hardware accelerated attacks, you may want to consider scrypt instead of PBKDF2.

The Oracle JDK 1.8 contains PBKDF2 implementations for SHA-512 "PBKDF2WithHmacSHA512". This can be used for compatibility with other systems or for deprecating SHA-1 entirely.