Creating Random Pad from XORed Sections of Pi

There's no benefit whatsoever to using XOR here. Pi is already believed to be Normal which means the stream of digits is indistinguishable from random in every base.

The offset into Pi functions as a key, for your system to be secure this key must be very large (e.g. several dozen decimal digits long) and chosen entirely at random, and it must not become known to anybody except the communication parties. With those constraints you should just use a stream cipher which is intended for this purpose.

If you just believe that "Nobody" would guess that your "three digits" are the key to a cipher based on Pi and so it's safe to just transmit the key to the other party you're relying on Security by Obscurity and might just as well use mirror writing or pig latin or something.


PKCS#1: Purpose of `Padding1` in EMSA-PSS encoding method

I conjecture that this salt is essentially a version number for future extensions, tasked with ensuring that signature per another version using a different salt is not a valid signature for the version described.
I can imagine two other roles:

It makes it even less likely that an RSASSA-PSS signature comes to match an RSA-PSS signature of something pre-existing starting with a hash (but there's also the 0xBC for right padding of EM playing that role). Recall that RSA-PSS was introducted by Mihir Bellare and Phillip Rogaway's The Exact Security of Digital Signatures - How to Sign with RSA and Rabin, in proceedings of EuroCrypt 1996; and it's reduction to practice RSASSA-PSS is a slight variation, as explained in notes of section 9.1 of PKCS#1v2.2.
It makes it less untrue that the hash function / random oracle producing $M'$ is independent from the one producing $\text{mHash}$ and the one used inside MFG1, which arguably is a silent assumption in the security argument.


Why aren't zero-knowledge proofs used in practice for authentication?

Answering the question in your title (and not addressing your proposed alternative which I don't quite understand) there is a zero knowledge proof of password protocol "SRP" which is fast and effective.

SRP does not seem to have been given as wide publicity as it should get. Having implemented it, and being an advocate of its use, I don't really understand why everyone doesn't use it all the time. Some reasoning that I have seen for dismissing it are:

A belief that a server is either totally 'good', or totally 'bad', and that using HTTPS ensures you always talk to 'good' servers, which can be trusted with plaintext passwords. Real life just isn't like the movies; it is more complex. The Heartbleed debacle shows that an otherwise trustworthy site can be leaking bits of memory such that a plaintext password sent over HTTPS can be observed by 3rd parties. More common would be poor error handling in custom website code which would print out a plaintext password into a log file which can be read by an intruder who can only see the file system on the server. Large systems stream logs to a central local exactly to make it easier to look at errors in logs where many people can search for patterns.
A belief that the client is either fully secure, or totally compromised, such that an attacker can see nothing, else can record what is being typed. If an attacker can record what is being typed they can steal the password directly; SRP only protects against interception on the wire and the TLS protects the wire. In reality interception is much more routine than people realise even using well configured HTTPS. Large employers routinely decrypt and scan HTTPS to protect themselves from intellect property theft by their employees. Even if they are only doing this to protect their own digital property rights it increases the risk of bugs leaking plaintext passwords or else a rogue employee stealing passwords. Big laptop suppliers install things like superfish to decrypt customers HTTPS traffic to sell "smart ads" on pages. They might not be all bad people; but it increases the risks of bugs leaking passwords or else a rogue employee stealing them. There have also been examples of certs being compromised meaning that encrypted traffic can be snooped. All this means that it might often be the case that an attacker cannot directly record what the user typed at the keyboard; but can view anything passed over the network even when HTTPS is being used. SRP can protect against any such interception as it is a zero knowledge password proof.
A belief that SRP is an positioned as an alternative to HTTPS. SRP does not (out of the box) verify the server (upon registration) so you might be talking to a fake server. So in an "either-or comparison" of SRP and HTTPS (assuming none of the problems detailed above) then HTTPS is often judged superior. This is a false dichotomy as in practice real world HTTPS has many weaknesses which can be addressed by using SRP over HTTPS. Performing SRP over HTTPS gives you server verification which strengthens SRP. So people should always be using both together.
A lot of focus on two factor authentication as an enhancement to plaintext passwords. Companies who have identified that passwords are high risk tend to employ a second factor (say, a text to your phone). The site may still leak passwords, which users may be using on multiple sites, many of which don't use a second factor. If sites upgraded to use SRP and a second factor they would fully protect their users.

When it comes to implementing SRP there are a couple of inhibitors:

A historic lack of a pure JavaScript examples. An early authoritative demo used a Java applet. Recently after the Heartbleed debacle there has been a revival of SRP and there are now a few solid opensource JavaScript libraries and demos.
An extra round trip to login. With plaintext you send username and password in one post. With SRP you first send username to get the salt (and a challenge) and then generate the password proof to send to the server. Most web security frameworks assume that everything is sent in one round trip. This can be addressed by an AJAX call for the first round trip and posting the password proof as the password. More sites are now splitting username and password across two pages to implement ”social login”. Based on your email given at the first page they present a password page that targets the correct social login server. This two page pattern fits well with SRP and end users are becoming more familiar with it.

Having said all of that there is no good reason why every site doesn't now use SRP. So you are correct in being surprised that plaintext passwords are still in use.

Update: I still encounter quite aggressive push back about SRP from crypto experts who are arguing about TLS being sufficient. I am sure they are only hired by high security outfits that (in theory) would never make the mistakes listed above. The fact that they use their theoretical knowledge to shoot down a practical additional defence in depth strategy of both TLS and SRP is a surprise to me. I didn't become a fan of SRP for theoretical reasons. I became a fan after the online banking system I had just upgraded failed its penetration testing with perfectly configured TLS with the external tester managing to harvestest live passwords. As my grandfather told me ”In theory, both theory and practice are the same. In practice, they are not.” Passenger airlines use redundancy to keep people alive. Security practitioners should use defence in depth rather than a theoretical model of security.


Would xoring 2 independant AES CTRs to produce p-rand introduce vulnerabilities?

No, this is safe.

In fact, if you show a way of distinguish the stream $AES_{k_1}(C) \oplus AES_{k_2}(C)$ from a random stream with fewer than $2^{64}$ outputs, you have just demonstrated a way of distinguishing AES from a random permutation.

Here is how this works: suppose we are given Oracle assess to a permutation $P$, which might be $AES_{k_1}$ for some unknown key $k_1$, or might be a truly random permutation.

Then, we ask the Oracle for the values $P(C), P(C+1), ..., P(C+n)$, select a random $k_2$, and compute the sequence $P(C)\oplus AES_{k_2}(C), P(C+1)\oplus AES_{k_2}(C+1), ..., P(C+n)\oplus AES_{k_2}(C+n)$.  Then, we run our stream distinguisher on that.

If $P = AES_{k_1}$ for some $k_1$, then this is precisely your stream, and the distinguisher will say "Yes"

If $P$ is a random permutation, well, with fewer than $2^{64}$ outputs, we can treat it as a random function (as collisions are inprobable).   With $P$ as a random function, any value $(C+i)\oplus AES_{k_2}(C+i)$ is a random value; hence the whole stream is a random string, and so the distinguisher will say "No".


Yes, this is basically the Goldreich-Goldwasser-Micali construction of a PRF from a PRG. All leaves of the tree appear independently random, and furthermore the construction works even if the tree has exponentially many leaves (note that it is possible to compute the value at one leaf without computing the entire tree, by focusing just on the root-to-leaf path).

You can find a formal proof of security for this construction in section 6.3 of my book (PDF link).

  Goldreich, Oded, Shafi Goldwasser, and Silvio Micali. "How To Construct Random Functions." Foundations of Computer Science, 1984. 25th Annual Symposium on. IEEE, 1984.


Proving equivalency of two security definitions of symmetric encryption schemes

Intuitive idea: the first definition is saying that an adversary can not do significantly better than random guessing. The second definition says that for two different inputs, the adversary would have the same probability of guessing 1. So to prove the equivalence, start with the first definition. Run this privacy experiment with two different inputs, subtract them, this is your second definition.


Laplace mechanism in Differential Privacy

These two formulas are the same thing. The second formula is the probability density function of the Laplace distribution centered on 0 ($\mu=0$) — although rather than $Pr[v]$, the second PDF should probably have used a notation like $f(v)$ to make it clear that this is a probability density function and not the probability of returning exactly $v$.
If the question about "how to implement the Laplace mechanism" was referring to something you want to do in practice, then you probably don't want to do it yourself; but you want to use an implementation safe against floating-point attacks. Here's an example of open-source software you can use (disclaimer: I'm part of the team behind that library).


Does using modulo (%) affect quality of randomness?

Let me begin by saying that if you have a hardware source of randomness, you don't need to be stingy with it.

1) Does modulo affect the quality of randomness, faking in some way the distribution of values?

Yes, it does. Or at any rate, it can --- see my answer to (3) below for more details. (I'm assuming by "quality of randomness", you specifically mean that each possible output should be equally likely, and every output should be independent of the others.)

For example, let's say that you wanted to generate a random integer between zero and three. If you did this by rolling a fair six-sided die (with sides labeled zero through five) and taking the result modulo four, what would the resulting distribution look like? Well, rolling either a 0 or a 4 would cause you to output 0, so the probability of outputting a 0 would be 2/6. On the other hand, the only way you'd output a 3 would be if you actually rolled a 3. So the probability of outputting a 3 would be 1/6. This means that you'd output a 0 twice as often as you'd output a 3.

2) I'm not sure whether bits gathered from /dev/hwrng can be considered truly random, but I guess so, since its entropy is based on a physical phenomenon.

The term "truly random" usually means by definition based on some physical source of randomness. But truly random doesn't imply uniformly random. In the example above, the output of a dice roll modulo four was truly random, but some outputs were more likely than others. Physical processes rarely produce a uniform distribution. They have biases -- for example, they might produce a normal distribution -- and often have state (leading to correlations).

It's possible to transform true randomness into uniform randomness using so-called randomness extractors (aka entropy extractors). It's possible that an extractor is already built into the bcm2708. But I'm not aware of any documentation that establishes this.

Various /dev/random implementations include (attempts at) randomness extractors internally. If you trust these algorithms, you can always read bits from /dev/hwrng into /dev/urandom, and then read from /dev/urandom.

3) Can I use 2 bytes instead of 4 bytes as int size, assuming that the needed range of generated values is low (eg: maximum value = 200)? I mean, probably 2 bytes are enough for small numbers. I ask this, because of the question (1): probably using bigger ranges in od results in higher quality of randomness when using modulo

Your intuition is correct here; if you're taking the result modulo some small number, then you can reduce bias to an acceptably small amount by using a really large range of numbers to begin with.

Concretely, if you start with a (uniform) random number in $\{0, 1, \ldots, N - 1\}$ and take the result modulo n, the result will differ from a uniform distribution by statistical distance of less than $(N \mod n)/N$. This is a useful measure because statistical distance is in turn an upperbound on how much you're increasing an attacker's probability of mounting a successful attack. So if you're protecting nuclear launch codes, you'd probably want to keep $(N \mod n)/N < 2^{-80}$. If you're protecting against SSH access to your media server, $(N \mod n)/N < 2^{-30}$ is probably a comfortable security  margin.

Note than if N is divisible by n, there's no bias whatsoever introduced during this step. In your context, N will be a power of two (either $N = 2^{16}$ if you use two bytes, or $N = 2^{32}$ if you use four). So if n is a smaller power of two, you're good.

4) Is using /dev/hwrng only for the seed value still true randomness? I would use the default PHP rand() as PRNG

From the PHP documentation:

  This function [rand()] does not generate cryptographically secure values, and should not be used for cryptographic purposes. If you need a cryptographically secure value, consider using openssl_random_pseudo_bytes() instead.

To answer your more general question, though: No. Given a 128-bit seed, it's mathematically impossible to generate more than 128 bits of "true" randomness (as measured by, e.g., min-entropy). But: Given a 128-bit seed and a cryptographically secure PRNG, this doesn't really matter. A 128 bit seed is plenty for all practical purposes. "True randomness" doesn't really gain you anything after that point.


Regular and Efficient doubling in $GF(2^n)$


Yes, it is possible with a symmetric system.

One way would be if we had a public prime $p$, and secret keys $k_1, k_2$ which are values relatively prime to $p-1$.

And, we define $E_k(M) = M^k \bmod p$; decryption then is $D_k(M) = M^{k^{-1} \bmod p-1} \bmod p$ (the value $k^{-1} \bmod p-1$ is easy to compute, given $k$).

And, for $K_{12} = K_1 \cdot K_2 \bmod p-1$, we have $E_{K_{12}}(M) = E_{K_1}(E_{K_2}(M))$


What Feistel network block ciphers do not use data-dependent table lookups or modular additions?

I didn't wish to post an answer because I don't want invent any scheme that may cause security hole in somebody elses' system. But here I'll do a bit of illustration for you.

Because both Gimli and Keccak have large enough block size in their typical instantiation, we can simply put key in one half and cipher block data in another half (zero-extend if needed repeat key bytes if needed, as is being done with ChaCha20 and Salsa ciphers):

Gimli: [ data 128 bits | key 128,192,256 bits ] 384 bits.

Invoke the permutation:

Gimli: [ Random....... | Bitstring........... ] 384 bits.

And bring it into the Feistal network:

[ Block half A | Block half B ] // Plaintext block.
       |              |
       |      Key     V
   data:->[Permute]->[+]
       |              |
       V              V
[ Block half A | Block half B']
       |              |
       V      Key'    |
      [+]<-[Permute]<-:data
       |              |
       V              V
[ Block half A'| Block half B'] // Ciphertext block.

Possible ways to increase security:

Increase the number of rounds from 2 to higher,
Derive a key schedule for example by running the permutation in XOF sponge mode.


Can sleeper agents in a public network find each other and avoid infiltration?

I'm looking for a way for one message recipient to distinguish steganographic (or other) messages from a friend client from similar messages from a foe client.

That's possible only if there's something friends know that foes don't. And if we talk crypto implemented by local-run software, that thing must be a key. If that key is not in the software itself, and that software is public, then it must be an input of the software available selectively to the "friend" instances. That does not seem to be the case here.
If we nevertheless assume such a key, we can think of using an authenticated encryption which cryptogram is indistinguishable from random for one without the key, which gives a method to hide the traffic in a context where there is legitimate reason to send arbitrary-looking data blobs like hashes. However:

If the software is public, the fact that it has provision allowing this can't be hidden. Only the use of that provision can perhaps be hidden.
That method rules out that one without the key can make a static analysis of a packet's content to tell if it contains a hidden payload (or which). But it can't rule out that such hidden payload gets indirectly detected by other means (like analysis of if there's any other reason a node could send a packet like this at that time; or the effect of that packet on the friend client software receiving it).


Is it possible to perform an MPC protocol to compute a product in a polynomial ring?

You mention a ring but you are only using the multiplication operation. So it's really just a protocol for a group operation that you want. If the group is abelian, then there is a simple classical protocol for $n$-party group product:

Each party performs $n$-out-of-$n$ multiplicative secret sharing of their input. In more detail, party $i$ has input $P_i$ and chooses random polynomials $P_{i,j}$ so that $\prod_j P_{i,j} = P_i$, then privately sends $P_{i,j}$ to party $j$.
Each party $j$ now has $\{ P_{i,j} \mid i \in [n] \}$. He/she computes their product $P'_j = \prod_i P_{i,j}$ and publicly announces $P'_j$.
If the group is abelian, then $\prod_j P'_j = \prod_{i,j} P_{i,j} = \prod_i P_i$, so everyone can compute the final answer from the public $P'_j$ values.

Furthermore, the view of any number of colluding semi-honest parties leaks no more than the final result.


How can a stream cipher encrypt one bit at a time and still be secure?

TL;DR that bit relies on a large state and a lot of calculations that cannot be easily reversed, as you seem to believe.

A stream cipher creates a key stream that depends on the input key material (key seed). Although the stream cipher outputs one bit at a time (usually one byte at a time in implementations for obvious reasons) that doesn't mean that the internal state is of that size. The internal state will generally be larger than the security strength of the cipher.

Before even a single bit is output the state must be updated so that the output is indistinguishable from random to an adversary. Sometimes this is not entirely the case if the stream cipher is (partially) broken: the initial output stream of RC4 is distinguishable from random; it is required to first remove the head of the key stream to create a - relatively - secure cipher.

It should not be possible to calculate any significant part of the state or any part of the key by an adversary.

To use a stream cipher it is of high importance that the key / nonce combination for each encryption remains unique. If this isn't the case then a lot of information can be retrieved from the messages encrypted with the same combination.


Soundness idea of basic zero knowledge prood

There are a couple of problems with this zero knowledge proof;

it isn't explained very well
it gives the verifier more information than it claims to

Lets go through them in order:

  It isn't explained very well

The problem is that the terminology it uses in the proof statement differs from the terminology they use in the protocol description; for example, the protocol uses this value 'r' without explaining what that value is.  Here's the protocol redone to use the same terminology:

         Prover                         Verifier
--------------------------------------------------
Prover selects random value k
y = g^k mod n            y
                 --------------->
                                   Verifier chooses challenge bit c
                         c
                 <---------------
s = k + c*a mod n-1
                         s
                 --------------->  check if g^s mod n = y*h^c mod n

The idea is that, if the protocol is run honestly and if $h = g^a$, then the check will always verify, because $g^s = g^{k + ca} = g^k \cdot g^{ac} = y \cdot h^c$.  The further idea is that someone could try to create a valid looking transcript by selecting s and c first, and then computing $y = g^s (h^c)^{-1}$, with the hope that these randomly selected values would be indistinguishable from a valid set.

  It gives the verifier more information than it claims to

It claims to just show that $h \in <g>$, or in other words, there exists an $a$ such that $h = g^a$.  However, the verifier can deduce more than that; not only can he deduce that such an $a$ exists; but in addition that the prover knows that value.  In fact, this Zero Knowledge Proof is actually a proof-of-knowledge of the value of $a$, not just its existence.

You can show that we cannot really create the 'Zero Knowledge Proof' of a nontrival binary statement (one which is either true or false, but nontrivial in the sense that it cannot be deduced directly).  The reason is that the existence of such a ZKP protocol would allow someone to deduce the statement directly (without a prover being involved).  Consider if we had such a ZPF protocol, then someone could just assume that binary statement, and run the proof/verification mechanism honestly with themselves; if the proof verifies, then they have learned that the statement must be true.


In RSA encryption, does the value of e need to be random?

Yes, this thinking is correct; there is no requirement that the public exponent $e$ to be random.  After all, it doesn't matter whether $e$ can be guessed by an attacker; we'll be including that value in the public key anyways.

Common practice is currently to use the fixed value $65537 =2^{16} +1$ for $e$.  Any odd value of $e > 1$ will work; however, smaller values of $e$ will tend to make the system brittle against errors in performing the RSA padding.


Without any additional knowledge? No.

The problem here is, that this understanding of security is wrong / too weak. Ciphertext-only attacks is the weakest kind of attack model, which is only relevant for classical ciphers any more.

To consider a cryptosystem secure today, it has to resist the much stronger attacks, most commonly the chosen-plaintext attacks and (in the case of public key crypto) chosen ciphertext attack. And on the other hand, we also don't require the attacker to decrypt the actual message. We consider the system broken if the attacker can distinguish messages already, for instance  ciphertext indistinguishability.

  ... without calculating the private key?

If the attack goal would be decryption, the only known way is to break the private key. It is unknown, if the RSA problem and the factorization problem are equivalent or not. And if we had an algorithm which could decrypt but not calculate the private key, this question would be solved.


If an attacker has a chosen-plaintext and encrypted data, can they determine the encryption type?

In fact, good password hashing libraries do not try to hide the used algorithm but document it instead, because it allows to transparently change to a better algorithm without knowing the user passwords: when a user tries to login, the library looks at the registered hash and uses the documented algorithm to compute the hash from the clear text password. If then do not match, login is rejected. If they match and the algorithm is the current one, access is granted and nothing more happens, but if they match and the algo is not the current one, a new hash with the current algo is registered. For example, Modular Crypt Format prepends the hash with $digit$ where digit is (from man crypt):

       1.   MD5
       2.   Blowfish
       3.   NT-Hash
       4.   (unused)
       5.   SHA-256
       6.   SHA-512

Other crypt formats may be easily added.  An example salt would be:

      $4$thesalt$rest

If you are in that case, only one single hashed password is enough to know the used algorithm, and it is not a security problem, provided the algorithm is non invertible.


Given an input x, can a distinguisher D output 1/2?

Such a distinguisher is certainly valid. In fact, in many proofs of security, we use this strategy. In particular, assume that there is some event that can be detected by $D$ with some non-negligible probability $\epsilon=\epsilon(n)$ when $D$ is given distribution $X$, but not when given distribution $Y$. You can use this to build a distinguisher but the problem is that the distinguisher needs to distinguish with probability non-negligibly greater than $1/2$ over all possible samples. In order to bridge this gap, we typically have $D$ output 1 if the detected value is received and output a random bit otherwise. This means that $D$ outputs 1 on distribution $X$ with probability $\epsilon \cdot 1 + (1-\epsilon)\cdot\frac12 = \frac12 + \frac\epsilon2$. If this detected event never happens on distribution $Y$, then $D$ will output 1 with probability $\frac12$ on random, and so it distinguishes with non-negligible probability $\frac\epsilon2$. Note that sometimes the detected event does happen on distribution $Y$ as well. But if it is with negligible probability then it's still OK. Letting $\mu=\mu(n)$ be a negligible function, we would have that $D$ outputs 1 on distribution $Y$ with probability $\frac12 + \frac\mu2$ (using the same computation as above) and the distinguishing probability is $\frac\epsilon2 - \frac\mu2$. Since $\epsilon$ is non-negligible and $\mu$ is negligible, this is still a non-negligible probability.


What security differences are there between E(p',"well-known-plaintext") vs. hash(p') where p'=KDF(p)

It is important to make sure that password based key derivation takes place before passphrase correctness is checked. Otherwise, possible attacker can choose if they attack against passphrase correctness check or pbkdf function.
(Appears ok on the both functions.)

PasswordSafe
In case of very high entropy key, it theoretically could be possible that for instance SHA-256(P') would be easier to break than the key. However, for any typical passwords, expected amount of entropy is (possibly) between 10 and 80 bits, and thus the passwords are likely weaker than the hash. (Thus appears ok.)

bcrypt
I don't like decision to use blowfish encryption in crypt. This is because cryptographic key should usually be used only for very small (preferably one) purpose. The use in blowfish algorithm "consumes" allowed key uses. Maybe blowfish is the weakest link?

Overall, it seems that both choices should appear good enough for common practice, but I think the PasswordSafe's choice of SHA-256 appears even more conservative and secure. However, using SHA-256 appears extraneous as well.


Can ECDSA signature signing and verification process replaces password hashed based login system?

Yes, this is secure provided the message to be signed is unique on each login to prevent replay attacks.  Usually that's done with either a random challenge or the signature over a shared secret.
In fact, SSH does this already with ECDSA keys: the two sides agree on a shared secret, which is hashed, and the client signs the hashed secret and some other data to verify that it's allowed to log in.  MariaDB also does a similar thing by deriving an Ed25519 key (which isn't exactly ECDSA, but is similar) and using that to sign a random challenge (although it doesn't necessarily derive this key in a secure way).
Similarly, most FIDO2 and WebAuthn two-factor authentication devices, such as YubiKeys, use this approach.  You could also use TLS client certs that are ECDSA, which is another approach used in some environments.
This could be used for any type of login, including websites, but it is less common there because people don't expect to carry a key around with them everywhere and frequently log into websites from different computers, so it's practically inconvenient.  But ignoring the practical problems, this is secure if implemented correctly.


Cryptography system that limits the length of the encypted message

As encryption scheme that could only encrypt fix length message is a important essence in cryptography, e.g. one-time pad.  Block cipher is a better example, e.g. AES is a popular block cipher whose block size is 128 bits.  While given such block cipher who could only encrypt 128-bit string, you can construct encryption scheme that encrypt arbitrary length string.

The security of the encryption scheme is not determined by the length of message but by the length of the key.  For example, AES has variant using 128-bit, 192-bit, 256-bit key.  AES-256, who use 256-bit key, is considered to be safer.

Finally, for ultimate security, you should use one-time pad.  One-time pad is information-theoretically secure which means the most powerful adversary can not break the cipher.  The disadvantage is the key could be only used once.  You could store multiple keys in your devices.  10MB space could store more than 60000 pre-shared keys, which sustain 60000 secure SMS message.


Is there a problem using Diffie-Hellman over a Mersenne prime?

I'm assuming the reason they are not used is that something about the
  special form allows fast discrete logarithm computations

Yes, the Special Number Field Sieve (SNFS) which is a faster version of the General Number Field Sieve (GNFS). More specifically the best known discrete logarithm computation with the GNFS was with a 768-bit safe prime. The best known result with SNFS is 1039-bit for factoring (which should have comparable work-load as discrete log) and 1024-bit for discrete log (using a specifically crafted prime).

As you can see, while 2048-bit or larger primes aren't feasible with the SNFS either, these primes have a structural weakness, which cryptographers like to avoid. Actually the cost of picking larger primes to defend against SNFS probably would probably far outweigh the gains from the special form and the faster reduction.

  Reductions modulo Mersenne primes are extremely fast

Which is why the "256-bit security" NIST elliptic curve P-521 uses $2^{521}-1$ as the underlying field-prime.

  Same question also applies to pseudo-Mersenne primes, of the form $2^n−c$ for small $c$, which also have fast reductions.

Which was done with Curve25519 which uses $2^{255}-19$ as the underlying field-prime.


Question about IV/initialization vectors

It depends on the encryption mode you're using:

For CTR, CFB and OFB modes, the IV simply needs to be distinct for every ciphertext encrypted with the same key.  (For CFB and OFB modes with less than full-block feedback, there are certain "weak IVs" that should also be avoided.)
For CBC mode, the IV needs to be unpredictable.  One way to achieve that is to generate the IVs randomly, although other methods (such as encrypting a counter with the raw AES block cipher — preferably with a separate key, if there's any chance that an attacker might be able to control the counter — and using the result as the IV) can also be used.

In any case, the IV does not need to be kept secret.  If it had to be secret, it would be called a key instead.

Also note that none of the traditional encryption modes mentioned above are secure against chosen-ciphertext attacks (i.e. attacks where the attacker modifies the ciphertext, or makes up fake ciphertext out of whole cloth, and sends it to the recipient to see what happens).  In particular, all of them (but especially CTR and OFB) are malleable, so that an attacker who can flip bits in the ciphertext may be able to flip corresponding bits in the plaintext.  Unprotected CBC mode is also vulnerable to padding oracle attacks, unless special care is taken to prevent them (and, even then, it still remains somewhat malleable).

To protect your messages from modification and to avoid such chosen-ciphertext attacks, you'll need to either use an authenticated encryption mode, or compute a message authentication code (such as HMAC) on the ciphertext (and IV!) after encryption (and verify it before decryption).


The two primary techniques I'm familiar with is structuring a cryptographic primitive as a sequence of games and the universally composable security framework.

Sequence of Games
The idea here is to represent a protocol/primitive as a game played between an attacker and a challenger. You define a bad event and show through the game that the event happens with (close to) some target probability (say 1/2 or 0). For example, if we are modeling an RNG and want to show that the attacker can only guess the next output bit with probability very close to (formally, negligibly close to) 1/2. If they are able to do better than that, then the RNG isn't very good. 1/2 is chosen since there are only 2 choices for the next bit (0 or 1) and they should occur each with probability approximately 1/2 so an attacker who simply always guesses 0, for example, should be right 50% of the time.

The paper I linked to above has some good examples.

UC Framework
This is a framework proposed by Canetti that sees a lot of use in protocols, especially multiparty computation, but is useful in many situations. The UC framework defines a scenario where we have a real world with an environment $\mathcal{Z}$, an adversary $\mathcal{A}$ and an ideal world with the same environment, a simulator $\mathcal{S}$ and an ideal functionality $\mathcal{F}$. In each world, we also have the participant parties $p_1,\dots,p_n$. The setup is pictured below (taken from Martin Geisler's dissertation):

In the real world, the parties execute some protocol $\pi$, in the ideal world the ideal functionality $\mathcal{F}$ provides the same functionality as $\pi$ but is secure by definition (think a trusted, uncorruptable third party). The UC Security theorem says that $\pi$ securely realizes $\mathcal{F}$ in the real world if there exists a simulator $\mathcal{S}$ in the ideal world such that $\mathcal{Z}$ cannot distingush the two worlds. In other words, if $\mathcal{Z}$ cannot tell which world they are operating in, then $\pi$ must be at least as secure as $\mathcal{F}$. But $\mathcal{F}$ is as secure as possible by definition, so in this case $\pi$ is also secure.

Another cool thing about the UC framework is the composability theorem which says that UC-secure protocols can be composed with other UC-secure protocols (including itself) in arbitrary (even adversary controlled) ways and the resulting composition is also UC-secure. Canetti's paper above has examples.

Reduction
A third technique that is often used is a reduction proof. This is very similar to reduction proofs in theoretical computer science. Basically it says we have some problem $X$ which is hard to break (how exactly that is determined is beyond the scope of the answer, but usually it is that a bunch of really smart people have been trying to break it and haven't). Say I have a new cryptosystem and have shown that breaking my cryptosystem is equivalent to breaking $Y$, i.e., if you break $Y$ you can break my problem. Then, if I can show that breaking $Y$ is at least as hard as breaking $X$, then there is reason to believe my cryptosystem is also secure. For example, see this answer.


Does keeping a PGP crypted message private helps?

Of course, if a message is encrypted and on a secure and secret storage it will impossible to compromise its security, because if the message is not available at all to an adversary, how could he attack it?

By the way, if it is correctly encrypted with a key of reasonably length its security is not compromised even if the encrypted message is made available to the adversary. The confidentiality protection is one, the main probably, of the security property of the cryptography and the threat model is exactly this one. Usually in proving encryption schemes the property researcher look for is the semantic security, meaning that even a bit of information cannot be recovered from the ciphertext.

In pratice it depends on your encryption scheme. If the message is encrypted with something that is at the state of the art, well implemented there is no risk and you can sleep well with no worries.

If you want to estimate the time window of security you could check the KeyLength page.

For the same reason keeping several encrypted message togheter does not leak information and does not represent a risk. In security proofs an adversary is supposed to have access to a decryption oracle and he is allowed to ask for a reasonable number of decryptions (but the challenge message) and the encryption is still secure. On the other hand, if your public key is known by the attacker (and it is supposed to be known, as it is public) the attacker is able to encrypt whatever he wants with your key, so he is able to get a bunch of encrypted messages (even better, knwon plaintext and ciphertext).


What differentiates a password hash from a cryptographic hash besides speed?

To the best of my knowledge there is no formal distinction, since "password hashes" aren't formally defined.

That said, if you look at this presentation from the author of scrypt you'll see that he wanted:

Password hashing to be CPU hard (i.e. to require significant amounts of CPU processing, in a manner that cannot be optimized away).
Password hashing to be memory hard, i.e. to require large amounts of RAM capacity and RAM I/O bandwidth.

Being CPU hard helps delay offline brute force password breaking, as you note. Being memory hard helps guard against getting dramatic speedups from using a different type of hardware.

Simple SHA hashes require minimal internal state, and can as such be massively accelerated by running hashing in parallel on the 256+ cores of a modern graphics card. An even larger speedup could be had by creating a bunch of FPGA / ASIC chips dedicated to running SHA operations in parallel.

Being memory-hard gives a measure of protection against this, because currently there is no cheap technology to scale memory-I/O. FPGA's are comparatively 'cheap' to make; but large amounts of low-latency memory isn't.

To your questions:

  I can just run SHA-256 100000 times?

If you loop through the same hash function many times, then there might be a small loss of entropy each time, if the hash function isn't ideal. See "Why does PBKDF2 xor the iterations ..". If you improve your own suggestion, for example by mixing in the salt at each iteration, then you get close to the design of PBKDF2. In that case you should use PBKDF2 instead, because PBKDF2 is a mature and peer reviewed design.

  Furthermore, it seems relatively extensible to adapt to increases in computing power. [...] I can just reapply the hash to my password hashes 100000 times and at verification time run SHA-256 100000*100000

That works. At verification time the end user gives you his password in plain text. So you could also verify the password against the old hash using the old hashing function, and create a new hash from the plaintext, using the new hashing function.

For more, see the scrypt presentation as well as the hash + password tag on Crypto, as well as the past discussions here.

Please note: It's great that you learn about this for your own interest and understanding. When it comes to building production software, you should not create your own password hashing implementation -- you should use an appropriate higher-level library, one that has seen extensive security scrutiny.


ElGamal - What if the Decisional Diffie-Hellmann problem could be solved?

Let $\mathcal{A}(g^a,g^b,g^c)$ be a DDH adversary which will return 1 if it thinks that $c = ab$, and return 0 if it thinks that $c$ is chosen from random.

Let $a$ is a private key and $g^a$ is a public key, we can attack IND-CPA of ElGamal encryption as follows.

Random $m_0,m_1$ and send them to the challenger.
The challenger will random $b$ and send $(g^b,g^{ab} m_i)$ back, where $i$ is the experiment number.
We can call $\mathcal{A}(g^a,g^b,\frac{g^{ab}m_i}{m_0})$. If it returns 1, we will guess that we are in Experiment 0, but, if it returns 0, we will guess that we are in Experiment 1.

Now we can distinguish between Experiment 0 and Experiment 1 easily.


Reuse nonce with Salsa20 stream cipher with counter

[What] if I keep the same nonce, but increment the block counter
  depending on the amout of blocks exchanged so far?

This is a "bad" idea.
What Salsa20 is doing can be considered to be "CTR-Mode like" $E_k(IV\parallel CTR)$ where you have to supply $k$ and $IV$.

If you were allowed to supply $IV'=IV\parallel CTR$ this would also mean you'd to absolutely make sure that no two blocks ever happen to share the same $IV'$ under the same key. Even worse to make sure this doesn't happen, you'd have to pick $IV'$ at random (or actually keep track of all the blocks encrypted under the key) as opposed to being able to just increment $IV$ (= uniqueness).

Note that this change was made to the usual API of authenticated encryption schemes to avoid the above mentioned problems and this approach is now standard with modern authenticated encryption schemes (like ChaCha20-Poly1305 and AES-GCM)


Making my steganography code more hard to detect and crack

Some general advice about steganography:

Much like in the physical world, the smaller what you want to hide, the easiest that goal is. Thus you may want to compress the payload(s), and treat the result as the new, smaller payload consisting of arbitrary bits. Because your payload consists of images, some lossy scheme such as JPEG or JPEG 2000 might be used to get excellent compression. Also, the bigger the apparent vector message is, the easier hiding into it is (all other things being equal, like the format of that vector message).
Shuffling bits (second bullet in the question) is a primitive technique to try to make data unintelligible. In order to protect the confidentiality of the payload, use encryption. If done correctly, that makes it demonstrably hopeless to recover the original payload from the message (as opposed to detecting the presence of the payload), for one not holding the decryption key. One simple form of encryption is generating a pseudo-random stream of data from a key, and exclusive-ORing that with the plaintext (possibly compressed as above), with the caveat that the same portion of the stream must never be reused (see e.g. AES-CTR). Using authenticated encryption (e.g. AES-GCM) can in addition make it hopeless for an adversary to induce an undetected alteration of the hidden message.
Now comes the hard part: hiding the modified payload into a vector message (here, passable as an image) in a way such that presence of the payload won't be discovered. Stenography schemes attempting that could be rated on three coarse levels:

Undetectability depends on the adversary (interceptor trying to prove there is a message hidden) not knowing the scheme itself. An example would be sending the payload in a portion of a vector file that most normal programs skip, like some comment field, or trailer. Such schemes fail as soon as known.
Undetectability  relies on the adversary not noticing some minute characteristics of the vector data. An example would be encoding the payload in the low bit of the bytes coding the RGB values in the vector, leaving all the rest untouched. Such schemes often fail (for example if the pristine vector is an uncompressed computer screen capture at a moment when a GUI is displaying areas of exactly uniform color, there will be extreme redundancy in the low-oder bits, and the scheme described will remove that, enabling detection, perhaps even with a sharp eye).
Undetectability  (to some quantifiable degree) is demonstrable under some assumptions, typically that a key is unknown to the adversary, and most critically assuming a model of the data in the vector (sorry, my only simple example is when that model is: true random data). In a real world, such schemes still can fail because the adversary has some better model (e.g. taking into account some details about how a particular camera allegedly the source of the vector image generates its files, or some characteristics of its sensor or lens).

In addition, some steganography schemes have another, even harder goal: prevent removal of the hidden payload without drastically altering the perceived quality of the vector (or at least, by casual transformation leaving the vector mostly undisturbed, e.g. saving an image as highly-compressed JPEG, or recoding digital audio as MP3). That would be necessary in some DRM schemes. Sometime this is called (digital) watermarking, but the analogy with the eponymous printing paper-manufacturing technique is reversed: in DRM, the designer's hope is that an unauthorized copy holds the watermark/payload, when on a banknote the hope is that the watermark is not copied. The three coarse levels above hold with some alterations.


How to check the integrity of a key received through mail using symmetric encryption?

Unfortunately, symmetric encryption do not provide integrity and digital signature functions. This is because symmetric encryption uses the same key for exncryption and decryption. This means that any who owns the decryption key can alter the data and no one will notice that the data is altered, because the same key was used for encryption.

This means that data integrity can be provided only by using asymmetric cryptography.


Can RSA with padding detect all errors in ciphertext?

First, when using padding (PKCS or OAEP), if the chiphertext has
  errors in transmission we'll we always get an error at the decyption
  process?

Yes, with extremely high probability. This is basically a chosen ciphertext attack and RSA-OAEP is fully immune to them, so the odds that you won't detect this attack (a.k.a. "error") are extremely low (below $2^{-128}$).

  Will it detect all errors, or is there a possibility that a certain
  combination of errors will result in a decryption but with a false
  result in plaintext?

This is possible but extremely unlikely, again due to the IND-CCA2 security of RSA-OAEP.

  Second, if no padding is used, (i believe it is called vanilla rsa?)
  and there are errors on the ciphertext, then the decryption will work
  any time but will give wrong results instead of the original encrypted
  plaintext?

Sometimes it's called "textbook RSA", "plain RSA" or "unpadded RSA".
If you follow the textbook RSA description, any errors will change the value of the ciphertext, resulting in a different number being decoded, resulting in an (unrelated) decryption, which will always work. If the error is malicious it could be exploited, depending on the reaction of the system.

  Finally with padding or not, with no errors on ciphertext and by using
  a wrong private key will we get an error in decryption or just a false
  decrypted plaintext?

If you use a wrong private key $d$, which, by definition, doesn't satisfy $ed\equiv 1 \pmod{\lambda(n)}$, you'll decrypt a wrong message, which will lead to a verification error for OAEP and to a simple wrong message for unpadded RSA.


Why does Ed25519 scalar multiplication allow values larger than the subgroup order?

My understanding of elliptic curves has me thinking that the range of accepted values for scalar point multiplication should be in [0, group_order].

Actually, that's not the case - the point multiplication $xG$ is well-defined for all integer values of $x$.

  While it could accept larger values since $(n+x)G=xG$, it would be wasteful computationally so I'd expect the function to constrain it to the group order or always mod it before using it.

Well, cryptographically that would be valid, however that would allow a further "optimization" that Dan wanted to avoid allowing to well-meaning implementors.

If someone were to implement the point multiplication $xG$ in the straight-forward manner (where $x$ is a number between $0$ and $n$), they might notice that, some of the time, $x$ was fewer than 252 bits - in that case, they might be tempted to skip those iterations of the point multiplication logic (and so speed things up slightly).  That might sound like a nice optimization, however that introduces a (small) timing leak (as the time taken depends on secret data), and Dan really wants to avoid any such leakage.

By ensuring that $x$ is a number between $2^{254}$ and $2^{254}+n$ (and thus is a fixed number of bits), any such optimization is far less straight-forward (and so far less likely to occur to our well-meaning implementator)


HMAC based challenge-response authentication

That's as secure as a symmetric challenge-response authentication can be. Some remarks:

In an authentication protocol, the only assurance is that the authenticated party participated in the protocol. It could well be that there's a man-in-the-middle.
Step 1 (sending client ID) can be coalesced into 3 if all clients have to authenticate that way regardless of ID.
At step 2, the server's challenge should be unique and unpredictable. Making that reliable is less easy than it seems.
At step 4, the server must be able to get or regenerate the client's key, from a database of random keys, or a master key and a key derivation function.

The big problems are

Said database or master key could leak for the server, and poof goes all security. One good mitigation is to use a security token (HSM, Smart Card..) in the server, programmed so that it can only check the response to challenges.
The ultimate solution from the standpoint of avoiding server leaks is when there is noting secret in there. Challenge/response replacing HMAC with a signature allows just that.
Authentication is one thing, securing what follows next is better. That's why we have authentication-and-key-agreement protocols. Good ones resist man-in-the-middle.
The client's key (symmetric or asymmetric) can be compromised on the client side. A password (and proper password-based key derivation) to encipher the key-at-rest in the client might help, but is less convenient than directly using the password as an authentication mean. That's why we have SRP and ISO/IEC 11770-4.


if your $e$ is coprime to $p-1$ where $p=2^{255}-19$ you can calculate the $e$-th of an integer modulo $p$ which means you can recover $E(m)$ given $E(m)^e$. In fact, if the condition holds, there exist $u,v \in \mathbb{Z}$ such that $eu+(p-1)v=1$ (Bezout's identity). Now, we are looking for an integer $x$ such that $x \equiv a^{1/e} \pmod p$ i.e. $x^e \equiv a \pmod p$. It is easy to find it: $a^u \equiv x^{eu} \equiv x^{1-(p-1)v} \equiv x\times (x^{p-1})^{(-v)}\equiv x \pmod p$ because $x^{p-1} \equiv 1 \pmod p$ according to Fermat's little theorem.


As fgrieu points out, the number of states reached is at most $2^\ell-1$ and that is achieved only if the feedback polynomial is a primitive polynomial (and the initial state is not all
zero). If the feedback polynomial is irreducible but not primitive, then with
nonzero initial loading, the LFSR state will cycle through $N$ states, where $N$ is a
divisor of $2^\ell-1$ but not a divisor of $2^m-1$ for any $m$ that is itself a proper divisor
of $\ell$. For example, if the feedback polynomial is an irreducible but nonprimitive polynomial of degree $6$, then, depending on which polynomial is being considered, the
LFSR will cycle through $21$ states, or through $9$ states. The $63$ nonzero states
form $3$ cycles of $21$ states each, or $7$ cycles of $9$ states each. Depending on
the initial loading, the LFSR will cycle through one of these cycles (and the other
cycles will never occur).

For an arbitrary feedback polynomial, which could be reducible, that is,
factorable into a product of (not necessarily distinct) irreducible polynomials
(meaning something like $[f(x)]^2g(x)$ might be the factorization),
the answer is much messier and complicated to describe. Search for the
term period of a polynomial and read Lidl and Neiderriter's Finite
Fields or Chapter 6 of Berlekamp's Algebraic Coding Theory for some
of the details.


Fully Homomorphic Encryption over the Integers - perform an operation on an encrypted data

It's actually straight-forward; we'll assume that all the inputs are either encrypted versions of 0, or encrypted version of 1; then:

We can replace an AND gate with just an FHE multiplication of the two inputs:

$$AND(x,y) = x*y$$

Where $*$ is our Homeomorpic multiplcation operation.  This obviously evaluates to an encrypted 1 if both of the inputs are encryped 1's; and an encrypted 0 if either of the inputs are encryped 0's
To replace an exclusive or gate, we encrypt the constants 1 and -1, and then compute:

$$XOR(x,y) = x*(1 + (-1 * y)) + y*(1 + (-1 * x))$$

Where + is our homeomorphic addition operation, and 1 and -1 stand for our encrypted constants.
To replace an or gate, we take our encrypted 1 and -1 constants, and compute:

$$OR(x,y) = 1 + -1 * (-1 + x) * (-1 + y)$$
To replace a NOT gate (that doesn't appear in your circuit, but does come up in others), we compute:

$$NOT(x) = 1 + -1 * x$$

It is easy to see that, in all cases, if the inputs are restricted to encrypted 0 and encrypted 1, the result is either an encrypted 0 or an encrypted 1 (and which will be the logical result of the operation).  Obviously, things can be simplified somewhat if our FHE operation includes a subtraction operation.

As for the number of operations used, we just translate each gate and count them up.  On the other hand, this construction is really a proof that just addition and multiplication suffice to be complete operations (that is, given just those two operations, we can compute anything); when you look at operation count, it turns out to be quite inefficient.


What is the expected number of different sequences of bits in the collection that contains $2^{800}$ elements?

Every input $G(i) \mathbin\| S$ to $P$ is distinct.  If $P$ were a uniform random permutation, the random function $x \mapsto F(P(x))$ would have almost uniform distribution.  So the answer can't be much different from the number of distinct 800-bit strings in an independent uniform random sampling of $2^{800}$ of them, which is a fraction of $$1 - (1 - 1/2^{800})^{2^{800}} \approx 1 - e^{-1}$$ of them by the usual reason.  The fact that $S$ is chosen independently at random is not relevant to this analysis; the same analysis would apply if $S = 0$.


Do companies like CipherCloud really have the option to use homomorphic encryption?

Is there a technically feasible way for companies like CipherCloud to use homomorphic encryption (HE) while preserving full functionality in a third party SaaS app (e.g. Salesforce)?

Fully homomorphic encryption can theoretically1 compute any function. Therefore, if a computer can perform a task on plaintexts, then fully homomorphic encryption could theoretically be used to perform that exact same task on ciphertexts.

It seems like your doubt stems from an equality check. From your example, you seem to believe that because there are say two rows in the database that belong to the same user, that FHE would not be able to combine the sales amounts of those two rows. In other words, how would FHE know that the two encrypted customerName values are the same?

The answer is, the FHE computation wouldn't need to know that the two customerName values are the same. Instead, it would compute an encrypted bit. If they are the same, the encrypted bit encrypts 1, else it encrypts 0. This is a very feasible computation with FHE. Once it knows that bit, it would sum in the bit times the dailySales value. Thus, if the bit is 1, the dailySales value is added in. If the bit is 0, the dailySales value is not added in (since 0 times anything is 0).

Thus, given your table, say you want to know the top 1 customer. Presumably you have a table of encrypted customerName values. For each encrypted customerName value, you'd step through every entry in the sales table, computing the bit for that row, then adding in the bit times the dailySales value for that row. You'd save the result along with the customerName value. Once you've done that for every possible customerName, you'd use FHE to find the one with the largest encrypted sum, and return that to the user. The user could then decrypt the values and learn who was the top customer.

This is a good example of how, yes, FHE allows you to compute any function, but the method of doing it sometimes requires some tricks.

  Furthermore, can it be done without requiring that the third party SaaS app be modified?

In general I would expect that the answer is no, w/o modification it could not be done. There are maybe a few corner/special cases where it could possibly.

For example, if dailySales value in the database is an int32, then an encrypted version will definitely not fit in the int32 slot. In which case the DB would have to be modified. If, however, the DB had originally been setup to store everything as, say, an unlimited size string, then FHE encrypted values could be encoded as a string (pick your favorite method) then stored that way.

The client software would either have to do the encryption itself, or a proxy could be used. So in that sense, the client would likely have to be modified (at least to point to the proxy). Let's assume you use a proxy. The client sends the entry to the proxy, the proxy encrypts it and submits it to the SaaS app.

The proxy would also have to be smart enough to translate queries. For example a query for the top customer would not be able to be run directly on the SaaS app. Instead the proxy would have to translate it into a query for the entire table, then run the process I described previously.

The proxy would only know the customer's public key, so the proxy couldn't return the plaintext answer. The customer would receive an encrypted answer to the query which it would have to decrypt.

I imagine this would be the process that would have to be done.

Note, the client doesn't really have to send FHE encrypted values to the proxy. The client could encrypt the values with AES, then send the AES key encrypted with the FHE public key. The proxy uses that encrypted key to homomorphically decrypt the values. The output is the user's values encrypted with FHE. Using this technique, the client would have to do very little FHE encrypting.

1. I say theoretically as FHE is still not practical today.


Your question is a bit broad for a completely detailed answer: pseudosquares is essentially a subgroup of $\mathbb{Z}_n$ (for an RSA modulus $n$) with particular properties, based on which a considerable number of cryptographic protocols have been designed. Nevertheless, having done some work on primitives that rely crucially on the properties of pseudosquares, I will try to give you an intuition of some aspects that I found important:

Protocols involving sending a square are inherently more difficult to be made secure against malicious adversaries. This is because when dealing with malicious adversaries, you must ensure that they remain honest. However, given an element of $\mathbb{Z}_n$ with Jacobi symbol $1$, it is computationally infeasible to determine whether this number is a square or not (this is the quadratic residuosity assumption). Hence, to ensure that a player indeed send a square, you must rely on expensive zero-knowledge proofs to check it. If, however, your protocol can be directly built using pseudosquares instead of squares, you remove this burden: checking whether a number is a pseudosquare (ie computing the Jacobi symbol) can be done in polynomial time (even without the factorization).
There is a very natural cryptosystem associated with the group of pseudosquares: to encrypt 0, send a random square, to encrypt $1$ send a random non-square pseudosquare. More formally, the public key is a non-square pseudosquare $y$, and encrypting a bit $b$ is done by computing $c = y^{2r+b}$ for a random integer $r$. With the factorization, one can recover $b$ by chechking whether $c$ is a square. The security comes from the quadratic residuosity assumption. This is the Goldwasser-Micali encryption scheme. Actually, this scheme has many good properties: it s randomizable, homomorphic for the xor operation, lossy (id est, the public key can come in two forms, either $y$ is a square and the encryption perfectly masks the bit, or it is a non-square and $b$ can be decrypted; this property is very useful to make security proofs of cryptographic schemes). It also allows for the design of oblivious transfer protocols (hence multiparty computation), among a considerable number of other applications.
Another example of the power of pseudosquares is identity based encryption. Primitives used in classical cryptography - such as ElGamal and RSA - are powerful tools, but they do not have enough structure to allow for some more involved cryptographic constructions, such as identity-based encryption. Indeed, IBE seems to require groups with more structures, such as pairings, or lattice-based cryptography. In this field, the Cock cryptosystem is an OVNI: it's an identity based encryption scheme based solely on the quadratic residuosity assumption, hence dealing with pseudosquares. Its existence suggests that pseudosquares enjoy very interesting and non-trivial features that cannot be found in, e.g., groups of squares, prime order fields ore elliptic curves without pairings.


Since

$$X' = F(X, k) = P(S(E(X) \oplus k ))$$

the value of key $K$ is an element of the set

$$ \{V \oplus E(R_0): V \in S^{-1}(P^{-1}(Z)) \}$$

where

$$Z = R_1 \oplus L_0$$

and

$$
S^{-1}(P^{-1}(Z))
$$
is the set of possible inverse images of the parallel map of the Sboxes $S$ which is not one to one.

Total number of possible keys is $2^{16}$ because Sboxes are not bijective, there are $4$ possible inputs leading to same output.


Stream vs Block cipher: Synchronising and the receiver

The answer to your question will very much depend on implementation details, but you might not be versed enough in cryptographic protocol development to know exactly what to ask, so I'll take a stab at answering this and hopefully my attempt will help you refine the question as needed.

  How are the blocks/streams after decryption synchronized at the receiver to form one long meaningful message?

Sychronization is often done before decryption. Wrap the ciphertext with a protocol header, throw a sequence number into the protocol header, authenticate the entire thing (header and ciphertext). The receiver, after checking authentication, can order the ciphertexts using the sequence number and then decrypt.

  Am I right by saying that stream cipher will incur a LOT more overhead while synchronizing?

If you look at my description of how synchronization could be done, you'll notice that it is symmetric-key cipher agnostic. Thus the synchronization will be the same whether we are using a block cipher or a stream cipher.


Understanding public key cryptography example

Interesting premise.
Q : "Is the ad encrypted with his private key ..."
A : no, I don't believe so
Edit - To clarify, I entertained the possibility that the author meant to say "private key" in item #4, but once you consider the subsequent paragraph in the source (excerpt below), I don't think the ciphertext that describes the crime in advance is encrypted with public-key cryptography. I reckon the author's protagonist is using the same bytes that are in the public key as the key for a symmetric cipher. (In this case, KDF could potentially be HKDF, PBKDF2, Argon2, scrypt, or even a keyed hash-digest.) eg.
broker_pk = PUBLIC_KEY( secret_key )
ciphDetailsOfCrime = E( KDF(broker_pk) , EvilPlanToMakeCelebsEvenMoreFamous )

eph_cli_pk = PUBLIC_KEY( ephemeral_client_secret_key )
kRequestForQuote = DH_or_ECDH( broker_pk , ephemeral_client_secret_key )
ciphRFQ = E( kRequestForQuote , DetailsOfNewTarget )
msg = eph_cli_pk || ciphRFQ

(This is a contrived example that shouldn't be used, especially if conspiring to commit murder and/ or acts of terrorism.) My original answer continues ...
It may be that the author meant to say "private key" in list item #4, however, I suspect the author is thinking about using the public key, posted on billboards, as a symmetric key (or password to be used in some key derivation function - aka. KDF) to decrypt the prior description of the heinously foul act of murdering film celebrities en masse ...
The paragraph that follows is:

"You have now made sure that everyone in the world has, or can get, your public key – and knows that it belongs to an organization willing and able to kill people. Once you have taken steps to tell people how to post messages where you can read them, everyone in the world will know how to send you messages that nobody else can read and how to identify messages that can only have come from you. You are now in business as a middleman selling the services of hit men. Actual assassinations still have to take place in realspace, so being a hit man still has risks. But the problem of locating a hit man – when you are not yourself a regular participant in illegal markets – has been solved."


There is a very recent paper that solves this problem at a large scale using secure computation techniques:

  How to (not) share a password: Privacy preserving protocols for finding heavy hitters with adversarial behavior: Moni Naor, Benny Pinkas, Eyal Ronen

They motivate the problem from the point of view of passwords (they want to identify passwords that are too common), but it seems like the same problem you propose.


How does a birthday attack on a hashing algorithm work?

The method described in the link you cited is based on Floyd's cycle finding algorithm, also known as "the tortoise and the hare" algorithm.  This is a general-purpose algorithm for detecting cycles in iterated maps, which I will first describe below.

Specifically, consider the sequence $(x_i)$ defined by $x_i = H(x_{i-1})$ for some map $H$ and some initial value $x_0$.  If this sequence is cyclic, then we have some integers $j > 0$ and $k > 0$ such that $x_j = x_{j+k}$, and thus also $x_i = x_{i+nk}$ for all integers $i \ge j$ and $n \ge 0$.

In particular, this holds for $i = nk$ and any integer $n$ satisfying $n \ge j/k$, yielding $x_i = x_{2i}$.
Thus, if the sequence $(x_i)$ is cyclic, there exists an integer $i > 0$ such that $x_i = x_{2i}$.  Conversely, the existence of such an integer also clearly implies that the sequence must be cyclic (with a period that evenly divides $i$).

It thus follows that, to detect cycles in the sequence $(x_i)$, it suffices to check whether $x_i = x_{2i}$ for any positive integer $i$.  We can do this iteratively using constant space by keeping track of two elements of the sequence, $y = x_i$ and $z = x_{2i}$ (both initialized to $x_0$ at iteration $i = 0$), and, on each successive iteration, updating them as $y \gets H(y)$ and $z \gets H(H(z))$.

If we find such an $i$, we'll know that the sequence $(x_i)$ is cyclic.  Now, we have two possibilities: either the initial value $x_0$ is part of the cycle, or it is not.  In the latter case, we have $x_0 \ne x_i$ but $$H^{(i)}(x_0) = x_i = x_{2i} = H^{(i)}(x_i),$$ and we've thus found a collision in the $i$-fold iterated map $H^{(i)}$, which in turn implies the existence of a collision in the underlying map $H$.

All that remains to be done is locating the underlying collision.  To accomplish that, we rewind the iteration back $i$ steps, so that $y = x_0$ and $z = x_i$, and advance them one step at a time, this time as $y \gets H(y)$ and $z \gets H(z)$ so that, at iteration $j$, we'll always have $y = x_j$ and $z = x_{i+j}$.  Since we know that $x_0 \ne x_i$ and $x_i = x_{2i}$, it follows that there must be some $j$ between $0$ and $i-1$ such that $x_j \ne x_{i+j}$ but $x_{j+1} = x_{i+j+1}$, and thus $H(x_j) = H(x_{i+j})$.  When we find that $j$ — i.e. when we find the first $y$ and $z$ such that $H(y) = H(z)$ — we stop; that's the collision we've been looking for.

This algorithm only requires space for storing a fixed number of values: $x_0$, $y$ and $z$.  How much time does it take?  Well, if $j$ and $k$ are the lowest positive integers satisfying $x_j = x_{j+k}$, then Floyd's cycle finding algorithm will take $i = k \lceil j/k \rceil < k(j/k + 1) = j + k $ steps (each involving three evaluations of $H$) to detect the cycle, and then $j$ further steps (involving two evaluations of $H$) to locate the collision, for a total of up to $5j + 3k \le 5(j+k)$ evaluations of $H$.

Now, if $H$ is a random function on an $m$-element set, then, by the birthday paradox, the expected number of steps $\mathbb E[j+k]$ before the first collision is $O(\sqrt{m})$.  Thus, the expected runtime of the collision-finding algorithm described above is also $O(\sqrt{m})$.


specific scenario question relating to using NACL crypto_box in a protocol

Yes, the attacker does have the ability to make messages to appear to be from SenderA. In the end, the crypto_box functionality relies on a MAC, not a signature. That means that it depends on a shared secret key, rather than a private key for message authenticity. As explicitly stated by the protocol, this allows any message to be signed if you possess just one of the private keys. Because in that case you can calculate the shared secret key and - of course - any MAC generated by the shared secret key.

If you require that messages are authentic even if the key of the receiver is lost then you need to use a signature as well. Generally you would then have to use sign-then-encrypt to create a secure protocol, especially if you consider that private keys may get known by the attacker(s) of the system. Obviously the public keys need to be trusted in any scenario.


For a one-time pad, which MAC method is information-theoretically secure?

First of all there does exist information theoretically secure message authentication codes suitable for use with a one time pad. An HMAC is not one of those information theoretically secure.

As far as I recall the first article presenting such a construction is the 1981 article by Wegman and Carter: New hash functions and their use in authentication and set equality

The construction build upon a specific class of universal hash functions. The MAC is constructed by computing a hash tree over the message, and finally applying a one time pad to the MAC tag.

Since we are not talking about a specific hash function but rather a class of hash functions, you will need key material to chose a hash function for each level in the tree. The key material needed at each level will be the same size as the final tag, the number of levels will be logarithmic in the maximum message size.

The key material used to chose hash functions for each level in the tree is reusable. The one time pad applied to the tag is of course not reusable. Quite conveniently the part of the key material which can be used only once is the smaller part, and doesn't grow with the message size.

If you combine this authentication scheme with a one time pad, the number of key bits consumed by the one time pad will be much larger than the number of key bits consumed by the authentication.

But this kind of authentication scheme can also be used in scenarios where you just need the authentication and not the confidentiality. For example the classical channel used in quantum key exchange need authentication but not confidentiality. So the two can supplement each other well as this construction provides the authentication needed for the quantum key exchange, and the quantum key exchange produce a stream of bit suitable for a one time pad, which can then be utilized by the authentication.

I have seen newer constructions than the one from the Wegman Carter article. All of them have build on the idea from the Wegman Carter article. They use the same hash tree plus one time pad construction, but they use other classes of hash functions. If each message will be several MB in size, I believe bucket hashing from a 1997 article by Rogaway is the fastest algorithm.

The question about whether to authenticate or encrypt first is a moot point if you are combining this kind of authentication with a one time pad, because the authentication itself by definition applies a one time pad to the tag.

Whether you apply a single one time pad or two one time pads to the tag doesn't change the security one bit. However if you do end up applying two one time pads, you will use twice as many key bits to achieve the same level of security. This would however only matter for small messages, because for large messages the key bits used for authentication is negligible compared to those used for the one time pad on the message.


Why is it insecure to use a randomized IV for CBC-MAC instead of an all-zero IV?

The nCipher Advisory #13 cited in your securityfocus.com link contains the explanation of the vulnerability (in the section "Cryptographic details").

The CBC-MAC algorithm works similar to the CBC encryption algorithm, but only outputting the final block (or a part of this).
Each block of the plain text is XOR-ed with the previous ciphertext and then encrypted.

This means we XOR the first block with the initialization vector before it first comes into contact with the block cipher. So changing only the first block together with a corresponding change in the initialization vector will mean that the same value is input to the block cipher, which gives the same resulting authentication tag at the end (which does not have to be changed).

If the initialization vector is fixed as zero (or some other constant), there is no way for the attacker to change it together with the first block, and this kind of attack is not possible. As an added bonus, we have one block of data less to transfer.


Is there a strong cryptographic reason for GCM's 2^39 - 256 bit limit?

With concatenation the caller only has to ensure the nonce is unique. For example they can use a counter that increments for each message. Incrementing a counter for each message is convenient in many scenarios, including encrypted network transports like TLS.

If you use xor or add nonce and counter you get overlaps, so a counter as nonce would be fatally broken.
The security of GHash, the MAC part of GCM, decreases as the length of the message increases. This means that it's a good idea to limit the maximal size of messages the receiver is willing to accept.

  forces the scrambling pattern to repeat every 2^32 16-byte block"

The pattern doesn't repeat, you simply MUST not encrypt a message longer than that size.

A 64 GiB message is a very unusual for authenticated encryption, since the receiver can't use the data before they verified the MAC on all of it. Typically you split long data into multiple messages, each with their own MAC. That way the receiver can verify individual blocks and then work with the plaintext, safe in the knowledge that it wasn't manipulated.


Here is an explanation of step 4.
Look at Figure 2 of the paper.
Lets say $y_s$ is $y_3$ at 6 o'clock.
Start at 12 o'clock and calculate going clockwise until you arrive at 6 o'clock. Denote the result by $r$.
Start again at 12 o'clock and calculate going counter-clockwise until you arrive at 6 o'clock. Denote the result by $l$.
Now $l =r \oplus y_s$, which gives the solution $y_s =r \oplus l$.


Which algorithm should be used to replace SHA512withRSA?

In standard Java libraries, SHA512withRSA designates signature per RSASSA-PKCS1-v1_5 with SHA-512. There is no known attack when used with a sufficient RSA modulus size, and SHA-512 is very secure. Given that SHA-512 has a 19-byte DER DigestInfo prefix, and that PKCS1-v1_5 signature further requires 10 bytes and 1 bit more for the modulus, we can tell from the question that the RSA public modulus size is at least 1+(10+19)×8+512=745-bit, but that's far from satisfactory.

The only truly indispensable thing to do is check that RSA public modulus size. Anything below 1024-bit is unsafe, anything below 2048-bit is to upgrade ASAP, when performance is no issue 4096-bit is reasonable, unless we care about quantum computers usable for cryptanalysis, or fairies (there's abundant literature about both).

It might be useful to also switch to RSASSA-PSS (which has a better security argument), but that's a bigger change (including in Known Answer Tests, since RSASSA-PSS signatures change randomly for the same data). It should also be ascertained that MFG1 in RSASSA-PSS does not use SHA-1; that would not be insecure, but is criticizable nevertheless, and often creeps in upgrades from RSAES-PKCS1-v1_5 to RSAES-OAEP in Java code, see this.


Bulletproof - Is it possible to do range proof only from public key?

No, it is not possible to generate a proof only with the knowledge of $Q$; you need the knowledge of $x$.

If it were possible to generate a proof (or fail to generate a proof if $x$ were out of the range), then it would be possible to efficiently recover the value of $x$ by attempting to generate a range proof for $Q - yG = (x - y)G$ for various values of $y$.


Take a look at the military's Dryad for authentication.


How can I resolve this basic MAC paradox I’m stumbling upon in my proof?

Your attack on $S$ involves computing $S'(k,m_i)$ for arbitrary messages $m_1,\dots,m_q$. In order to do that, you must compute $S(k,m_i)$ and $S(k,0^n)$, and thus you have obtained $S(k,0^n)$. This means that $0^n$ must be added to the list of invalid forgeries, and so in order to present a valid forgery for $S$, you must have
$$(m,S(k,m)) \notin \{(0^n,S(k,0^n),(m_1,S(k,m_1)),\dots,(m_q,S(k,m_q))\}.$$

But you do not know how to do that: the only known attack on $S'$ precisely involves computing $S(k,0^n)$. More precisely, the attack goes like this:

Compute $S'(k,m)$ for some $m \ne 0^n$.
Output $(0^n, (s,s))$ as a forgery for $S'$ (where $s = S(k,0^n)$).

Then, you present $(0^n, s)$ as a forgery for $S$, but this is not a valid one.

The exact point where this error manifests itself in your proof is when you write

  because $(m,S(k,m))$ being an element in that set would contradict (*).

This assumes that if $(m,S(k,m))$ is in the second set, that necessarily means that $(m,S'(k,m))$ is in the first one. In other words, that if a "request" for $S(k,m)$ was made, it necessarily means that a request for $S'(k,m)$ was made as well. This is, again, not correct: it is possible to make a request for $S(k,0^n)$ without making one for $S'(k,0^n)$.


Is the HMAC construction really neccessary for a fixed length message?

In summary: Yes, HMAC is the way to go for construction of a MAC from an arbitrary concrete iterated hash. We have no constructive argument of security of the MAC constructs in the question; we even have a concrete attack when using some otherwise apparently fine hashes.

I consider a hash constructed by iterating a compression function $F$ as $s_{i+1}=F(s_i,m_i)$ with $s_i$ of $h$ bits (also the size of the MAC), message blocks $m_i$ of size $b$, perhaps with Merkle-Dåmgard strengthening (this matches MD5, SHA-1, SHA-2, but not Keccak/SHA-3); I also assume Key is of fixed size, enters $m_0$, and the third construct is Hash(Fixed-Sized Length indicator||Key||Message).

Under the assumption that $F$ is an ideal PRF, the three constructs in the question appear to be secure, but perhaps to some sub-optimal degree. The best general attack (that is, valid irrespective of the details of the iterated function) that I see is to obtain the hash of messages of equal size (at least $\max(2b,h)+b$), with the beginning of the message random and the last message block fixed, until a collision is found between distinct $m_0$ and $m_1$ (which requires $\mathcal O(2^{h/2})$ MACs); then obtain the MAC of $\widetilde{m_0}$ with the last bit toggled; that MAC will stands a good chance to also be valid for the similarly modified $\widetilde{m_1}$. That's a valid attack against the MAC. It works because the collision between the MACs for $m_0$ and $m_1$ stands a good chance to have occurred before the last block, and in that case $\widetilde{m_0}$ and $\widetilde{m_1}$ will necessarily collide too.

The above generic attack does apply to HMAC (and CBC-MAC, and any iterated MAC with a single pass). However, HMAC (contrary to the other constructs) comes with security arguments that there is no asymptotically better attack, and even arguments valid with relatively weak assumptions on the iterated function; see Mihir Bellare: New Proofs for NMAC and HMAC: Security without Collision-Resistance, with extended abstract in proceeding of Crypto 2006.

The security arguments of HMAC, and the fact that the key enters both at the start and the end of the computation (which in turn insures, in the above attack, that the attacker does not get to know the colliding value), gives us a security margin. I'm reasonably confident that HMAC-MD5 won't be practically broken (excluding attacks on implementations such as DPA or injected faults) for some years, but I'm not so confident for MACs constructed from MD5 as in the question. Addition: there's a lot of truth in the saying: better safe than sorry.

As an illustration of the superiority of HMAC, we can make an iterated hash such that the three constructs are weak, but HMAC remains strong. An example is SHA-256 modified by removing the 8 additions modulo $2^{32}$ in the 4th (last) step of a round (making that $H_0^{(i)}=a$, .., $H_7^{(i)}=h$). If there's an attack against the collision-resistance, or (first or second) preimage resistance of that modified SHA-256, I fail to see it (update: on second thought, the best I see is a preimage attack similar to this, with cost about $2^{128}$ rather than $2^{256}$ for full SHA-256). However, in the constructs of the question, from a single message/MAC pair, it becomes easy to compute the MAC for any message of the same length differing in blocks after the first (notice that for known blocks and output, it is possible to walk back the hash states). [Addition following strongly critical comment: A key point of my reasoning is that the security argument of HMAC seems to apply when using that modified SHA-256; I'll concede a gap if it irreparably does not; or if since there's a widely accepted definition of security of a hash that this modified SHA-256 fails (quantitatively  at least), but SHA-256 pass (notice that SHA-256, contrary to Keccak/SHA-3, trivialy fails widely accepted definitions of security due to the length-extension property)].


Why is Poly1305 popular given its 'sudden death' properties?

At least in the case of NaCl, Poly1305's "sudden death" properties aren't much worse than XSalsa20's. With any stream cipher, if you reuse the same stream with two messages, then the XOR of the ciphertexts gives you the XOR of the plaintexts. So your security is already ruined by nonce reuse, whether or not you rely on Poly1305.


difference between soundness in ZKPoK and special soundness for sigma proofs

Soundness usually means "you can't prove a false statement". There are different ways to formalise this but usually the probability of an efficient algorithm coming up with a false statement and a proof that verifies is negligible in some parameter (such as the length of the statement). Soundness can be defined for any proof scheme, including ones that are not sigma protocols.

Special soundness is a particular property of sigma protocols. It implies soundness (the chance of making a false proof is at most the inverse of the size of the challenge space) but it implies a lot more, as it can be used to show that sigma protocols are proofs of knowledge.


Does collision resistance imply (or not) second-preimage resistance?

With the definitions that a function $F$ is

collision-resistant when a [computationally bounded] adversary can't [with sizable odds] exhibit any $(a,b)$ with $a\ne b$ and $F(a)=F(b)$;
first-preimage-resistant when, given $f$ determined as $F(a)$ for an unknown random $a$, a [computationally bounded] adversary can't [with sizable odds] exhibit any $b$ with $F(b)=f$;
second-preimage-resistant when, given a random $a$, a [computationally bounded] adversary can't [with sizable odds] exhibit any $b$ with $a\ne b$ and $F(a)=F(b)$

yes, collision-resistance implies second-preimage resistance. Proof by contraposition: assume the property for second-preimage-resistant does not hold. Repeatedly pick a random $a$, perform the attack that exhibits a $b$ with $a\ne b$ and $F(a)=F(b)$, until it succeeds. By our assumption, that requires a feasible amount of work. Once exhibited, that pair $(a,b)$ proves that the property collision-resistant does not hold.

However, as pointed by CodesinChaos in his comment, the answer is no for definitions of collision-resistance and preimage-resistance that quantify the difficulty of finding a collision or (respectively) preimage, to roughly $2^{n/2}$ or (respectively) $2^n$ evaluations, where $n$ is is the number of bits in the output.

Proof by counterexample: for even $n$, assume a hash function $H:\{0,1\}^*\to\{0,1\}^n$  that behaves as a random function. Now construct $F:\{0,1\}^*\to\{0,1\}^n$ as
$$F(x)=\begin{cases}x||x&\text{if }x\text{ has }n/2\text{ bits}\\H(x)&\text{otherwise}\end{cases}$$
$F$ has the collision-resistant property (when $a$ and $b$ are both $n/2$ bits, $a\ne b\implies F(a)\ne F(b)$; when neither $a$ nor $b$ are $n/2$ bits, collision resistance is that of $H$; when a single of $a$ or $b$ is $n/2$ bits, the other must have a hash with two equals halves, and it takes effort about $2^{n/2}$ hashes to exhibit such input). However the following algorithm breaks the second-preimage resistance property for $F$ at cost comparable to $2^{n/2}$ hashes, much less than required: if the random $a$ is not of size $n/2$, compute $H(a)$, and if its two halves are equal (which is expected to occur after $2^{n/2}$ hashes), let $b$ be that bitstring of $n/2$ bits; it holds that $a\ne b$ and $F(a)=F(b)$.

In summary: a function's second-preimage-resistance is always at least as strong as its collision-resistance; but it can be not much stronger, rather than quadratically stronger, which is the theoretical ideal. So depending on definition, collision-resistance implies second-preimage-resistance.. or not! That's true when we keep the same security level (effort and odds of success of adversary) to assess the two properties. That's false when we expect a security level consistent with the property and the function's output size.

Addition following comments: The question links to a paper by Elena Andreeva, Bart Mennink, and Bart Preneel Security Properties of Domain Extenders for Cryptographic Hash Functions. That highly technical paper considers various proposed extension methods to iterate the core building block of a hash function over much larger input than the core block accepts; and if security properties of that core are conserved in the extended construction, to comparable level (work for attack and odds of success).

As any good paper should, that paper gives its specific definitions, and for some established ones refers to its reference [15]: P. Rogaway & T. Shrimpton Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance. All these quantitative definitions stay fully consistent with the classical result that for any given level (work for attack and odds of success), collision-resistance implies second-preimage-resistance.

The paper shows that some extension methods demonstrably (mostly) preserve the level of collision-resistance but do not demonstrably (mostly) preserve the level of second-preimage-resistance. That is entirely consistent with the above rule.

For example, starting from a core block assumed collision-resistant to $\mathcal O(2^{n/2})$ effort and second-preimage-resistant to $\mathcal O(2^n)$ effort, some extender might construct a hash that is collision-resistant to $\mathcal O(2^{n/2})$ effort and second-preimage-resistant to $\mathcal O(2^{2\cdot n/3})$ effort. The less-than-perfect extender conserved the level of collision-resistance, but not the level of second-preimage-resistance. Yet, for the hash built using that extender, collision-resistance to some effort level still implies second-preimage-resistance to that effort level.


Group description in pairing based cryptography

DrLecter's comment should really be an answer, but one point which bears emphasis is that it is not sufficient for crypto purposes to say "a (cyclic) group of prime order $p$", because even though mathematically all groups of order $p$ are essentially the same group (i.e., they are isomorphic), we can't really say the same thing in crypto.

When doing crypto in cyclic groups, we generally make the assumption that the discrete logarithm problem is difficult to solve in the groups in question (most often implicitly through a stronger assumption like those in the DH family). But the choice of a particular cyclic group makes a dramatic difference in the difficulty of solving the discrete logarithm problem, at least in the current state of our knowledge: we know cyclic groups of prime order in which the discrete logarithm problem is easy (which ones?), and others in which it seems to be difficult. And even among the groups in which the discrete logarithm problem is considered difficult, it seems to be more difficult in some than in others.

Hence, any discrete log-based cryptosystem needs to specify explicitly which group it operates in if we want to have any idea of its security. This is what $G$ and $G_t$ represent in the definition of a pairing: they are simply the groups in question (e.g., $G$ is the group of points of the elliptic curve with equation [...] generated by the point [...]).

EDIT: Of course, in abstract discussions we can simply say that $G$ is a cyclic group of prime order in which such-and-such assumption holds, but still we would need to be more specific than just saying we operate in cyclic groups of prime order. It is also very helpful in discussions and proofs to have a name for the groups we are working in, especially in pairing settings where there are two (sometimes three) groups involved.


First of all, the avalanche effect is a desirable effect: it means that a very small change in the input will lead to a very big change in the output.

A security algorithm that doesn't provide this avalanche effect can lead to an easy statistical analysis: if the change of one bit from the input leads to the change of only one bit of the output, then it's easy to guess / try to find the input: just change one bit of it and verify if it was the right one.

How it works in DES: if you take a look at the DES, you'll see that it has 16 rounds and 2 permutations. The real thing happens in the rounds: for each round, the input bits are used to look up for bits that will be used as the output (the S-box). take a look at this presentation, for example. With the shifts that are made at each round, it means that the "index bits" (the ones used to do the table look up) come from the "data bits" from the previous round.

Changing a single bit in the input will cause more bits to be changed in the following rounds. Slide 6.41 of the above presentation shows how many bits will change at each round.


The key part of the entry is "...where σ was not produced by the legitimate signer.". The legitimate signer is the key holder. We assume the adversary does not possess the key, but would like to have a way to produce MAC tags anyways.


Is the key deducible with AES CTR when we know about the plaintext, IV and the ciphertext?

No, that's not possible as long as the security of AES as a block cipher is not weakened.

In CTR mode a counter is encrypted using AES, and the result of that is XOR'ed with the plaintext. The counter actually consists of a nonce part and a counter part. Both the nonce and counter are known by a possible attacker.

If anybody would just be encrypting zeros the you would get exactly the key stream. This is still secure though, because the key used for AES is protected by the block cipher itself. And, as indicated by the comments of Dave Thompson, AES itself is secure against known plaintext attacks.

Basically the same reasoning can be performed for other (well known) block cipher modes of operation; the key is protected by the block cipher, how the result is used is inconsequential to security of the key.


Do we consider all zeros (0000000) as empty block of data or is it still a data?

Either it is a block of data or it isn't, there is no such thing as an "empty block". And yes, it is still data (data is always plural), as it has certain properties such as a size. For AES it needs to be 16 bytes of any value to be considered one block of data.

  Do we really need padding to the data blocks if a disk sector is multiplication of data block?

No, in most disk encryption protocols padding is not required (and the problem is where to store the encrypted block of padding as it doesn't fit in the sector).

  Also if one data block is empty (all 000000) why we just dont apply encryption on that block as usual?

As indicated, it is not empty, and we would use encryption as usual.

  Most of the disk encryption software let us to encrypt used space vs full disk. In case of full disk , how is the empty space being encrypted with AES?

Just like always. Note that empty space - or rather unused space is not necessarily put to all zero. For instance, a quick format only makes sure that the file system meta information is created, commonly at the start of the partition. The rest is left untouched.

  is disk encryption always encrypt data into same location? lets say data from sector 200 will always land after encryption in sector 200? (assuming that we are not adding any HMAC which expands the data).

Depends I guess. Usually you have two situations: encrypting an already existing file system structure and adding information to the file system. If it is encrypted then generally the sectors would probably stay the same for most software, although the physical location may still change (e.g. for an SSD with write leveling). And yes, that can be dangerous.

When writing new data to a "live" file system you'd expect that the data gets encrypted before it is written, so there is no "source sector".

  Does AES keep track which sector of disk is encrypting? Or this info is irrelevant for encryption? I think bitlocker in CBC mode adds IV as encrypted sector number - but is it to keep track on sector number or just to randomize the input (instead of sector number they could just add any random number)

The disk encryption uses AES, AES doesn't use disk encryption. AES is a block cipher algorithm and as such instances of AES doesn't know anything about what task it is performing, other than that required to encrypt or decrypt a single block.

Yes, the IV is just used to randomize the input.


Standardized parameters for elliptic curve cryptography

There are a few more standards, with (sometimes) overlapping sets of parameters:

ANSI X9.62
SECG
Brainpool