Could PAKE via smooth projective hash function protect agaist replay attacks?

And I checked some related works, and most of them only considered the dictionary attack and forward security.

Actually, a PAKE has two security goals:

That someone cannot recover the password from a number of exchanges (with any greater advantage than being able to test $N$ potential passwords using $N$ active attacks).

That someone will not be authenticated without knowing the password (or having a correct guess to it).

Both of these needs to be true even if the adversary has the transcripts of a large number of successful authentications.
The "replay attack" falls in an attempt to violate the second security property.  If the related works did not specifically call that out, the security proofs they presented still need to address that (and if they don't, well, that's a hole in the proof).
All of the PAKEs I'm familiar with handle replay attacks; most of them because the initial message from both sides include some randomness that is different with each exchange, and which is stirred into the later computations; this implies that straight-forward replay attacks will fail.
The exception is Opaque, which has a different defense against replay attacks; the difference is on the replay on the client side,  The adversary can indeed replay the initial message (and get the repeat of the server side message; it doesn't stir in any randomness for this part of the exchange), however the adversary cannot then retrieve the client's private key (stored in some data encrypted with a key that the adversary does not know), and hence will fail in the next stage of the protocol.


Secret key agreement by public discussion from common information

Maurer is likely making unrealistic assumptions about noise. The following excerpt is from the paper's conclusion:

  The paper suggests the following conclusion for the implementation
  of cryptographic systems on given noisy communication
  channels. Such channels should not be converted
  into error-free channels by means of error-correcting codes,
  followed by a cryptographic protocol based on error-free channels
  because this design strategy would imply that Shannon's
  pessimistic inequality (2) applies and therefore perfect secrecy
  cannot be achieved unless an impractically large amount of
  shared secret key is available. Instead, cryptographic coding
  and error-control coding should be combined, resulting in a
  system achieving virtually perfect secrecy, with a (short) secret
  key being required only for authentication.

  The author hopes that this paper and a subsequent paper on
  practical implementations will help to move perfect secrecy
  closer to being practical.

I'm not an expert either, but have an interest in new and unconventional cryptography. With research papers I find it helpful as a first pass to read the abstract and conclusion. Whatever claims made in the conclusion can then be referenced by going back in the paper. In this paper, the reliance on noise and error coding seemed both its strength and weakness.

What happens if an attacker can manipulate the noise/signal of the system? If they were able to reduce the noise of a channel, wouldn't an attacker be able to derive too much information about the cryptography from the coding? Here's a hypothetical attack: attacker Eve deliberately injects noise into a system, making system seem much noisier than it actually is, which the two communicating parties Alice and Bob then derive their probabilistic models from, but when Alice and Bob start exchanging data, Eve removes the noise.

By comparison Diffie-Hellman is a simpler overall scheme that makes no assumption about the underlying communications channel.


Is a tweakable block cipher still considered deterministic in nature?

When talking about encryption with block ciphers, you should distinguish block cipher itself from the mode of operation that employs the block cipher.

Block cipher takes an input $P$ of fixed length $n$ and transforms it under key $K$ (and possibly under other parameters such as tweak $T$) to output $C$ of the same length $n$:
$$
E:\; P \xrightarrow{K(,T)} C.
$$
It is always deterministic in the sense that $C$ is entirely determined by the listed parameters.

A mode of operation $\Pi$ is used to turn a fixed-length block cipher into a variable-length encryption scheme. To achieve semantic security, modes of operation typically uses deterministic nonces or random initialization vectors. In the latter case the resulting schemes are called probabilistic.

The use of tweaks is somewhat orthogonal to this classification. Both deterministic and probabilistic modes may use tweaks to further parametrize the encryption (e.g., in disk encryption).


This is not related to your particular factorization problem (I believe), but is related to a hard matrix factorization problem (I believe). It is known as the "Lattice Isometry Problem" (or perhaps it is the "Lattice isomorphism problem" --- I will call it LIP either way). Stated in matrix terms, this problem is, given two matrices $\mathbf{B}_1, \mathbf{B}_2\in\mathbb{R}^{n\times k}$, determine if they generate isometric lattices.
A lattice generated by some basis $\mathbf{B}\in\mathbb{R}^{n\times k}$ is defined as:
$$\mathcal{L}(\mathbf{B}) = \{\vec x\in\mathbb{R}^n\mid \exists \vec y\in\mathbb{Z}^k\text{ s.t. }\vec x = \mathbf{B}\vec y\} = \mathbf{B}\mathbb{Z}^k$$
As defined, basis of a given lattice are specified up to multiplication by an (integer) change-of-basis matrix on the right, i.e. if $\mathbf{B}\in\mathbb{R}^{n\times k}$ is the basis of a lattice, and $\mathbf{U}\in\mathsf{SL}_k(\mathbb{Z})$, then $\mathbf{BU}$ is a basis of the same lattice.
Two lattices $L, L'$ are said to be isometric if they are related by an orthogonal transformation of determinant 1.
In terms of matrices, $\mathcal{L}(\mathbf{B})$ is isometric to $\mathcal{L}(\mathbf{B}')$ if there exists some $\mathbf{O}\in SO(n)$ such that $\mathbf{O}\mathbf{B} = \mathbf{B}'$.
All combined, this means that the lattice isometry problem takes as input two matrices $\mathbf{B}, \mathbf{B}'$, and attempts to factor $\mathbf{B}' = \mathbf{OBU}$ for $\mathbf{O}\in SO(n)$, $\mathbf{U}\in\mathsf{SL}_k(\mathbb{Z})$, so can be seen as a certain matrix factorization problem.
I don't know precise results for the hardness of LIP, but a certain "natural" extension of it to the ideal lattice setting becomes easier than one would hope for. This is the content of the Gentry-Szydlo algorithm, which determines whether a certain ideal lattice is isometric to $\mathbb{Z}^k$, which can also be described as "having an orthonormal basis".


ECDSA with SHA256 and sepc192r1 curve: Impossible, or how to calculate $e$?

NIST FIPS 186-4 at the end of section 6.4 states that:

  When the length of the output of the hash function is greater than the
  bit length of $n$, then the leftmost $n$ bits of the hash function output
  block shall be used in any calculation using the hash function output
  during the generation or verification of a digital signature.

In section 6.1 they define $n$ as the order of the generator, which makes the wording

  leftmost $n$ bits

wrong. Although it's clear they meant the bit size of $n$.

Which means:

You don't need a bigger curve
BouncyCastle implementation looks correct


How to formally prove that random guess is the best attack

But how to argue there is no better algorithm than guessing?

Show that, if there is a better algorithm than guessing, you can distinguish the PRF from random.


The only security issues that I can think of when sharing the same key among several users (in an asymmetric encryption system used to broadcast messages) are:

We can't revoke a single user without impacting all the others.
We loose the flexibility to encipher to an arbitrary set of users (which, for large messages and when using hybrid encryption, has moderate overhead).
If the key is determined to have leaked to someone not authorized, we no longer know from which user (or user's device) it has leaked from.
If the ability to decipher messages is determined to be available to someone not authorized, we can no longer selectively disable users to try to determine which user (or user's device) is involved in the leak.
If extracting the key form one device requires making a large number of experiments, and that's practically not possible to an adversary (due to a usage counter, or the time required, or because the experiments are destructive), an adversary in a position to use multiple devices with the same key is in a better position than if each device had a unique key.
This is an issue in side-channel protection of Smart Card (where resistance is quantified in number of power traces allowing to recover the key), and some fault-attacks that similarly require many experiments. As an extreme example, if an adversary could force any chosen key bit to 0 or 1, and when that has changed the key the device self-destructs together with all the key bits, and the adversary can find that, then there is a simple attack finding about $2n$ bits of the key shared by $n$ devices, when there is no threatening attack to any individual device.


The correction question you should ask about why various operations in RC4 (or, for that matter, any other cipher) are there would be "if I were to remove that, what would the impact be?  Would this weaken the cipher in some way?"

At your current state of knowledge, that may be a rather imponderable question, but it is still the correct one.  I can try to give you a simple example: if you remove the $S[i]$ from the update of $j$, leaving

j = (j + key[i % keylen]) % 256

Then $j$ will follow a much simpler trajectory through the array as we run the key setup routine.  In particular, if the key bytes just happen to sum to a multiple of 256 (which will happen 1/256 of the time for a random key), then $j$ will visit only (at most) keylen bytes of the array; all the other elements of the array will participate in one swap.  Now, it's not immediately clear how a bias like this might influence the cipher; however it is quite plausible that it wouldn't be good.


Encrypted files in an encrypted partition or folder

In short: does storing these encrypted files in an encrypted partition/folder create the same potential weaknesses as cascade encryption? If not, what of encrypting a .tar of encrypted documents?

An encrypted file inside an encrypted container is a cascade of ciphers, almost by definition.

Is that a problem? Not really. A cascade of ciphers shouldn't be weaker than a single layer of encryption, unless something is wrong – e.g. the keys are not independent.

Concerns about cascades are mostly theoretical – I wouldn't expect the cascade to ever be weaker when you have two different ciphers. There is no easy way to prove that for real world ciphers, however, and there's always the risk of sidechannel attacks and bugs, so it isn't something to recommend as a way to strengthen a system.

In your case it's still the best thing to do, since you don't want all those files to be visible decrypted when the filesystem is mounted.


I recommend against using RAND_pseudo_bytes(). OpenSSL's CPRNG does not provide better pseudo-random numbers than /dev/urandom but it is much harder to use right. It has a couple of known flaws, for example it doesn't handle fork() very well. The standard PRNG is not very well designed, too. The FIPS mode PRNG is a bit better, though.

/dev/urandom (Linux, BSD, Solaris) are about as fast as RAND_pseudo_bytes(). You don't have to take care of seeding, fork hooks, thread locks and other stuff that makes the PRNG hard to use. You can just read as many bytes from /dev/urandom as you need. Windows has CryptGenRandom().

No matter what some people or documents say: ignore /dev/random. /dev/urandom is fine for everything you are going to do.


Are basic replacement ciphers always bad for structured data encryption?

A good encryption should produce data that are indistinguishable from a random stream. If you simply replace bytes with other bytes, and each byte has always the same replacement, many statistical characteristics of the original message remain. For instance, if the original message is text, then the frequency of each letter will remain also after applying byte-by-byte replacement.

by encrypting the data with other methods before passing it through
the basic cipher

If you encrypt the data with other methods, for instance with AES, there is no need to do any further encryption of the encrypted message. AES is unbreakable.
The question about multiple encryption was answered on SE many times. See for instance this.


Since they're all competing, the hash-power used to create a block in 10 minutes, is 1/4 of the total hashing power.

That's not correct.

If the work effort is set to $n$, that is, it takes an expected $2^n$ hashes before someone finds a valid preimage.  If Alice, Bob, Charlie and Eve are all working equally hard, then we would expect that each one would end up computing an average of $2^n / 4$ hashes before someone finds a preimage.  It might be Alice, who has computed only $2^n / 4$ hashes, but still a total of $2^n$ hashes were computed.

So, if Eve goes off on her own, she'll need to compute her own $2^n$ hashes herself before she finds a preimage; in that time, Alice, Bob and Charlie will end up computing $3 \cdot 2^n$ hashes, enough to find an expected 3 links in the hash chain, before Eve can compute one - Eve cannot win this race in the long term.

(Note: this analysis rather assumes that when Alice finds the preimage, she instantly announces it, and the others immediately start searching based for the next preimage.  This isn't precisely true; however that isn't nearly a large enough effect to give Eve an advantage when she has only 1/4 of the computing power)


As a previous commenter pointed out, you're describing the avalanche effect.  In a block cipher, every output bit should be dependent on every input bit.  Changing a single bit of the key or a block of plaintext should, on average, cause half of the bits in the ciphertext block to change.

A cipher that exhibits the avalanche effect is not necessarily secure.  It can still have statistical biases or be vulnerable to attacks such as differential or linear cryptanalysis.


The tricky point is that $\mathbb{F}_2^8$ is not a field; it is a degree-8 vector space. Multiplications are not defined on vector spaces. However, the $A$ transform is defined only on the vector space, not on the field (it is "affine" only when considering its source/destination space as a vector space).

The $\phi$ and $\phi^{-1}$ operations are thus "type conversions". If you think of it in terms of implementations, they are akin to type casts: if $x$ is a vector, then $\phi(x)$ is the same sequence of bits, but interpreted as a field element. So you have to apply $\phi$ (i.e. switch to field interpretation) in order to do field-related things (here, exponentiation), then $\phi^{-1}$ must be apply on the result to go back to vector space interpretation, so that a vector space affine transform ($A$) may be applied.

A possible source of confusion is the notation $\phi^{-1}$ that means "the inverse function" (i.e. the one that goes in the reverse direction), but not "the inverse of the value". The same term ("inverse") and the same notation (exponentiation with $-1$) are used for two very different things.

Also, $z^{254}$ indeed computes the inverse of $z$ in the field $\mathbb{F}_{2^8}$, but it also returns 0 when the source value is 0, which is what we want in AES, while the inverse of 0 is nominally not defined. Hence the use of exponentiation in the formula, instead of inversion.


Do practical key-less cryptosystems exist?

Sure, use AES with a fixed key. Since the key is fixed, it could be considered keyless in the traditional sense. Someone with only access to the ciphertext could not crack it as long as you use a good mode (say GCM, CCM, or EAX) using proper nonces, IVs, or whatever else is required.

This is security by obscurity as the plaintext is only as secure as the fixed key. Since the fixed key is on the devices, it is only as secure as the security of the devices. A physical security breach could leak the keys and thus destroy security. A "cyber" attack could do the same.

Note though, that this security will not continue forever. IV's will eventually repeat, counters will eventually repeat, etc.


Computing only one byte of a cryptographically secure hash function

For SHA-256, given its structure, the savings achievable when computing a single byte of the output is small. Argument: the computation consists of 64 rounds in cascade (or several times that for input of at least 56 bytes); full diffusion is achieved after 8 rounds, therefore all but the last 7 rounds must be computed in full (and then a large fraction of the rest, varying with which byte is kept), therefore savings are (much) less than 7/64 on the rounds, and a little extra operation on the output (worth less than 8 32-bit additions). Thanks to tylo for reporting that diffusion is much slower than I stated.

This is largely true for all common hash functions, but we can not generalize to any hash function. It is easy to construct a hash function of cost about proportional to the width needed (but somewhat inefficient, or insecure).


Self authenticating tamper resistant first meetings

I wouldn't consider voice or video to remain a secure means of identification for much longer.  Advances in real-time video stream editing are near enough to reality that I wouldn't build a new security system on it.

In the olden times in millennia past, you could have the computers on either end display a short MAC for both parties to alternate reading aloud one letter at a time to each other (quickly), and the lack of delay plus the sound of your partner's voice was a pretty good assurance that you weren't being MITM'ed.  But today, the technology available to a sophisticated attacker could render even that approach untrustworthy.

If you are really that paranoid, you need to physically and privately exchange some other kind of okay/duress signal, such as a specific word or phrase; right leg crossed over left; carnation or rose on the table facing right or left; cigarette or other object in the left or right hand; book face down or face up, or any of a thousand other cheesy spy tradecraft signals.  But sometimes the old standbys can't be beat.


Creating an encryption key from several other keys and using hash functions

If the keys have constant, known length, I'd concatenate them, and then apply SHA256. If they have variable length, applying some separation mechanism might be useful.

Truncating hash functions works well. If the original hash function is good, a truncated hash function has the same properties, albeit at a correspondingly lower security level. Truncating SHA-256 is certainly better than using MD5.

I recommend something like:

Truncate(SHA-256(output-size || number-of-keys || sizeof(key1) || key1 || sizeof(key2) || key2 ...), output-size) where output-size <= 256


Shannon entropy calculation: is $H(A|R·A) = H(A)$?

Well, no, in general, it is not.  Here's a simple example that demonstrates it is not:

Suppose that $m=2$, $n \ge 3$ and the matrix $A$ can take one of the following two values:

$\pmatrix{1&2\cr1&1}$ with probability $1/2$, and $\pmatrix{1&2\cr1&2}$ with probability $1/2$

Note that the first matrix is nonsingular (invertible), while the second is singular.

In this case, $H(A) = 1$

On the other hand, if we are given the value $R \cdot A$, this matrix is nonsingular if $A$ is the first value, and singular if $A$ is the second value.  Hence, the value of $R \cdot A$ allows us to derive the value of $A$ with probability 1, and hence $H(A | R \cdot A) = 0$

If $A$ is constrained to be an invertible matrix, and $R$ can take on all invertible matrices with equal probability, then $H(A | R \cdot A) = H(A)$; this can be deduced from the fact that matrix multiplication is a group operation over invertible matrices.


How to prove a symmetric encryption scheme provides perfect secrecy?

Xor-ing the first half of the encrypted message with the second gives the same result as xor-ing the first and second half of the original message. (When the key is duplicated). This contradicts perfect secrecy as some information can be obtained from the cyphertext.


Unleakable shared secret under realistic assumptions?

I think that the use cases for this requirement still need some clarification as they seem to be illogical and self contradictory.  So I'll answer the question posed in your last paragraph.  No. There is no entropy source that can satisfy the buffering requirement.

Firstly, it would be impossible to develop and randomness test an entropy source without recording it's output.  If you record the output, the attacker can record the output.  They will certainly be able to record a few of your minutes of attack time.  There is no way to prove randomness without storing the entropy stream and making multiple passes over it.  In other words, there are no pure streaming tests.  They all require some block of stored data for multiple passes, even something simple like FIPS 140-2 uses blocks of 20,000 bits.  No single pass over data can prove randomness, it takes a combination and then careful assessment of combined probabilities.  If you tested it, you made multiple passes, ero you recorded it.

Secondly.  It is impossible to record the same data stream from any practical entropy source (other than dice).  This feature works to the advantage of TRNG builders, but fatally against you.  In engineering terms, entropy sources don't produce any entropy at all.  The measuring system does, and totally determines it's quality and quantity.  Switch on the old analogue TV you kept.  You'll see static.  1% of that static is your true atmospheric noise in the form of the cosmic background radiation. 99% is other stuff populating the aether, some permanent, some transient.  Some of it will be localised from your hairdryer.  Ever heard a TV studio guest's mobile phone checking in with the local cell tower?  If you record a -100dB signal, there will be a huge proportion of unpredictable external noise.  There is a good example else where on this forum that mentions the ANU Quantum Random Numbers Server.  The developers specifically mention the difficulty of separating the true entropy signal from incidental system noise.

Thirdly.  Randomness extraction will blow it all out of the window.  All extractors use some form of hashing.  If you take the simple example of a 1024 * 768 bit matrix extractor, it requires 1024 bits of entropy to generate 768 truly random bits.  If one bit is different between your two devices (0.1% which is a virtual measurement impossibility), the 768 bit random outputs will be totally different by virtual of the avalanche effect.  Unless something funny is going on, no two TRNGs can ever produce anything like the same output.  They're always absolutely different.


data migration: bcrypt to bcrypt different salts

What do you mean by "differing only in their salting"? A correct implementation of bcrypt should generate a unique salt for each hashed password. The salt is stored along with the hash itself, so yes, the migration is as simple as just using the old values in the new system.


How is "post-quantum security" proven/shown?

This is in principle similar as how "normal" cryptosystems are proven. With some algorithms we can reduce them to some "hard problem", but we do not know that those problems are actually hard to solve. Only that we cannot solve them efficiently. For example, the Diffie-Hellman problem is not even known to be NP-hard, never mind the whole issue of P vs. NP.

Similarly, we know some problems that Shor's algorithm accelerates. Post-quantum algorithms avoid these and make use of problems to which Shor's algorithm does not offer an easy solution. However, that does not mean there is no other algorithm that solves them, or even that there is no way to use Shor's for them. (E.g. it is possible that the hidden subgroup problem in non-abelian groups can somehow be reduced to the HSP in abelian groups.)

In the end it is similar as with symmetric algorithms. They are not so much proved secure, but become proven after facing years of cryptanalysis.


It is reasonably safe to leave an AES encrypted RSA private key public?

Based on skimming the relevant RFCs, I can't find any outright problems. Key derivation from the password is performed via PBKDF2, and best I can tell, the choice of cipher is left up to the implementation. As long as a good cipher is chosen, a truly random 30-character passphrase consisting of uppercase letters, lowercase letters, and digits should have roughly 178 bits of entropy. This is significantly higher than that of a 128-bit key, which is considered to be secure.

It still gives me a bad feeling that I can't shake. But as long as keys are only ever decrypted on trusted devices, I can't personally find a reason why it would be unsafe.

Not that this should be considered an endorsement by any stretch of the imagination.


Why do public keys need to be validated?

Before we get to the questions, we need to understand what these attacks look like.

An Elliptic Curve point is a pair of values $(x, y)$ that satisfies the equation $y^2 = x^3 + ax + b \bmod p$, and point addition is an operation that takes two such points $(x_1, y_1)$ and $(x_2, y_2)$, and computes a third point $(x_3, y_3)$.  (The equations I'm writing assume a curve over $GF(p)$; this attack works for binary curves, but the equations are somewhat different; the above definitions also ignore the Point at Infinity; that's mostly unimportant for what we're doing).

If we consider operating on a point that is provided by someone else, one thing that we need to ask is "what happens if he gives us a point that's not actually on the curve"; that is, is not actually a solution for $y^2 = x^3 + ax + b \bmod p$?  Well, that rather depends on what is the exact algorithm we use to do point addition; in the standard algorithms (and where we're dealing solely with points derived from the attacker-provided pseudopoint, which is the case in ECDH), we end up with "points" which are solutions to $y^2 = x^3 + ax + c \mod p$, where $c$ is the value that original attacker-provided point was a solution to.  That is, we're effectively doing the ECDH operation on a curve that the attacker chose.

Why is this a problem?  Well, different elliptic curves have different numbers of points (that is, solutions to the underlying equation).  The original curve may have been chosen to be a large prime; the attacker can select a curve which has an order with a small factor.  For example, he may give us a curve whose order has $r$ as a factor, and give us a point $Y$ of order $r$ (that is, $xY$ can take on exactly $r$ distinct values).  If he give us that point $Y$ as his ECDH public value, we compute $eY$ (where $e$ is our private value), and use that as the 'shared secret'); then, the attacker can determine the value $e \bmod r$ by checking what shared secret value we got; the details depend on the protocol that uses the shared secret.  This effectively gives the attacker $log_2 r$ bits of our private exponent; doing this a handful of times for different values of $r$ allows him to recover our entire private exponent.

So, to answer your questions:

Why can these attacks accumulate information over multiple queries? Shouldn't they leak the same information each time?

The attacker can choose a different curve (and a different value of $r$) each time; each different $r$ gives him more information about the private value

Which validations need to be performed? Just check if the order of the point is large enough?

The obvious validation that needs to be performed is to plug his values $(x, y)$ into the elliptic curve equation $y^2 = x^3 + ax + b \bmod p$; that's cheap and totally foils this attack.  The other things that you ought to make sure (to avoid other attacks) is to make sure that his point isn't the point-at-infinity, and if the curve order is composite (which it typically isn't; check your curve to be sure), then whether his point is in the subgroup generated by the ECDH generator $G$ (this last bit can be done by verifying if $qY = 0$, where $q$ is the order of $G$, $Y$ is the point provided by the other side, and $0$ is the point-at-infinity).

Why do some curves require this validation, and others don't? Which properties make a curve immune to these attacks?

This attack really isn't against the curve, but against the implementation (and what it does when given an invalid value).  As far as I know, all curves can have implementations which are vulnerable.


How to determine if a hash is pre image resistant or collision free

Name and exact definition of security properties of hashes vary, depending on level of formalism. Refer to your reference material. However the general idea always is:

preimage resistant (or first preimage resistant): given $h$, it's infeasible to come up with $m$ having hash $h$.
second preimage resistant (or weakly collision free): given $m$, it's infeasible to come up with $m'\ne m$ such that $m$ and $m'$ have the same hash.
collision resistant (or strongly collision free): it's infeasible to come up with $m$ and $m'\ne m$ such that $m$ and $m'$ have the same hash.
indistinguishable from a random member of a Pseudo Random Function family (or indistinguishable from a PRF; or secure in the Random Oracle Model) meaning that lacking some fragment of the definition of the hash, it's infeasible to distinguish it from a random function with the same domains.

Some of these properties are stronger than others. Finding implications involving (3) and those involving (4) is easy, and highly recommended to help grasp these properties. With appropriately large input domain of the hash, (2) implies (1), see this.

On relation between security properties of different hashes: the general idea is to assume an algorithm that can break one security property of one of the hashes, and use it (as a subprogram) to build a new algorithm that breaks one property (often, the same) for another hash. This proves that the second hash is no stronger than the first (or equivalently that if the first hash is secure, then the second is) w.r.t. the security property/properties considered.

For example, take preimage resistance for $H'$. Assume an algorithm $\mathcal A'$ breaking that. It is one which, given $h\in\{1,\dots, 2^{256}\}$ as input, outputs¹,² $m\in\{0,1\}^*$ with $H'(m)=h$; that is an algorithm¹ such that² $H'(\mathcal A'(h))=h$.

By definition of $H'$, for the $m=\mathcal A'(h)$ that this algorithm produces, it also holds $H(m\mathbin\|m)=h$.

Therefore we can devises an algorithm $\mathcal A$ breaking preimage resistance for $H$, as follows:

accept input $h\in\{1,\dots, 2^{256}\}$
compute $m=\mathcal A'(h)$ by invoking the hypothesized algorithm breaking preimage resistance of $H'$
compute and output $m\mathbin\|m$

We see that² $H(\mathcal A(h))=h$ (and the runtime of $\mathcal A$ is only slightly/linearly higher than that of $\mathcal A'$).

We conclude that if $H$ has preimage resistance, then $H'$ also has.

It is possible to make similar demonstrations for other security properties and other pairs of functions in the question.

Hint: In the problem at hand, the function $h\mapsto\alpha^h\bmod p$ is used in the construction of $H''$. Given the stated properties of $p$ and $\alpha$, this function has one demonstrable property and one conjectured property, which can be put to use to derive security properties of $H$ or $H''$, or relations between these properties.

¹ With running time polynomial w.r.t. the width of the output of the hash, but that formalism is not in the question, and can be omitted to some degree.

² With non-negligible probability, though that's sometime left implicit.


Is it possible to deduce the value of a string when given its hash and multiples hashes of the string + other known strings?

Assuming the hash is strong, you will not be able to find a preimage any more easily when you know multiple hashes (whether they use the same function or another). In fact, with some hashes you will be able to derive $H(S||K)$ from just $H(S)$ and $K$ (known as the length extension attack), so it can't give you more information.

Unless the hash is broken, the only way to find $S$ in either case is to guess, hash and compare.

However, if your hash was short enough to have collisions, you could need multiple hash values to verify a guess. As an extreme example, consider the first byte truncation of a strong hash. Any guess you make will match it one 256th the time. In that case, knowing more hashes would allow you to verify your guess with higher confidence.


How long would it take on average to perform a timing attack on HMAC over brute forcing a 32bit tag if the hash is good?

Yes, if you have a 100% certainty that you can measure each timing then this is the way to go about it, approximately.

You'd have 128 tries on average per byte, so you'd need 128 * 4 = 512 tries, or $2^9$ bits of security to break, that's next to nothing. This is of course an average, the attacker may be lucky or unlucky, the maximum amount of tries would indeed be 256 * 4 = 1024 tries (or 1020 really, as you don't need to test the last byte value due to the power of deduction) and 1 in case of extreme luck.

There are however a few things wrong in your question:

timing attacks often require a large number of retries to find just one correct value - timing attacks usually rely on statistic, instead of an oracle that immediately tells you if you're correct or not.
you don't need to bother with the exponentiation of 2; there are just a maximum number of tries per byte: 256 (or 255), so the probability of guessing the first byte is just $1/256$, next guesses however will have a higher probability (as the number of untested values goes down).


You need to understand that any variation on the OTP would ultimately be equivalent to the OTP security-wise, since it is unconditionally "secure" (the ciphertext leaks zero information about the plaintext or the key), and so you'd just making it harder to compute for now reason. So, sure, you can use the OTP, or some variant thereof, on 128-bit messages with a 128-bit key, but once you use up that key it's gone. With AES you can encrypt way more data with a single key.

So, looking at your question, you could, conceivably, design a cipher that takes in a 128-bit key and a 128-bit plaintext block, and encrypts it so that the 128-bit ciphertext provides exactly zero information on the plaintext or key (making it unconditionally "secure"). AES probably does not quite satisfy this condition, but the OTP does, and you can certainly design (redundant; see above) variants that could achieve the same thing. But the point is that you can only encrypt a single 128-bit block of plaintext with that 128-bit key. Encrypt any more than that, and the multiple ciphertext blocks must together leak sufficient information on the plaintexts for a (computationally unbounded) attacker to retrieve the corresponding key, no matter what cipher you use.

Basically, there is nothing to improve on; what you are asking for is impossible, and you cannot "work around" the OTP's key reuse problem by chopping the plaintext up into 128-bit (or any size) blocks.


I'm guessing:
"HVZK" stands for "honest-verifier zero knowledge", right? Your objection is that a dishonest verifier can choose a random $x_i$, compute $\rho_i\equiv x_i^2\mod N$, and then when they get $\sigma_i$ from the prover, there is a $1/4$ chance that $gcd(\sigma_i-x_i,N)$ is a non-trivial factor. But an honest verifier should generate random $\rho_i$.
This should be secure, based on the following: Suppose $A$ is an algorithm that can factor $N$ given random $\rho_i$ and $\sigma_i$ such that $\sigma_i^2\equiv \rho_i\mod N$. Then we can factor any $N$ with $A$ by picking a random $\sigma_i$, computing $\rho_i\equiv\sigma_i^2\mod N$, and sending $\rho_i$ and $\sigma_i$ to $A$.
It seems intuitively true that the Fiat-Shamir tansform should be able to turn HVZKs into NIZKs (probably with some extra conditions). An HVZK could fail because a dishonest verifier can send a "dangerous" challenge which reveals information, but a Fiat-Shamir forces the challenges to be random. As long as such dangerous challenges are sufficiently rare, then the Fiat-Shamir transform should produce a NIZK.


Generating shared secret random permutation

Your approach makes getting information other than count of cards in

possession of each player at least as hard as breaking the PRFness of HMAC.

To make it information-theoretically impossible "for all the ... each player",

$\;\;$ if different card_values have different lengths then use

$\;\;$ SHA256(commonly_agreed_public_salt:card_value)

$\;\;$ instead of card_value for what follows

$\;\;$ at the beginning, each player chooses a strong extractor whose output length is  equal to the length of

$\;\;$ each card_value, chooses a random seed for that extractor, and sends both of those to everyone

$\;\;$ (those choices can be reused)

$\;\;$ players compute SHA256(commonly_agreed_public_salt:secret_random_value)

$\;\;$ and Extract(secret_random_value,seed) xor card_value

$\;\;$ with independently chosen secret_random_value for each card,

$\;\;$ and then announce to each other the list of the pairs they possess

.
For retrieval of additional cards from the deck, you need to use
multi-party computation; specifically mental poker protocols.

(as already mentioned by bmm6o)


Can XEX or XTS modes be used with only one tweak?

No, using XEX mode with $j = 0$ is not entirely safe.  As noted in section 6 of the Rogaway (2004) paper (emphasis mine):

  "Some added care is needed to address the security of XEX. Suppose, to be concrete, that we are looking at $\mathsf{XEX}[E,2^{\mathbf I}]$ and $\mathbf I=[0\mathop{..}2^{n-2}]$. Let the adversary ask a deciphering query with ciphertext $C=0^n$ and tweak $(0^n,0)$. If the adversary has a construction-based deciphering oracle then it will get a response of $M=\tilde D_K^{0^n}\,^0(0^n)=D_K(Δ)⊕Δ=D_K(\mathsf N)⊕\mathsf N=0^n⊕\mathsf N=\mathsf N$, where $\mathsf N = E_K(0^n) = Δ$. This allows the adversary to defeat the CCA-security. For example, enciphering $2M=2\mathsf N$ with a tweak of $(0^n,1)$ and enciphering $4M=4\mathsf N$ with a tweak of $(0^n,2)$ will give
  identical results (if the adversary has the construction-based enciphering oracle). Corresponding to this attack we exclude any tweak $(N,i_1,\dotsc,i_k)$ for which $(i_1,\dotsc,i_k)$ is a representative of $1$—that is, any tweak $(N,i_1,\dotsc,i_k)$ for which $α_1^{i_1} \dotsb α_k^{i_k} = 1$. In particular, this condition excludes any tweak $(N,0,\dotsc,0)$."

However, using $j = 1$ is safe, and, indeed, is explicitly used as an example of a valid tweak by Rogaway e.g. in section 3:

  "Tweaks that are not the increment of a prior tweak will also
  arise, and they will typically look like $(N,1,0\dotsc,0)$. Constructions should be reasonably efficient in dealing with such tweaks."

Also, in their comments on the XTS mode, Liskov and Minematsu confirm that, indeed, $j=0$ is a bad choice for XEX (emphasis original):

  "Note that $j = 0$ must be excluded, as $f(0, v) = v$ for any $v$, which implies $ρ = 1$. Moreover, if $j = 0$ was allowed, a simple attack based on this fact existed, as pointed out by [6] and [3]. Hence if XEX is used, one must be careful to avoid $j$ being $0$."

However (while generally criticizing the choice to use two keys for XTS), they also note that this requirement to avoid $j = 0$ only applies to the single-key XEX mode, and not to XTS, which uses separate keys for the tweak and encryption stages:

  "Note that XTS does not require to avoid $j = 0$, as the offset function of XTS needs not be $(ϵ,γ,ρ)$-uniform, but only be $ϵ$-AXU if it is combined with URP. This difference is significant in security, but has no impact on effectiveness for practical applications."


A SHA-256 hash is, until broken by cryptanalysis, indistinguishable from 256 bits of random noise. The only way to defeat this is by enumerating inputs until you find a matching hash.

If there isn't much entropy in the input (e.g., it's an English word, or it's a value that repeats), it will be relatively simple for an attacker to distinguish it from random noise and possibly even determine the data that was originally hashed.


Does impersonating an SRP server give you enough information for an off-line dictionary attack?

Suppose the server did not include $v$ in the computation of $B$. In such case the following events have happened:

The server has sent a salt value $s$ to the client. We might assume it is authentic (because it is easy for the fake server to get it from the real server). The client re-calculates its long term private key $x$ such that $v = g^x$.
The client has generated a fresh random ephemeral key pair $A = g^a$ and sent $A$ to the server.
The server generates a random $u$ and a random $B$ and sends them to the client. The server might, or might not, know the value $b' = log_g(B)$.
The client calculates $S = (B-g^x)^{a+xu}$ and sends a proof of $S$ to the server.

Let's assume the fake server aborts the protocol at this point and attempts to mount an offline dictionary attack on the client password, in order to find the $x$ value.

Now, the problem is that the server is supposed to calculate $S = (Av^u)^b$, but that would require, for each guess at $x$, finding a value $b$ such that $g^b = B - g^x$. The "SRP assumption", if there is one, is that this is as hard the discrete log problem.

Conversely, should the fake server instead try to simulate the client calculation of $S$, it would require also guessing the ephemeral client private key $a$.

Is there any way around this? Yes, there is, but it requires that the server sends $B = 0$ and the client doesn't check for this. If $B = 0$, then we might infer that $b = x + (p - 1)/2$ (where $p$ is the prime field modulus). In such case $B = g^x + g^xg^{(p-1)/2} = g^x + g^x(-1)$, provided that $g$ is a generator of $\mathbb Z^*_p$. The offline calculation of the fake server, in such case, collapses to $S = (Ag^{ux})^{x + (p - 1)/2}$. This has only one unknown.

Edit:
It might be noted, with regard to the "SRP assumption", when e.g. $g = 2$ there are couple of special cases when the assumption is false. For instance, for arbitrary values $z$, ${2}^{z+1} = {2}^z + {2}^z$ and ${2}^z = {2}^{z+1} + 2^{z+(p-1)/2} \pmod p$.

As far as I can tell, all this means, is that if the server sends $B = 2v$ or $B = p-v$, it means that the server already knows both $v$ and $x$ and has selected $b = x$ or $b = x + (p-1)/2 + 1$ respectively. Hence, the server commits to $v$, but fails to hide it, or, alternatively, the server actually commits to $x$.


Just how surjective is a cryptographic hash like SHA-1?

In this regard SHA-1 despite it's weaknesses can be viewed as a pseudo random function.
This means we are are throwing $n$ balls into $n$ bins.
An output bin remains empty if all the balls miss it.
Which happens with probability $(1-1/n)^n$ which is $1/e$ and that is the portion of output bins which are empty.
We also can estimate that the most populated bin has approximately $log(n)$ balls.


Build Encryption Method from Decryption (Reverse Modulo)

so my goal is to make an encryption method that swap the characters to the proper places.

If that's the goal, that's what you do.
You were thinking about "how do I generate the $g$ (actually, the $l, d$ values) in the reverse order"; actually, there's no need.  You just compute the successive $l, d$ values generated by the algorithm, storing them in an array, rather than using them to do the exchanges.  Then, once you have generates all $x$ $l, d$ pairs, then perform the swaps in the reverse order (that is, starting with the last $l, d$ pair generated).


Details about ROS attack on blind Schnorr signatures

The attack is practical. The only safe way to use blind Schnorr and Okamoto-Schnorr signatures is to forbid parallel sessions, that may be impossible if performance is critical.
You can see great explanation of attack here https://youtu.be/W-uwVdGeUUs (Authors of paper offer solution against ROS attack - some modification of Schnorr blind signature, but IMHO it's unsafe)
RSA and BLS blind signatures are not affected by ROS attack.


Is there an information theoretic equivalent of a trap door collision free function?

Any fixed function $f\colon A \to B$ of a finite domain $A$ is guaranteed to have collisions if the range $B$ has fewer elements than $A$, so there always exists a random algorithm $C()$ which returns a collision: the algorithm that just returns one of the collisions.  We just don't know how to find $C$ for functions like SHA-256 (although we do for MD5 and SHA-1!).  This is why the notion of ‘collision resistance’ as applied to fixed hash functions like SHA-256 doesn't even have a formal definition, although there are attempts to formalize this elusive issue of human ignorance[1][2].

We might consider a probabilistic, or ‘information-theoretic’, model: a random function $f\colon A \to B$ drawn with uniform distribution from all functions from $A$ to $B$.  Any random algorithm $C(f)$ to find a collision is limited to birthday attacks that make $O(\sqrt{|B|})$ calls to $f$ to attain nonnegligible probability of success.*

Of course, choosing a function uniformly at random takes a lot of bits: in general, you need storage for a table of $|B|^{|A|}$ entries if you want to be able to specify all of them.  We might pick a smaller family of functions $f_k\colon A \to B$ with a short key $k$, and consider separately the adversary's knowledge about the key:

If the adversary never knows the key (and, of course, can't learn anything about it from side channels like time of hash table operations), there are many cheaply computed functions to choose from that have ‘information-theoretically’ guaranteed bounded collision probabilities called universal hash families—that is, for any $x$ and $y$, $\Pr[f_k(x) = f_k(y)] \leq \varepsilon$ for some small $\varepsilon$.  This is a theorem that is easily proven for many cases like GHASH or Poly1305.  See [3] for more related notions and references.
If the adversary doesn't know the key in advance, Rogaway and Shrimpton gave the standard formal definition[4] of the notion of collision resistance of the family $f_k$ in terms of the best cost of a random algorithm $C(k)$ to find a collision in $f_k$ (or, more specifically, the best success probability of a cost-limited algorithm in terms of the cost).  Families that we conjecture to be collision-resistant in this formal sense include HMAC-SHA256 and keyed BLAKE2b.

Obviously, for each $k$, there is a collision as long as $|B| < |A|$, but even if we had a precomputation oracle to find them all for us in advance, there is an extremely high cost to storing a table mapping every value of $k$ to a collision in $f_k$, and we assume the adversary probably can't afford $2^{128}$ bytes of RAM or even ROM to store it all.  Functions like HMAC-SHA256 and BLAKE2b seem to exhibit this notion of collision resistance, but proving any theorems about it seems difficult.  In contrast, functions like Poly1305 are easily proven to have low collision probabilities.

What about trapdoor functions like $m \mapsto x^m \bmod n$ where $n = pq$ for secret factors $n$?  Anyone who can find collisions in this function can factor $n$, so as long as factoring $n$ is hard—and until whoever knows $p$ and $q$ publishes a single collision!—it seems difficult to find collisions.  But as above, the domain and range are finite, and if $n$ is limited to a particular size then the space of these functions is finite too.  So there's no way you can guarantee a finite but cost-unlimited attacker has a limited probability of finding collisions.

I don't know what the authors might have meant by an information-theoretic generalization to this—you'll have to ask them.  Incidentally, the paper seems to be discussing claw-free function pairs $f_0$ and $f_1$ for which it is difficult to find $x_0$ and $x_1$ with $f_0(x_0) = f_1(x_1)$, not collision-resistant functions $f$ for which it is difficult to find $x_0 \ne x_1$ with $f(x_0) = f(x_1)$.

* You could naively make a table of results so far and check it for collisions each time you call $f$, but that costs $O(\sqrt{|B|})$ time and $O(\sqrt{|B|})$ space for a total area*time cost (which is a proxy for rubles or ergs) of $O(|B|)$.  In contrast, it takes about the same number of calls to $f$, and only constant memory, to use van Oorschot and Wiener's collision search algorithm[5], which can also be parallelized to speed it up with higher power consumption.  It doesn't even seem to help to have a quantum computer that can evaluate superpositions of $f$[6].


Any scenario for using ElGamal-SIGNATURE over RSA?

ElGamal signature works as follows.  Define a large prime $p = 2qs + 1$ where $q$ is a prime.  Let $g$ be an element of order $q$ and a hash function $H\colon \{0,1\}^* \to \mathbb{Z}_q$. The public key is $y = g^x \bmod p$ and the private key is $x \in \mathbb{Z}_q$. The signature of a message $m$ is given by a pair $(r,s)$ where $$r=g^k \bmod p\quad\text{and}\quad s = k^{-1}(H(m) - xr) \bmod q$$
for a random integer $k \in \mathbb{Z}_q$.  The validity of a signature $(r,s)$ on message $m$ is checked by verifying that $r^sy^r \equiv g^{H(m)} \pmod p$.

It is worth to see that the two expensive operations in the signature generation, namely computing $g^k \bmod p$ and $k^{-1} \bmod q$, are independent of the message to be signed.  They can therefore be precomputed.  ElGamal signatures can be preferred when signing should be done very fast, like for example to authenticate a car at a toll bridge.  In this mode (called off-line/on-line),

[off-line phase] several coupons $(r_i, t_i)$, with $r_i = g^{k_i} \bmod p$ and $t_i = k_i^{-1} \bmod q$, for random integers $k_i \in \mathbb{Z}_q$ are pre-computed;
[on-line phase] when a message $m$ has to be signed, the signer takes a fresh coupon $(r_i, t_i)$ and computes the signature as $r = r_i$ and $s = t_i(H(m) - xr_i) \bmod q$.

Notes.

A coupon can only be used once.  Each signature needs a fresh coupon.
In the on-line phase, the cost of an ElGamal signature is only a couple of multiplications modulo $q$ (which is much faster than a full modular exponentiation in the case of RSA).


Does cryptographically-secure pseudo random generators require a secure seed?

Actually, your second sentence itself is the answer. A pseudo random number generator(cryptographically secure or not) is a deterministic algorithm which produce random looking numbers. Every time you provide the same seed it produces the same random looking numbers. Now, if your seed value is predictable and algorithm is public then the output of the deterministic algorithm is also predictable. So, the seed of a cryptographically secure pseudo random number generator must be secret, so that the output you get is unpredictable.


Is there any course video for lattice cryptography?

It's from 2012, so it's not the most up to day. However, the 2nd BIU winter school was on this topic, and all of the slides and videos can be found online. The lecturers were Craig Gentry, Vadim Lyubashevsky, Chris Peikert and Oded Regev. The link is here: https://cyber.biu.ac.il/event/the-2nd-biu-winter-school/.


What is meant by "$r$ may be chosen in a way dependent on $z$"?

An hypothetical algorithm $\mathcal A_2$ breaking the strong RSA assumption has input¹ $(n,z)$ with $n$ generated by the RSA key generation procedure, and outputs² $(r,y)$ such that $y^r\equiv z\pmod n$, with the only other constraint on $r$ that $r>1$. Contrast with an hypothetical algorithm $\mathcal A_1$ breaking the RSA assumption, which has input¹ $(n,r,z)$ with $(n,r)$ generated by the RSA key generation procedure, and outputs² $y$ such that $y^r\equiv z\pmod n$.

The distinction makes the problems different: an hypothetical algorithm $\mathcal A_2$ that builds $r$ as $r\gets n$ is of no obvious use to break RSA, since that choice of $r$ is never used by a standard RSA key generation procedure³. Same if $\mathcal A_2$ was generating $r$ as a function of $z$, e.g. $r\gets2\,\lfloor z/7\rfloor+3$, because that $r$ has vanishingly low probability to match the $r$ generated by an RSA key generation procedure.

In the other direction, we can turn an hypothetical algorithm of the $\mathcal A_1$ kind into one of the $\mathcal A_2$ kind, e.g. by repeatedly trying incremental odd $r\ge3$, submitting $(n,r,z)$ to $\mathcal A_1$ used as a subprogram, and if within some time limit it outputs an $y$, giving $(r,y)$ as output of our $\mathcal A_2$.

The strong RSA assumption (which is that there exists no algorithm² $\mathcal A_2$) is thus a no weaker assumption than the RSA assumption (which is that there exists no algorithm² $\mathcal A_1$). These different notions are soundly named!

¹ Making implicit the security parameter which can be taken as the bit size of $n$, and the random input for randomized algorithms.

² With non-vanishing probability of success within time polynomial w.r.t. the security parameter.

³ It is used by the C.C. Cocks cryptosystem, which predates RSA, and is believed just as secure.


AES GCM encryption, authentication and PBKDF2

Is it safe to generate IV along with KEY from PBKDF2 when using and storing salt for each user or should IV also be randomly generated and stored along with salt? When generating IV from PBKDF2 I'm basically choosing for it to be part of the key, ie a secret. Using a sufficiently large salt per user would guarantee that no two generated KEY/IV pairs exist even if users have same passwords.

Sure thing, but I would recommend to use a KBKDF such as HKDF on the output of PBKDF2 instead of generating a larger output. The reason is that PBKDF2 doesn't handle large output well. That is: output larger than the underlying hash size.

  Should randomly generated master KEY pair be stored with both KEY and IV encrypted or should IV be stored in plain text?

Inconsequential. The IV can be stored in plaintext as well. I'd recommend this as key wrapping is often thought as a specific routine, and it won't include the IV. Furthermore, you probably need more than one IV (see below).

  If you store both encrypted, it is safe to store them in two separate records or should they be encrypted together (concatenated) and stored in a single record? This is regarding IV reuse since two records are now encrypted with same KEY/IV pair.

You need to create a fresh IV for each record that you encrypt. If you have trouble storing the IV then you should consider Format Preserving Encryption (FPE).


RSA - are we able to encrypt into any possible ciphertext in $Z_n$ given a specific key?

Given a public key $(e,n)$, if we are free to choose the plaintext does that mean we are able to generate any possible ciphertext in $Z_n$ ?

Yes

  Because if we were given $e$ we can say that the decryption key is $e^{-1} = k \mod n$

Not quite; the decryption key (which is traditionally named $d$; I'll leave it $k$ using your terminology) is related to the encryption key as $e \cdot k \equiv 1 \pmod{ \text{lcm}(p-1, q-1) }$, where $p, q$ are the prime factors of $n$, or in other words $e^{-1} = k \mod \text{lcm}(p-1, q-1)$.  Other than that detail, you're correct.

  and then choose the ciphertext we wish to generate, say $c$, perform $c^k \bmod n$ and that shows that any ciphertext is "reachable" via encryption given a specific key and some plaintext?

That is correct...


The key is stored physically anyway in the hardware, so access is still possible

The assumption is that it is practically impossible to read the keys that reside (permanently or temporarily) inside the HSM. They will be present in usable form, and used, only inside the HSM, and it is the HSM's job to protect these keys (including enforcing restrictions about what can be done with them).

Preventing access to information stored and processed in the HSM (and deliberate interference with that processing) is accomplished to some useful degree by physical barriers that prevent connecting probes to the insides of the HSM. There are sensors intended to detect if these barriers are pierced or operating conditions otherwise not normal, checks to detect incorrect processing... In such case, the HSM typically attempts to destroy the keys and data being processed, so that there is no longer anything useful that can be extracted.

Additionally, it is often insured that the keys are just not there (thus can not leak) unless there is good assurance that the HSM is operating under rightful conditions (for example, it might be necessary to reunite several partial keys, some in Smart Cards under control of security officers and protected by a PIN code with counter, in order to obtain and use the actual keys inside the HSM).

  If the keys are encrypted, that means that there is another key in the hardware that encrypted those keys

Yes. That's typical.


Regarding Key Strength with DES and Blowfish

I won't say someone would be able to break it 'easily'; however it won't be anywhere as difficult as with a true 128 bit cipher (or even 120 bit cipher; your construction ignores 8 of the key bits).

Here's an outline of how the attack would work: we assume we know the plaintext and the ciphertext, and are trying to recover the key.  When we do is encrypt the plaintext with all $2^{56}$ possible DES keys, and put them in a huge list.  Then, we decrypt the ciphertext will all $2^{64}$ possible Blowfish keys, and put them in another huge list.  Then, we go through the lists, and look for a match; when we find a DES-encrypted ciphertext that matches a Blowfish-decrypted plaintext, that gives us both the DES key and the Blowfish key.

Now, the first obvious objection to this is "if the attacker already knows the plaintext, why does he need the key".  Well, one answer is that this sort of attack can work even if the attacker has a guess of part of the plaintext; if he can just encrypt that region, that is enough to make the attack work.

The second objection is "there's no way anyone has enough memory for lists that big".  While this is true, this attack can be modified to use less memory (at the expense of more computation); in general, if you have $O(2^m)$ memory, this attack can be done in $O(2^{120-m})$ time (for $m \le 56$); this means that if the attacker has a few Terabytes ($2^{40}$ bytes) sitting around, he could do this in $O(2^{80})$ time; that's a bit too close to practical for me


When it comes to linear cryptanalysis, is there always a key that could work for every possible input/output?

Regarding your first question, we assume (for known plaintext attacks such as Linear cryptanalysis) that we can obtain a large number of inputs and the corresponding outputs under the unknown key. The goal of designing a good linear attack is to find a biased linear approximation to the cipher to minimize how many input/output pairs we need. But we shouldn't need all input/output pairs, since that would turn into a brute force codebook(dictionary) attack. Matsui's Linear cryptanalysis attack on DES needs only $\approx 2^{42}$ of the $2^{64}$ possible input output pairs.

Addressing your second question "..when it comes to block ciphers that could be cracked using linear cryptanalysis, is there always a key that could work for every possible input/output?":

Any block cipher defines a unique invertible mapping between the input and output spaces, say both are $\{0,1\}^n,$ given any fixed key, so the answer is yes, absolutely.


adaptation of NIST sp800-22 for short sequences

You will simply not be testing those properties and thus structured nonrandom sequences may pass with respect to tested properties.

For a simplistic example random excursion test fails if the maximum magnitude of the cumulative sums defined by the -1,+1 version of the sequence is too large (much larger than say  $2 \sqrt{n}$ where $n$ is the sequence length.

So you can have long runs and fail random excursions but still pass other tests, e.g., the frequency test.

The paper https://arxiv.org/pdf/1208.5740.pdf has some intuitive discussion of what some of the tests are aimed at.


What kind of ciphers does not depend on order of operation?

What kind of cipher does not depend on order of operation?

Any form of PRP (block cipher) or PRG (stream cipher).

  I suppose ciphers in counters mode where Enc() and Dec() are identical operations provide such property.

CTR mode transforms a block cipher (PRP) into a stream cipher (PRG).

  What about AES_CBC ? ChaCha20 ? Camellia ?

CBC would pass your test but it'll xor the plaintext (instead of ciphertext) into the next block's ciphertext (instead of plaintext). This might weaken it. I'm not sure. You'll have to check the proofs if you want to invert CBC. PCBC would be probably safe (or safer than inverted CBC?) as it xors the plaintext and ciphertext into the ciphertext (normally plaintext) of the next block.

Chacha20 is a PRG where $\text{Enc} = \text{Dec}$, so it'll pass the test.

Camellia is a block cipher, just like AES.

Better questions:

Which modes support this without weakening it?

This is safe at least with CTR, OFB and wide-PRPs. Or even ECB, but you shouldn't use that anyway!

You can test all modes and try to prove or disprove their inverse-safety. But it is generally safer to use the right function for the named task.

Why do you need to invert these functions?

I see at least one use for this: to hide the encrypt vs decryption direction in onion routing networks like HORNET or Tor. In this case the relays would use the cheaper function (if one is cheaper). This use case relies on the stronger semantics provided by a wide-PRP. For more information on this see Onion-AE.


Security of a cryptosystem where the encryption is swapped with decryption

If we have a plain text attack which takes n pairs of known plain text known cipher text and with expected computational effort T extracts the key K then for the inverted cipher the same attack would work with the same properties would work by swapping the order of the pairs.

More formally if we have an atack function a(c,p)= k where c is a cipher text and p is a plain text, we can trivially construct a'(x,y)=a(y,x) which will work on the swapped cipher. You can extend this to family if known plain text attacks, multiple pairs required, computaitional cost, probability of succsss, weak keys etc. As long as the input is pairs of cipher text and plain text you can swap the pair order and get the same attack propeties on the swapped cipher.


I've thourgh that 439 would represent the key size in bits.

No, NTRU doesn't measure things like that.  Instead, it's the number of elements in a ring.  In addition, with the current parameter sets, each ring element is a value between 0 and 2047 (11 bits), and the public key consists of one ring, and so it takes up $11 \times 439 = 4829$ bits, which compresses to 604 bytes.


Safety of having many passwords hashed with the same salt?

To answer your explicit questions:

Hashing many passwords with the same salt is definitely a security issue. The whole point of a salt is to never hash different passwords¹ with the same salt.
When passwords are involved, there is no way that a SHA algorithm can be more suitable than a password hashing algorithm such as Bcrypt or Argon2. Despite the similarity of names, hashing algorithms and password hashing algorithms have very different properties. Recommended background reading: How to securely hash passwords?

Now, on to your system design. It's difficult to tell exactly what you're doing, but there's probably something you need to change in your design. It may not need to be a drastic change, probably just making some changes to how you use the password and what information gets transmitted between the client and the server.

The salt needs to be unique, but it doesn't need to be secret. If the server needs to make a calculation involving the salt, either the salt should be stored in the server's database or the client should send the salt to the server.

  The user's raw password is used for cryptography purposes

A password can't² be directly used for any cryptography purposes, for the same reason a cryptography hash can't be used for passwords. To turn a password into something that can be used for cryptography, such as a key, you need to apply a key stretching algorithm to the password.

Key stretching and password hashing are very similar. In fact, you can take a password hashing function with a suitably long output, split that output in two, and use one half as a key and the other half as a password hash. Knowing one of the halves of the output, you can't find the other half (unless you manage to guess the original password). You need to be very careful not to mix those two halves!

¹  By “different passwords”, I mean passwords for different accounts, or successive passwords for the same account. I'm not referring to whether the passwords happen to be identical character string.
²  “Can't” meaning “your program may work but it will be grossly insecure”.


Reveal all information up to n-th message

Is there a way to generate a sequence of keys that have the property that exposing any of those keys will reveal all previous keys, but no future key?

One possibility: select a hard to factor value $n = pq$; publish the value $n$ (or include it with each day's "key"), and keep the factorization secret.  It'll make things easier if you select $p \equiv q \equiv 3 \pmod 4$

Then, select a random quadratic residue $r_0$ (which you can do by selecting a random value $t$ and computing $r_0 = t^2 \bmod n$)

Then, for each day's secret $r_i$, you can compute the next day's secret $r_{i+1} = \sqrt{r_i} \bmod n$ (that is, a modular square root); there are four such square roots; you'll want the one which is a quadratic residue.

That's actually easier than it sounds; if you took my advice about about $p \equiv q \equiv 3 \pmod 4$, then all you need to do is compute:

$$r_{i+1} \mod p = r_i^{(p+1)/4} \mod p$$

$$r_{i+1} \mod q = r_i^{(q+1)/4} \mod q$$

And combine $r_{i+1} \mod p$ and $r_{i+1} \mod q$ using CRT to reconstruct $r_{i+1}$

This addresses your problem, as:

Computing next keys is as difficult as factoring $n$
Computing previous keys is easy, as $r_{i-1} = r_i^2 \bmod n$
You can compute next keys as long as you want


What is the reason to separate domains in the internal hash algorithm of a merkle tree hash?

The document you refer to describes a method for hashing lists of data entries. Assume you do not prepend $0$ or $1$. Then, the hash for the list $(e_1, e_2)$ is $H(h_1 \| h_2)$ for $h_1 = H(e_1)$ and $h_2 = H(e_2)$. It is now easy to find a second preimage of that, namely the "list" with the single entry $h_1 \| h_2$, which will be hashed to $H(h_1 \| h_2)$.

This attack does not work if you pretend $0$s and $1$s as suggested: The hash of the list $(e_1, e_2)$ is then $H(1 \| h_0 \| h_1)$ for $h_0 = H(0 \| e_0)$ and $h_1 = H(0 \| e_1)$. You now cannot easily find a preimage of that: The single entry list $h_1 \| h_2$ gets hashed to $H(0 \| h_0 \| h_1)$, and $1 \| h_0 \| h_1$ gets hashed to $H(0 \| 1 \| h_0 \| h_1)$.


This is a complex topic. Hence my suggestion:

There is a reasonable tutorial here. Forget the example table above and whatever you are reading and read the tutorial first. The example above is full of vague words and undefined terms. There is a lot going on in the TMTO and things have to be fully defined.

Even Hellman's paper while  very technical is more enlightening than what you have given above, but the tutorial is more gentle.

In the case keylength is not equal to blocklength, a projection map is used from 64 bits (say) to 56 bits (say) by taking the first 56 bits of the output, since the only goal of the update function along the trails is to give you a pseudorandom walk among possible key values.

Table vs list, these are valid programming and data management distinctions and the author was sloppy. While they have impact on the exact complexity, they have small impact on the overall big-oh complexity of the attack.


Protocol to identify zone of potential agreement without revealing reservation prices and having to trust third parties?

Is there a protocol that A and B can use to find out the same thing
  without having to trust the other and any third parties?

There is. Even more than one.
Your problem actually is equivalent to Yao's Millionaire's Problem.
You have two numbers which two parties want to keep secret and you want both parties to find out whether the one is larger than the other, i.e. compare $a\geq b$ with $a$ being the maximal price willing to be paid by A and $b$ being the least price for which B would sell.

The secure multiparty protocols (credit goes to Ricky for pointing that out) to solve this are various. Because they aren't easy and it's better if you get them from source I'll quickly name three (better protocol suggestions are welcomed):

"Protocols for secure computation" by Yao
"Some Efficient Solutions to Yao’s Millionaire Problem" by Kumar and Gupta
"An Efficient Protocol for Yao's Millionaire's Problem by Ioannidis and Grama


Yes, it is good enough. In the case of random primes the distance as large as the numbers with high probability.

With the recommended key-size ($2048$-bit) one only needs to generate two random primes of the right size ($1024$-bits each). This is generally done throwing a random number of $1024$ bits, forcing the first one and the last one bits equals to 1 (the Most significant bit is equal to 1 to guarantee the right size and the Less significant bit is equal to one to get an odd number) and check the primality of this integer. Sometimes the second most significant bit is set to 1, too. As  fgrieu explained in his comment mandating that the second highest-order bit of $p$ and $q$ is set insure that $N=pq$ has exactly as many bits as the sum of the numbers of bits in $p$ and in $q$, because $(\frac{3}{4})^2>\frac 1 2$. That's not quite the way ANSI X9.31 and derivatives (including FIPS 186-4) RSA key generation methods do this; they tend to prescribe $2^{(n−1)/2}<p<2^{n/2}; 2^{(n−1)/2}<q<2^{n/2}$; and (w.r.t. Fermat/Lehman factorization) $|p–q|>2^{n/2–100}$ where $n$ is the number of bits in $N=pq$, with $n$ multiple of $2^6$ or some higher power of two.


Is PBKDF2 with 1 iteration acceptable for a simple random key expansion?

Or would it be better to use something like HKDF?

Generally? Yes. Using HKDF is preferred, if only to communicate clearer what you're actually doing here.

Is it acceptable to use PBKDF2 with just 1 iteration to do the simple key expansion that I need?

Yes.
To explain this, we first need to understand how PBKDF2 works. First, note that it compute $\ell$ from the input as the number of PRF (HMAC) invocations needed to get the desired key length. The key is then $T_1\|T_2\|\ldots\|T_\ell$. The $T_i$ are defined as $T_i=F(P,S,c,i)$ - with $P$ being the password, $S$ the salt and $c$ the iteration count. If we now look at $F$ we get $F(P,S,c,i)=U_1\oplus U_2\oplus\ldots\oplus U_c$ which simplifies to $U_1$ for our purposes. Finally we look at the definition of $U_1=\operatorname{PRF}(P,S\|\operatorname{INT}(i))$ - with $\operatorname{INT}(i)$ being a fixed-length 32-bit integer encoding.
Putting all of this together we see that PBKDF2 with 1 iteration yields
$$\operatorname{PRF}(P,S\|\operatorname{INT}(1))\|\operatorname{PRF}(P,S\|\operatorname{INT}(2))\|\ldots\|\operatorname{PRF}(P,S\|\operatorname{INT}(\ell))$$
which can be easily proven to be a variable output-length PRF with the same argument that is used to prove Counter-mode secure.
Finally, a variable output-length PRF keyed with a uniformly random key yields an output that is indistinguishable from a random string. The only assumption we need to make here is that HMAC-SHA512 is actually a secure fixed-length PRF but that one shouldn't worry you.


Using AES-CBC and providing the IV in file header -> security hole?

As hunter said in his comment, IVs are not required to be secret. Recall that the purpose of an IV is to make an otherwise deterministic construction instead be non-deterministic; if this were not the case, then these constructions would no longer have indistinguishable encryptions under chosen-plaintext attacks, and that would be a real shame.

Thus, there is no real need to keep the IV secret. If revealing the IV in AES-CBC somehow weakened the scheme, then there would be something very wrong with AES, and as far as anyone in the past 15 years can tell, there isn't much wrong with it. Think about it: what role does the IV have? Well: it is XOR'd with the first block of the plaintext before encryption. There's not much that can go wrong.

Of course, it's not all fun and games. For CBC mode encryption, your IV does need to be unpredictable and never reused. Generally, just picking a good (pseudo)random number does the trick there, but the requirement's there all the same.

Note an exception: if you are using CBC-MAC, your IV needs to be some fixed constant, usually zero, to prevent a bit of trickery on the part of an adversary. This doesn't really apply to your question directly, but I wanted to mention it just in case someone stumbled across this answer and thought it applied to CBC-MAC.


aes128_ecb_encrypt (the AES block cipher in the forward direction) is a pseudorandom permutation family: if the adversary doesn't know the key, then knowing the output corresponding to some inputs doesn't help to find the output corresponding to some other input. In other words, the only way to find AppSKey for a given AppKey is to convince someone who knows AppKey to calculate and publish the value of AppSKey for that exact input (same AppNonce, same NetID and DevNonce).

Therefore the potential problems with the protocol are:

Can users who share an AppKey be convinced to repeat both AppNonce and DevNonce within the same NetID?
Can this use of AppKey result in calling the AES permutation with the same inputs as other uses of AppKey?

1. Nonce repetition

Nonce repetition needs to be done on both sides. AppNonce is a 24-bit value, so if it's chosen at random, it'll likely repeat at least once within a little over $2^{12} \approx 4000$ attempts (birthday paradox). DevNonce is a 16-bit value which is supposed to be random, so it'll likely repeat at least once within a little over $2^8 = 256$ attempts (§6.2.4). But since the two nonces are chosen by different devices, the probability that one nonce repeats is independent from the probability of the other nonce repeating. If AppNonce is genuinely random then to get a good chance of repeating you need about $2^{20} \approx 1,000,000$ attempts. At 11kbit/s, which is the nominal maximum bandwidth, you could go through this in a day, if the device's battery is up to it.

If the nonces are repeated, they'll end up using the same AppSKey. AppSKey is used for unauthenticated encryption with CCM*. Unauthenticated CCM* is CTR with a choice of initial counter value that ensures that counter values won't repeat if the CCM* IV doesn't repeat. So in order to get a block to repeat, you need to arrange not only for the key to repeat, but also the IV. Since the IV is calculated in a simple way from constant device characteristics and the frame count (§4.3.3), each session uses the same IV sequence. So if two sessions use the same AppSKey, then the corresponding messages in these sessions will be encrypted with the same mask. This reveals the xor of each pair of corresponding messages.

Uses of AppKey

In addition to the derivation of AppSKey, AppKey is also used to calculate integrity values (MIC) for join messages (§6.2.4) and join-accept messages (§6.2.5), to derive NwkSKey (§6.2.5), and to encrypt join-accept messages (§6.2.5).

NwkSKey is derived in the same way as AppSKey except with the prefix 0x01 instead of 0x02.
MIC are CMAC calculations. CMAC uses AES in the encryption direction, with inputs that are the result of xor-ing successive input blocks with an intermediate result that's an AES output. The intermediate result is not published.
The join-accept message is calculated by decrypting a block of data.

I don't see an obvious way to get the inputs to collide, but this would require extensive analysis.


AES 128-bit encryption - not getting expected results

However, when I tried using an online AES encyption tool encrypting a 16-byte message produced 32-byte output. How is that possible? What am I not understanding correctly?

The tool in question seems poorly documented for implementation validation. It appears that it performs padding to deal with arbitrary length inputs. This padding is necessary if you want to encrypt arbitrary length messages in a reversible way, however, this implies that you need to add at least one message to the plaintext before encrypting it. This expansion yields the observation: A 16-byte message needs padding to ensure padding is there to be removed. However in a 16-byte block, there's no space for extra padding, so a second block is produced and appended only containing padding.
If you insist on using this tool, it should be possible to do so but just taking the first 16 bytes of the output as the plain input.
Alternatively, you can use tools that don't perform unspecified padding or use the test vectors specified in FIPS-197 (PDF).


Why Bellare-Micali Oblivious Transfer Construction requires ElGamal with hashed key?

The hash needs to be used in order to be able to simulate. In particular, consider the case that the receiver is corrupted. The simulator can't know the choice of $b$ so doesn't know if the receiver can decrypt the first or the second message. Therefore, in order to simulate, the simulator has no choice but to just choose random values to represent $H(y_0^{r_0})$ and $H(y_1^{r_1})$; denote these random values by $\rho_0$ and $\rho_1$. Then, the simulator can see which of the two queries $y_0^{r_0}$ or $y_1^{r_1}$ the receiver makes to the random oracle. (One can show via the CDH assumption that the receiver cannot make both queries.) Now, once the simulator receives the query $y_b^{r_b}$ to the random oracle, it can send $b$ to the trusted party and get back $m_b$. Then, it sets the response of the random oracle to be $\rho_b \oplus m_b$ (i.e., $H(y_b^{r_b})=\rho_b \oplus m_b$). You should be able to verify that this indeed gives the right distribution.
Next, in order to simulate the corrupted sender, the simulator has to be able to extract the values $m_0,m_1$. Since it doesn't know $r_0,r_1$ (since no ZKPOK are used), this is problematic without the hash. However, .... I'm actually stuck at this point; I'm not sure how you would do this without adding a proof of knowledge of the discrete log of $c$ in the beginning (maybe my brain is fried right now). Then once you have this ZKPOK, you wouldn't need the hash for this part of the proof anyway. Note that you only need to do the ZKPOK once for many OTs using the same $c$.
Note that the lectures refer to the semi-honest setting. In this case, I don't believe that the hash is actually necessary, and it suffices for $m_0,m_1$ to be in the group.


If you find a flaw or bug for example in Linux kernel you can create an issue in GitHub, or if you can solve it you can contribute.
  How about Finding a flaw in cryptographic protocol?!

A protocol is slightly different than a concrete implementation of a piece of software like the linux kernel on GitHub. It is closer to a specification that may be followed by many different implementations.

  How can you report it or flag an issue?
  If you can fix it, is it possible to contribute?

This depends on whether the protocol is something that is deployed and in use, e.g. TLS, or is a protocol that has merely been proposed academically.

If it is a theoretical academic protocol, you would create a paper discussing the attack or relevant shortcomings of the protocol and publish it as appropriate.

If the protocol in question is actually in use in the real world, then you would find who the authors of the protocol are and email them privately. Exactly who you email might vary depending on circumstances: Companies, individual implementors, and standards bodies might all be relevant. Try looking for white papers/RFCs/working groups/etc to locate the appropriate people to contact.

Be sure to include the email:

A thorough description of exactly what the problem is
Who is affected
How serious the problem is
How long the problem has been present
An implementation of the attack (a.k.a proof of concept)
Recommendations for how to fix the problem

Vulnerability reporting and disclosure can have multiple, orthogonal approaches and vendor responses may vary. If it is a widely used protocol like TLS your approach and response may very well be different from some random individuals project on GitHub.

Oh, and apparently it's trendy to create a branding campaign for the vulnerability, including a name, logo, and website. Whether or not this is a good practice is debated.


The original paper (Don Johnson, Alfred Menezes, Scott Vanstone. The Elliptic Curve Digital Signature Algorithm (ECDSA), International Journal of Information Security volume 1, 2001, pp. 36–63) is surprisingly quiet about the rationale for all of these.

  Check that $Q_a$ is not equal to the identity element $O$, and its coordinates are otherwise valid.

If $Q_a=O$, then the step $(x_1,y_1)=u_1\times G+u_2\times Q_a$ turns into $(x_1,y_1)=u_1\times G$ because the identity element multiplied with anything ends up being the identity element – the same as normal math ($0\cdot a=0$).

Let's start with the verification equation and roll it back with the assumption that $Q_a=O$. As a reminder, the signature is $(r, s)$. The signature is valid if and only if $r \equiv x_1 \pmod{n}$.

$(x_1, \_) = u_1\times G+u_2\times Q_a = u_1 \times G + O= u_1 \times G$, where $u_1 = zs^{-1} \mod{n}$.

An attacker trying to forge a signature for a new message has control over:

$z$ is a trimmed hash of the message. The attacker can compute this.
$(r, s)$ are signature parameters and thus provided by the attacker along with the message.

Because $Q_a$ is gone from the picture, the part that effectively binds the private key into the signature, a valid signature becomes trivial:

Compute $z$.
Pick any $s$ at random in the range $0 < s < n$.
Compute $u_1 = zs^{-1} \mod{n}$.
Compute $(r, y_1) = u_1\times G$.

Because the verifier skips verification that $Q_a \ne O$, this checks out.

(Note that this requires a way for the attacker to supply a public key $Q_a$. In many cases, the public key is pre-shared or otherwise hard-coded so this issue rarely arises in practice. Often, there may not even be a way for an attacker to force $Q_a=O$ if there's no accepted bit representation of $O$ depending on the implementation.)

  Check that $Q_a$ lies on the curve.
  Check that $n*Q_a = O$

If $Q_a$ is not on the curve or has an order that does not equal the expected $n$ for the curve, it may lie on another curve $E'$, chosen by the attacker; $E'$ would typically be a curve that has a small order and then use the Chinese remainder theorem to discover information about the private key in Diffie–Hellman settings.

This can be abused in the context of a certificate authority (CA) using ECDSA as a proof of possession of the private key for $Q_a$ when $Q_a$ is not validated (adapted from Adrian Antipa et al. Validation of Elliptic Curve Public Keys, section 4.3), though this is all in the context of ECMQV and thus a special case:

Select two values for $s$ and $u_2$ between $1$ and $n-1$ inclusive.
Compute $z$ and $u_1$ for ECDSA as normal; the message for $z$ may be chosen by the CA.
Compute $T_1=u_1\times G$ on curve $E$.
Compute $T_2=u_2\times Q_a$ on curve $E'$.
Compute $V=T_1+T_2$ using point addition as if both points were on curve $E$; the result will be on neither curve.
Set $r$ to the x-coordinate of $V$.
Compute $u_2'=rs^{-1}\mod{l}$, where $l$ is the order of a point with small, prime order on $E'$ that contains $Q_a$.
Repeat this procedure unless $u_2\equiv u_2'$
Output the signature $(r,s)$.

  Verify that $r$ and $s$ are integers in $[\![1;n-1]\!]$. If not, the signature is invalid.

The original paper by Johnson et al. notes on p. 48 that (a) this mitigates attacks related to ElGamal signatures without such checks, and (b) the check that $r>0$ in particular avoids an issue specifically relating to a base point $G=(0,\sqrt{b})$ (with $b$ from the short Weierstrass curve parameter for $E$: $y^2=x^3+ax+b$), though I am unaware of any elliptic curve standard specifying a base point with an x-coordinate of zero.

This also helps prevent malleability so that given an existing $(r, s)$ and existing message $m$, no new signature for the same $m$ can be made without possession of the private key. The group generated by the generator $G$ is a cyclic group of order $n$, which means that the cycle repeats after $n$ additions of $G$ to itself: $n\times G=O$, $(n+1)\times G=G$, …, therefore for every $(r, s)$, the tuple $(r + cn, r + cn)$ is also a valid signature for the same message for every integer $c>1$. Note that $(r, -s\mod{n})$ is already another valid signature that may need to be guarded against as well.


Finding the cycle set of specific polynomial

This is quite combinatorial in nature and the suggestion in the comment is exactly how one would do small examples. General results are much more complicated for arbitrary polynomials, but simple for primitive polynomials.

If the generating polynomial $f$ of degree $d$ over $F_q$ is primitive (i.e., $f$ is irreducible, and has a root in the splitting field of order $q^d-1,$) then the cycle length is maximal, and equal to $q^d-1$ for any nonzero loading, and is otherwise a single cycle at zero.

If the generating polynomial $f$ is not irreducible but is a product of irreducibles, the cycle structure can get quite messy.

Most generally, form the companion matrix $C_f$ of the polynomial $f$ of degree $d,$ which is a $d\times d$ polynomial over $F_q.$ Then the length of any cycle that can be generated by the given degree $d$ polynomial divides the order of $C_f$ in the general linear group $GL(F_q,d)$ of $d\times d$ invertible matrices where the group operation is matrix multiplication. This means that the length of any cycle will be a divisor of
$$
q^{k(k-1)/2}(q-1)(q^2-1)\cdots (q^d-1)
$$
and this is all we can say in general.


RSA: Construct private / public key for given cipher and plain text message

Note: klugreuter's answer outlined a different approach to the problem, that I developed here. This obsoletes the following, except perhaps when we want a small $e$.

We can compute $\mathbin|m^e-c\mathbin|$ for various small odd $e>1$, and try to factor them (even partially). As soon as we get two distinct primes factors $p$ and $q$ for some $\mathbin|m^e-c\mathbin|$, with $\gcd(p-1,e)=1$ and $\gcd(q-1,e)=1$, $m<p\,q$ (and $c<p\,q$ if that's added to the problem statement), then we can compute $N$ and a $d$ matching $e$ for this $N$ by one of the methods used in RSA, and that solves the problem. That's at least sometime feasible by pulling moderate factors using ECM factoring (e.g. using GMP-ECM).

If $N$ is required to be large (including, because $m$ is; $c$ has lesser influence), it is hard to find $p$ and $q$ with large enough a product. But we can sometime find more than two distinct large primes dividing $m^e-c$, and compute $N$ and $d$ as in multi-prime RSA; that improves our chances to find $(N,e)$ passing scrutiny (but does not answer the problem as worded, since it requires $N$ to be a bi-prime).

Addition: in the question as asked, there's no requirement that $c<N$ (that's normally part of RSA). When $m\ll c$, that allows to try the above with $e=1$, that is factor $c-m$, which is much smaller than above. If we get distinct prime factors $p$ and $q$ with $m<p\,q$ that gives a solution. We can hide that we started from $e=1$ by adding a multiple of $\operatorname{lcm}(p-1,q-1)$ to $e$ and/or $d$.

Late addition/hint: if we are allowed to use $e=\operatorname{lcm}(p-1,q-1)+1$ as hypothesized above, then at least one choice of $e$ not discussed above is worth consideration.


Secret sharing where the combination of shares matters

Yes. It is possible to construct secret sharing schemes for general (monotone) access structures. You can read about the first construction in the paper called Secret Sharing Scheme Realizing General Access Structure. I also suggest reading this survey by Amos Beimel.


There is no such thing as the "Entropy Rate" of a bit string. That's shorthand for the entropy rate of the process that created the bitstring. Thus what's to be analysed to determine this entropy rate is how the bit string was produced, not the bitstring itself.

If a bitstring 0000 was produced by four fair coin throws, the entropy rate of that process is 4 bit/bitstring, and the entropy rate of the process that created each bit of the bitstring is 1 (bit/bit). Knowing the bitstring is of no use in this determination.

If a bitstring 0101 was produced by starting with 0 then alternating, then the entropy rate is zero.
The "NIST Randomness Test Suite" accepts a bitstring as input and determines if the hypothesis that the bits in this bitstring have been created independently and uniformly at random is acceptable, or should be rejected as too improbable.

When the hypothesis is true, the tests most often accept the hypothesis, but occasionally reject it (modern versions output a p-value, that is the probability that the hypothesis is rejected even though it actually holds).
When the hypothesis is false, what the test concludes depends enormously on the actual process.

If the process is a CSPRNG initialized with a constant bitstring, its entropy rate is zero, but the tests conclude just like if the hypothesis was true (and the entropy rate was 1 bit/bit).
If the process is a natural source that behaves distinguishably from the hypothesis (for example, if each bit is determined by 20 fair coin throws and is 1 if there was at least 10 heads; which is a source of independent bits sizably biased towards 1), some tests in the suite are more likely to reject than they would be should the hypothesis hold; how likely depends on the source, and on which test.

To check the "biased-ness" of a bit string, first define "biased-ness" of a bit string; I know no acknowledged definition.

To test if a bitstring could be from a source of random independent bits with no bias, count how many bits it has, and how many are 1; then, armed with these two integers, use a (perhaps, one sided) chi-squared test. This will tell if the hypothesis can be rejected with confidence. The monobit test in the NIST Randomness Test Suite does that, restricted to long bitstrings.


Server receives three messages:

$I=x+z$. This is the value $x$ encrypted with a one-time pad $z$. The server cannot find $x$ without knowing (something about) $z$.
$w$. This is (presumably) independent of anything secret.
$c=(-z)\cdot w+a$. This is the value $(-z)\cdot w$ encrypted with a one-time pad $a$. The server receives no information about $(-z)\cdot w$ and thus $z$ or $x$ without knowing something about $a$.

Therefore, assuming that $z$ and $a$ are generated randomly just for this instantiation and never reused or revealed, and that $w$ is independent of $x, z, a$, the server learns nothing about $x$.


Please help a complete noob with deniable encryption!

If you aren't concerned with integrity guarantees, one easy way of accomplishing this is via AES-CTR encryption. For a given ciphertext, decrypting with any AES key results in a valid plaintext.

That being said, you should be concerned with integrity guarantees. I'm not recommending deploying any crypto which does not meet standard security notions like IND-CCA2.


Path ORAM asymptotics for arbitrary block sizes

The smallest block size that is reasonable to consider is at least $\log N$, since the headers of blocks in server storage need to contain their virtual address and position (according to the position map).
The idea behind path ORAM (and most tree-based ORAMs) is to maintain the position map using a recursive ORAM. The "data units" in the position map are of size $\log N$ (a position in $[N]$), therefore the recursion will not work for a block size $O(\log N)$ since in such case you will not reduce the number of blocks in the recursion.
We now understand that for the scheme to actually work, we need a block size $k\log N$ for non constant $k$. For such a block size, the overhead will be $\log N + (\log^2 N)/k$ (I know this doesn't align with the original paper, but a better parameterization of the recursion with the same construction gives this overhead. See "Circuit ORAM" paper for more details).


Algorithm to find primes $q$ and $p$ with $q\, |\, p - 1$?

The critical facts enabling to find such $p$ in practice are:

We can easily tell with practical certainty if an integer with many thousand bits is prime or not, using a primality test such as Miller-Rabin, even though we are typically unable to tell all its factors when it is not prime.
About $1.4/b$ integers of $b$ bits are prime. Thus it is more likely than not that randomly trying $b$ integers of $b$ bits will uncover a prime (for $b>4$).

Hence a possible method to find a somewhat random large prime $p$ with some large known random prime $q$ dividing $p-1$ is:

first randomly select a suitably large prime $q$
for successive $r$ of suitable size

compute $p\gets q\,r+1$
if $p$ is prime

output $p$ and stop.

There are refinements to this. Obviously, we can restrict to even $r$. That's a special case with $s=2$ of a more general tweak: for any small prime $s$, it must hold that $q\,r+1\bmod s\ne0$, thus $r\bmod s\ne-q^{-1}\bmod s$. This allows to build a sieve of possible $r$, eliminating most candidates without a full primality test.

There are standardized algorithms to generate such $p$ and $q$, including deterministically from a seed. See FIPS 186-4 appendix A.1


What are differences between $E(F_p)$ and $E(Z_p)$?

Just adding the comments of poncho and blackadder here which I think should have just been posted as an answer (answer is community wiki in order not to cowardly get credit for this).

The difference comes if you do ECC in an extension field; where the field size is $p^k$ for k>1. In that case, $Z_{p^k}$ would imply that you're doing your math modulo $p^k$, which would be incorrect (that's not a field). Instead, in that case $E(F_{p^k})$ would be the correct notation. Of course, nowadays we usually stick to prime fields; in that case both notations are equivalent.

Note that as BlackAdder mentioned the correct answer might depend on the author of the paper, if the paper was written by a number theorist then there is a chance that $Z_p$ means the $p$-adic integers, and arithmetic in $Z$ modulo $p^k$ (i.e. the $Z_{p^k}$ in poncho his comment) would be denoted by $Z/{p^k}Z$ in such papers.


Is this a valid "fix" for deterministic encryption in encrypted databases?

I work in the area of data-at-rest encryption, so I feel fairly qualified to answer your questions.

Re. 1: Access control is well and good but it typically isn't modeled in cryptographic proofs of security because it's an extra assumption, and proofs try to use as few assumptions as possible. It's obviously important for the real-world security of a database, but to be safe you have to assume everybody is an attacker, even someone with valid credentials.

re. 2: Your strategy for deflecting frequency analysis is usually called 'homophonic encryption' in the literature. It is indeed useful for making certain statistical attacks much more difficult, but its efficacy is highly dependent on the particulars of the type and number of bogus values injected, and crucially also on the distribution of the plaintext data.

If your database will primarily be doing information retrieval and/or search-type stuff, a much more secure (in theory and practice) primitive is searchable symmetric encryption. It gets you the functionality without needing deterministic encryption.


First off, from your question, it is not clear whether or not you understand the "circuit" part. So I'll start there. With (most) FHE schemes, you are evaluating circuits, or a bunch of gates hooked together. Often, we think of circuits in terms of and/or/not gates. It turns out, however, that you can construct circuits from other types of gates. NAND by itself is functionally complete. So, with just a single NAND gate, you can construct any circuit. That is why we need a scheme that can compute at least one NAND gate (in addition to its own decryption circuit).

As you stated, FHE schemes add noise to the ciphertext. So, you can evaluate a circuit on the input ciphertext(s), but you may add so much noise in the process of doing this that you can no longer decrypt. That is the problem we are faced with. It is important to remember that inputs to the circuits are ciphertexts, and that the output of the circuit is a ciphertext.

What Gentry gave us what a somewhat homomorphic encryption scheme. After evaluating too many gates, the noise becomes too much and we can no longer decrypt. But, he showed that by taking the decryption algorithm for his scheme and converting it into a circuit and passing the circuit a ciphertext and an encrypted version of the private key, what you would get out was a ciphertext of the same plaintext, but with the noise gone. Furthermore, the cipher allowed you to run at least one NAND gate on two ciphertexts (a couple of gates that were equivalent to a NAND) and the decryption circuit without the noise being too much.

So, let's say we can execute one NAND gate and the decryption circuit homomorphically and still be okay noise-wise.  Given a circuit like this (A NAND B) NAND (C NAND (D NAND A)) we would actually execute it as (say DEC is the decryption circuit using an encrypted version of the private key):

DEC(
  DEC(
    A NAND B
  )
  NAND
  DEC(
    C NAND
    DEC(D NAND A)
  )
)

So after every NAND you would insert a DEC to eliminate the noise. I should note that even though the last thing you evaluate is DEC, the value that comes out is encrypted.