Converting a "raw" non-ASN.1 EC private key to a public key?

Without knowing which domain parameters were used this question is impossible to answer. The problem is that the value of the private key is random within the domain.

So although we know that the key size is about 224 bits, there is no way to validate any public key value, because the public key is calculated using the random private key as input in the first place. To be precise, it is the multiplication of the private key with base point $G$ of the curve. This means that we generate a valid public key whichever curve / set of domain parameters we use.

Another issue is the required key size. Normally a public key is identified using a compressed or uncompressed key point. An uncompressed point would add 1 byte for an identifier. However, this in turn is usually put into an ASN.1 BIT STRING, which adds 3 bytes if we assume DER encoding.

So in that case we would for instance get:

033a00046bf056effd0478f8cfe52a07ac42d098f7775314aa84ff4657719c529ce3c117062b42f67b35e2d19276537ea44a14a3b41a072d7fa3c0b7

for P-224 and

033a0004aee24d6692b745b4ecb76d2aff13e51ce177a34f00b5d6c92778d1367dbdb2dd6283fdec3966d33cb800a0e6e5d2060b0daf7e8382e3736e

for brainpoolP224r1, however with no method to distinguish between either two, and there may be more candidates.

Verifying any previously generated signature should of course enable you to select the correct value.


Matyas–Meyer–Oseas for super-fast single-block hash function

Is it basically safe and correct to use the Matyas–Meyer–Oseas construction to turn a fast block cipher like AES into a really fast single block hash function?

Mostly, yes.  It is one standard approach to convert a permutation into a one-way function (at fairly small expense).  It does have some odd properties (e.g. it's easy to find the fixed point, that is, the block that hashes to itself), but those are typically not a concern.

  If you're curious the application would be Winternitz one-time signatures.

That brings up some concerns.  For one, Winternitz one-time signatures consist of a series of $H(x)$ values, and you can forge if you can find any of the $x$ values.  You are using the exact same $H$ function for each iteration; what an attacker can do is compile the list of $H(x)$ values he's looking for, and compute $H(y)$ for various values of $y$; if it happens to match any of his target $H(x)$ values, he wins.  For example, if your signature consists of 34 Winternitz chains of length 255 each (that's 256 bits, plus checksum), then there are an expected 4000+ hashes that are potential targets [1]; that cuts your security by 12 bits.  This can be mitigated somewhat by using different AES keys for the different chains, but that's not free, and it only reduces the concern.

The existing proposals for doing Winternitz, such as XMSS or LMS, get around this by stirring in a different value for each Winternitz iteration (and so each $H$ invocation is distinct), and hence such multicollision attacks do not apply.

The other objection depends on why you're using a OTS (and not a more standard signature algorithm, such as RSA or E[Cd]DSA).  One potential reason is for Quantum Resistance; for that, 128 bits of hash output don't cut it.  Now, there are other potential reasons (e.g. your signer or your verifier has constrained resources), and so this objection might not apply.

[1]: Note: not only the hash that appear in the signature are potential targets, but any hash latter in the chain as well.


I know that MD5 should not be used for password hashing, and that it also should not be used for integrity checking of documents. There are way too many sources citing MD5 preimaging attacks and MD5s low computation time.

There is no published preimage attack on MD5 that is cheaper than a generic attack on any 128-bit hash function.  But you shouldn't rely on that alone when making security decisions, because cryptography is tricky and adversaries are clever and resourceful and can find ways around it!

  Identifying malicious files, such as when Linux Mint's download servers were compromised and an ISO file was replaced by a malicious one; in this case you want to be sure that your file doesn't match; collision attacks aren't a vector here.

The question of whether to publish known-good vs. known-bad hashes after a compromise is addressed elsewhere—in brief, there's not much that publishing known-bad hashes accomplishes, and according to the citation, Linux Mint published known-good, not known-bad, hashes.  So what security do you get from known-good MD5 hashes?

There are two issues here:

If you got the MD5 hash from the same source as the ISO image, there's nothing that would prevent an adversary from replacing both the MD5 hash and the ISO image.

To prevent this, you and the Linux Mint curators need two channels: one for the hashes which can't be compromised (but need only have very low bandwidth), and another for the ISO image (which needs high bandwidth) on which you can then use the MD5 hash in an attempt to detect compromise.

There's another way to prevent this: Instead of using the uncompromised channel for the hash of every ISO image over and over again as time goes on—which means more and more opportunities for an attacker to subvert it—use it once initially for a public key, which is then used to sign the ISO images; then there's only one opportunity for an attacker to subvert the public key channel.
Even if you got the MD5 hash from a known-good source, collision attacks may still be a vector in cases like this.  Consider the following scenario:

I am an evil developer.  I write two software packages, whose distributions collide under MD5.  One of the packages is benign and will survive review and audit.  The other one will surreptitiously replace your family photo album by erotic photographs of sushi.
The Linux Mint curators carefully scrutinize and audit everything they publish in their package repository and publish the MD5 hashes of what they have audited in a public place that I can't compromise.
The Linux Mint curators cavalierly administer the package distributions in their package repository, under the false impression that the published MD5 hashes will protect users.

In this scenario, I can replace the benign package by the erotic sushi package, pass the MD5 verification with flying colors, and give you a nasty—and luscious—surprise when you try to look up photos of that old hiking trip you took your kids on.

  Finding duplicate files.  By MD5-summing all files in a directory structure it's easy to find identical hashes.  The seemingly identical files can then be compared in full to check if they are really identical.  Using SHA512 would make the process slower, and since we compare files in full anyway there is no risk in a potential false positive from MD5.

When I put my benign software package and my erotic sushi package, which collide under MD5, in your directory, your duplicate-detection script will initially think they are duplicates.  In this case, you absolutely must compare the files in full.  But there are much better ways to do this!

If you use SHA-512, you can safely skip the comparison step.  Same if you use BLAKE2b, which can be even faster than MD5.
You could even use MD5 safely for this if you use it as HMAC-MD5 under a uniform random key, and safely skip the comparison step.  HMAC-MD5 does not seem to be broken, as a pseudorandom function family—so it's probably fine for security, up to the birthday bound, but there are better faster PRFs like keyed BLAKE2 that won't raise any auditors' eyebrows.
Even better, you can choose a random key and hash the files with a universal hash under the key, like Poly1305.  This is many times faster than MD5 or BLAKE2b, and the probability of a collision between any two files is less than $1/2^{100}$, so the probability of collision among $n$ files is less than $\binom n 2 2^{-100}$ and thus you can still safely skip the comparison step until you have quadrillions of files.
You could also just use a cheap checksum like a CRC with a fixed polynomial.  This will be the fastest of the options—far and away faster than MD5—but unlike the previous options you still absolutely must compare the files in full.

So, is MD5 safe for finding candidate duplicates to verify, if you subsequently compare the files bit by bit in full?  Yes.  So is the constant zero function.

  (In a way, this would be creating a rainbow table where all the files are the dictionary)

This is not a rainbow table.  A rainbow table is a specific technique for precomputing a random walk over a space of, say, passwords, via, say, MD5 hashes, in a way that can find MD5 preimages for hashes that aren't necessarily in your table with fewer trial hash evaluations than a naive search.  (It can also be done in parallel with the search to not only speed it up but reduce the price/performance ratio.)  It is not simply a list of precomputed hashes on a dictionary of inputs.

(The blog post by tptacek in 2007 that you cited, and the blog post by Jeff Atwood that it was a response to, both misrepresent what rainbow tables are.  tptacek claims in 2019 that he DGAF about rainbow tables, perhaps because modern password hashes thwart them by the mere use of salts.  But password search under a fixed, unsalted hash function is only one application of the idea, for which the term was popularized.  Rainbow tables are relevant to any preimage search as noted in the original paper, such as AES keys given known plaintext/ciphertext pairs.  And it's not just a trivial time/memory tradeoff—a rainbow table preimage search can reduce price/performance ratio if parallelized.  This is why, for instance, AES-128 should not be construed to give ‘128-bit security’.)

  When the password scheme article states that "MD5 is fast", it clearly refers to the problem that hashing MD5 is too cheap when it comes to hashing a large amount of passwords to find the reverse of a hash.  But what does it mean when it says that "[MD5 is] too slow to use as a general purpose hash"?  Are there faster standardized hashes to compare files, that still have a reasonably low chance of collision?

I don't know what tptacek meant—you could email and ask—but if I had to guess, I would guess this meant it's awfully slow for things like hash tables, where you would truncate MD5 to a few bits to determine an index into an array of buckets or an open-addressing array.


I think you can find the pairs $(i,j)$ with $P_i(y_j)=0$ in time $N\cdot\log(N)$ for preprocessing and $k\cdot n\cdot\log(N)$ for processing, if you can use space $N$ for preprocessing the $y_i$:

Preprocessing consists of generating (1) the list $E$ of all $j$ such that $y_j$ is even, and (2) a tree (or something even faster) that you can query in time $\log(N)$ for a given $y$ to get the list of all $j$ such that $y=y_j$.

Now loop over all $x_i$, adding to the result either (1) all indices $(i, e)$ for $e\in E$ if $x_i$ is even or (2) all $(i, j)$ with $y_j = -x_i\cdot 2^l \bmod 2^k$ for some $l\le k$ (using the precomputed tree) if $x_i$ is odd.

The reason why this gives the correct result is written in my first comment to your question.


What is the benefit of zero knowledge identification (Fiat Shamir) over a standard digital signature?

Solution 1 has some weakness when the verifier is malicious. If the prover's private key $a$ is used for decryption, Solution 1 provides the verifier with a decryption oracle, i.e., a malicious verifier can decrypt any ciphertext encrypted with the public key $v$. On the other hand, Solution 2 reveals nothing about the private key $a$ because the random number $r$ (which masks the private key $a$ when the verifier sends a bit 1) is chosen by the prover rather than the verifier.


Are there any known problems or attacks for using SHA1(AES_key) as the HMAC key?

We don't know. Although it seems unlikely to the extreme that there is some kind of mathematical equation that gets easier to solve when the second key relies on the first key, we probably cannot prove it. So that's it for the theoretical problems.

One practical problem is that when the key for confidentiality is obtained by the adversary (e.g. through a side channel attack) that the HMAC key is also obtained; the adversary only has to perform a SHA-1 calculation over it, after all. It depends on the use case how much of an actual problem this is - if the confidentiality is the main goal then it doesn't matter, but if the authenticity or integrity of the messages is more important then this might be a good reason to think of another scheme (or to swap the keys, and have the encryption key be dependent on the MAC key).

SHA-1 over a key can be thought of as a poor mans KBKDF (key-based key derivation function). As a KDF again we cannot prove that SHA-1 is a strong method, but as a single SHA-1 is almost identical to e.g. KDF1 or KDF2, generally we assume it is OK.

Sometimes the hash over the key is also used as a poor mans key check value (KCV). KCV's are considered public knowledge. Of course you'd be in serious problems if you'd use both the poor mans KDF and poor mans KCV over the same key in the same protocol.

As we're now getting into the realm of what constructs we generally use to achieve this goal of generating two keys out of one: usually we perform the following instead:

$$K_\textit{mac} =\operatorname{KDF}(k_\textit{master}, \texttt{"mac"})$$ $$K_\textit{enc}=\operatorname{KDF}(k_\textit{master}, \texttt{"enc"})$$

where $k_\textit{master}$ has the value of the original encryption key. $\texttt{"mac"}$ and $\texttt{"enc"}$ are labels that are part of the $\textit{info}$ string that helps to deviate the MAC and encryption keys from each other.

For instance, you could use HKDF-expand as KDF. That's a much stronger construct as HKDF uses HMAC internally. It also removes the dependency of the HMAC key on the encryption key; they now both rely solely on the original key now called the master key, which isn't used in the protocol afterwards.

As generally the KDF is only executed once per session it should not influence the performance of the protocol all that much. So usually it makes sense to play it safe rather than to use the quick and dirty method of just taking the SHA-1.

The fact that these kind of constructs are proposed together with (what I assume is CBC) encryption and HMAC makes me wary of the knowledge of the person producing the protocol. In this case the scheme was really originating from the person asking the question that you linked to.

Usually we now use an authenticated (AEAD) scheme for new protocols, and most AEAD schemes require only one key from the very start, rendering the entire discussion and additional calculations unnecessary.


Is ECDH(E) Key Exchange FIPS 140-2 compliant?

If you look at the FIPS Implementation Guidelines for FIPS-140-2 here
https://csrc.nist.gov/csrc/media/projects/cryptographic-module-validation-program/documents/fips140-2/fips1402ig.pdf
In section D.8 Key Agreements, you will find the recommendations.
This recommendation points to NIST SP-800-56A, where in Appendix D, there is a table of  "Approved ECC Curves and FFC Safe-prime Groups."
SP-800-56A has references to FIPS186-4 and RFC4492 (for TLS) and RFC 5903 (for IKE).
These references should be enough to justify use of ECDH in a FIPS140-2 approved device.


Signing a document: which algorithm to use?

I guess they would need to go to my website, find the document and check whether the signed code is the same as the document they want to check.

If you assume people are able to trust your website, you could simply list the SHA-256 (for example) hashes of your documents on your website. Perhaps include an URL in the signed document pointing to a particular page on your site that lists the hash for that file.

Trusting others to get the correct hash from your website when they visit the URL would remain unsolved. Someone could intercept the request and return a different hash that matches a modified document they've distributed.

The more complex option is public key signatures.

If you go that way you would use something like GPG/PGP to generate a key-pair, distribute the public key, then sign the documents using the private key. In this case an attacker couldn't produce a different signature that matches your key even if they controlled requests to the documents and your website.

However, you would still need to get your public key into the hands of anyone wanting to verify the signature. An attacker who could distribute their own key as yours could again forge signed documents in your name.


Book request about elliptic curves, RSA and DSA

This is an excellent resource that covers those topics: http://www.crypto-textbook.com/. And here's a channel that follows the book.


Hash and (MAC) based signatures using zk-SNARK

This is a valid paradigm for building a signature scheme, although a secure commitment scheme should be used to commit to $k$ instead of just using $H(k)$ as the public key. This type of construction was published by Bellare and Goldwasser at CRYPTO'89; see New Paradigms for Digital Signatures and Message Authentication Based on Non-Interactive Zero Knowledge Proofs. Formally, they use a NIZK, as you stated.


Why is the clear communication of the UID such a problem?

Problem is that most RFID tags can be read at a distance, without the holder knowing. Since the UID is readable, and if it is fixed, that can help track the holder. That's why there is a trend¹ in modern RFID tags towards random UIDs (RID), and making it necessary for the tag reader to hold a key in order to be able to read any tag-identifying information. As explained in the question's quote, that key must be non-diversified, except when there is another tag identifier available thru a different channel².

  Can the UID be used to crack the key?

No. The tag's UID is an arbitrary public number: fixed at manufacturing (often sequential or random), or drawn randomly³ at each power-up or reset of the tag (see NFC's AN10927). In a system with non-diversified key³, the UID has no relation to the key. In a system with diversified tag key $K_D$ derived from a master key $K$ (not in the tag), the UID has no relation with  $K$. If the tag key is diversified per the UID, it holds the relation $K_D=\operatorname{KDF}(K,\text{UID})$. However, not knowing $K$, knowing the UID does not allow finding the tag key $K_D$, for proper $\operatorname{KDF}$. And even if $K_D$ is somehow extracted from some tag(s), then for proper $\operatorname{KDF}$ that does not allow finding the master key $K$ (which would allow to find $K_D$ for other tags).

  How should one diversify the key instead?

In some tags, when the tag-identifying information (other than UID) has been read using the first non-diversified key, it can then be used to diversify another key, bringing back the security of diversified tag keys. I have no idea about if this is possible on this particular tag.

As already explained, in some application it could be possible to diversify the key using a different information read thru an other mean, e.g. optical.

¹ That's currently marginal. In France, practice is that legitimate readers are required not to keep identifying information beyond the requirement of the application, and identifying information kept by unrelated applications should be protected against reconciliation (for example, a serial number read from an RFID tag could be be encrypted by an application-unique key before being entered in a database).

² In many modern passports/MRTDs that can be read per ISO/IEC 14443, the design is such that there is no identifying information (personal or not) readable directly by that channel, including a mere serial number/(U)UID/PUPI. Reading such information only becomes possible after reading data on the optically readable strip inside the passport, which (after a public transformation) acts as a key to unlock reading more thru the RF channel. I heard that one of the design rationale was to defeat a device that performs a nefarious action (explosion, toxic spray…) when a specific person approaches. If someone has a reference for the true design rationale, please leave comment.

³ In this case, the (U)UID has no cryptographic role and is only used for addressing purposes when there are several tags in the operating field of a reader.


About the Security of PCBC Encryption Mode

PCBC is provably secure for confidentiality, assuming you use a random IV like with CBC. The attacks you mention are all on the integrity rather than confidentiality of PCBC.
No, you probably cannot construct secure authentication with PCBC and an unkeyed hash. For that you should instead use an actual MAC.
While PCBC propagates errors, it only propagates them towards the end of the message. It sounds like you would want the file to be completely undecryptable if modified. What would work is an all-or-nothing transform. Such schemes are typically unkeyed, but if you encrypt the result of the AONT, the whole thing needs to be correctly decrypted to reveal the plaintext.

So what I would recommend is:

Use an all-or-nothing transform on the plaintext.
Encrypt that using some standard authenticated encryption algorithm. Like AES-GCM or AES-CTR + HMAC.

Note that nonce uniqueness is critical with these encryption algorithms, especially the former where you lose both authentication and confidentiality if nonces are reused.


Is it possible to have interactive decryption?

Probably not. When Bob at the end of the interaction finally computes the plaintext, it must be a function of everything he has obtained thus far; there's nothing stopping him from running the same computation again, unless you introduce some kind of special hardware or other additional assumptions.

In other words, decryption is deterministic, and we know that deterministic interaction is useless ($\mathbf{dIP} = \mathbf{NP}$).


Does having multiple hash iterations of the same message weaken your original message security?

A hash function is a hash function: a deterministic, public function with no secret parameter. Everybody can compute SHA-256, and they all get the same results when applied on the same inputs.

Therefore, if you give H(m) to the attacker (who tries to recover m: a preimage attack), giving him H(H(m)) too does not grant him any extra actual help -- because he already has it: given H(m), he can compute H(H(m)) himself (and H(H(H(m))) and so on).

In the question above, the attacker is shown x = H(m) (for an unknown message m) and challenged to find a message m' such that H(m') = x. Another, distinct but interesting setup, is the following: suppose that the attacker is shown y = H(H(m)) for some unknown message m, and is challenged to find m'' such that H(H(m'')) = y. This raises two questions:

Is this new challenge (finding a preimage for double-hash, not for the simple hash) harder, easier, or equivalent to the original preimage attack ?
Does showing H(m) in addition to H(H(m)) (but still challenging the attacker with finding a preimage for the double-hash, not for the simple hash) help him ?

We suppose that the hash function is "perfect", i.e. acts as a random oracle. For a perfect hash function, the best attack for preimages is luck, i.e. trying different inputs until a match is obtained. If the hash outputs data in a set of size N, then luck works with an average cost of N invocations of the hash function. For a 256-bit perfect hash function, N = 2256.

Now for the double-hash: if H() acts as a random oracle, then so does H(H()), albeit with a slightly reduced output set. Indeed, the outer hash works over the 256-bit output of the inner hash; H, as a random oracle which offers 256-bit outputs, is expected to produce, for all possible 256-bit inputs, about (1-(1/e))N distinct outputs (to say things otherwise: if H produced all possible 256-bit outputs when applied over all possible 256-bit inputs, then H would be a permutation over the set of 256-bit values, which would be very surprising and is not expected from a random oracle). Therefore, the double-hash produces outputs in a set of size about 0.632*N, and that's also the cost of the generic preimage attack on the double-hash. BUT remember that this cost is expressed in the number of invocations of the attacked function. Invoking the double-hash means computing H twice. So we are talking about 1.264*N invocations of H. This yields our answer to my first question: finding a preimage for the double-hash is about 26.4% harder than finding a preimage for the simple hash.

So this also answers my second question: does knowing H(m) helps the attacker finding a preimage for the double-hash ? Indeed it does, because he can then search for a preimage for the simple hash, in cost N instead of 1.264*N, and any solution will also be a solution for the double-hash.

Generalized result

Let H(n) be the n-hash (n nested invocations of the hash function). Let Cn be the challenge of finding a preimage for H(n) (attacker is given x = H(n)(m) for an unknown m, and his goal is to find an input m' such that H(n)(m) = x). Then the following holds:

The cost of solving Cn rises when n increases: though the output space of H(n) reduces with bigger n values, the individual cost of each invocation of H(n) increases and more than cancels the gains obtained through the space reduction. (This result holds until n becomes close to the square root of N, at which point things become more complex to analyze.)
When the attacker tries to solve Cn, giving him additional values H(k)(m) for values k > n does not help him, because he could have trivially computed them himself (H(n+1)(m) = H(H(n)(m)), and so on). If obtaining these extra values was a good idea, then he would do it right away.
When the attacker tries to solve Cn, giving him an additional value H(k)(m) for a value k < n indeed helps him, because it allows him to solve Cn by solving the comparatively simpler Ck.

Of course, we are speaking only theory here; with hash functions offering an output of more than 100 bits, the involved costs are way too high to be envisioned. In practice, preimages on simple hash or double-hash are unfeasible -- unless the hash function is not "perfect" and we can exploit a structural weakness of that specific hash function, at which point anything goes.


Linkable Ring Signatures on Pairing-Friendly curves

As I know, the pairing on bn-curve is type 3, $G_1\times G_2\rightarrow G_T$.
In CryptoNote, the key image is $I=H(P)^x$ and it can't be attacked if $H(*)$ and $P$ belong to same group.

See my question related.


Can AES in CCM or GCM counter mode interoperate with AES in "plain" counter mode (CTR)?

A message encrypted with AES-GCM can be decrypted with an AES-CTR library IF the authentication tag is stripped from the message.
If you are encrypting with AES-GCM and then adding an HMAC tag, you need to strip the HMAC and the GTAG off the message in order to decrypt it, assuming the IV section of the message is in the correct location for each library to handle.
edit:
Thanks to Maarten Bodewes for pointing out that the initial counter value is used in GCM to create the Galois hash key, and thus would need to be incremented by 1 in order to read the message data properly.


NIST 800-90B /Non-IID track - min-entropy result > 8 for 8-bit symbol

There are three separate reasonable questions here.

What does LRS Estimate mean?
Does the software compute it correctly?
Are stupid entropy estimation tools like this useful for your goal?

The setting is that we hypothesize specific families of generating processes for the data that came out of a black box.  The families of generating processes are all quite simple-minded.  For example:

A gremlin in the black box rolls a 256-sided die with unknown face probabilities $p_i$ independently for each octet in the string.
A gremlin in the black box emits outputs from unknown states by a hidden Markov model with unknown emission probabilities $e_i$ and transition probabilities $t_{ij}$.

Each of these models has a certain measure of min-entropy that is determined by the choices of parameters, such as the $p_i$.  The NIST tool, like any other entropy estimation tool, estimates the min-entropy by fitting parameters and evaluating or estimating an upper bound on the min-entropy in the specific case of the model with the parameters it fit.  Obviously 8.0028 is an upper bound on the min-entropy of an octet.  How do we get there?

To address (1), what the LRS Estimate means, the LRS estimator posits a generating process something like this:

A gremlin inside the black box has a hat with $d$ strings of varying lengths on it, the $i^{\mathit{th}}$ string having $n_i$ copies.  It shuffles the hat and draws a string out to add to the output; then it repeats.

The estimator works by guessing a few strings that might be in the hat based on repeating and nonrepeating contiguous substrings in the data, and uses the frequency of those strings as an estimate for the probability that they will occur.  (The complete details of the computation are in NIST SP800 90A, §6.3.6.)  From those probabilities it yields an estimate of the min-entropy using the standard $-\max_i \log p_i$ formula.

It doesn't consider all contiguous substrings in the output (there is a combinatorial explosion of them), so it ignores some of the probability space and thus slightly underestimates the probability of each substring it does consider, which has the effect of slightly overestimating the min-entropy—which would explain why it seems to produce an entropy rate of just over eight bits per octet.

Now, to address (2), does the software implement it correctly?  That's a question for codereviews.se, and maybe for stats.se if you want to make sure that the posited model and the estimator for the probabilities is sensible and what was intended by NIST.

Finally, to address (3), whether this is useful for your goal, the answer is not very.  It will detect certain families of patterns in your data, if those patterns appear.  High estimates like the LRS Estimate in your sample are not useful: they just mean that this particular pattern didn't appear.  Low estimates suggest that someone at NIST who wasn't even thinking about your particular noise source could predict its output with pretty good chances of success.  That's usually bad sign.  So don't worry about the slightly >8-bits-per-octet estimate for LRS: worry about the ~5-bits-per-octet estimate with a Markov model!  Does your device alternate between internal states with somewhat more predictable emission probabilities?

What you really need to do is study the physics of the object in question from an adversary's perspective, and try to find the best way to predict the output knowing how your particular noise source works.  Then compute the entropy of that model.  If it's higher than all of the NIST estimates, either you had a lucky sample or someone at NIST who doesn't even know what you're working on was better at studying your noise source than you are.


Since I haven't heard of it and it isn't immediately obvious (not even from the linked RFC) what it does or how, can somebody provide a short explanation?

In short, Logical Key Hierarchy – LKH – is a solution to handle keying issue in secure group communication. LKH is interesting because it allows keying in an efficient and scalable way by minimizing the number of transmissions in rekeying as well as storage requirements. (At it's core, there's a binary tree.)

You might want to check the ample materials available online (which you can find using your favorite search engine) for examples. Mentioning only two random materials of many: there's a short, 15 page lecture from 2003 by D.R. Stinson (PDF) and there's Logical Key Hierarchy Protocol (PDF) for a protocol example.


Diffie-Hellman problem: is DH still secure if $g^{a^2}$ is known?

No, the assumption "given $g, g^a, g^b, g^{a^2}$, it is infeasible to compute $g^{ab}$" is not known to reduce to the CDH assumption. In fact, we can even prove a separation in the generic group model (meaning, it is impossible to build such a reduction by using the group operations in a black box way). Intuitively, this is because we do not know how to generate an instance of the first assumption given a CDH instance: it requires computing $g^{a^2}$ from $g^a$, which is already equivalent to breaking the CDH assumption. However, this assumption remains a plausible one: a scheme whose security would reduce to this assumption would be considered secure in the crypto community. In fact, many assumptions of this type which are variants of the CDH assumption are common in the crypto community.


BGN encryption scheme with unbounded message space

There is a scheme whose purpose is exactly that, the LWE-based BGN-like encryption scheme. In general, we do not know how to achieve large message space for homomorphic encryption using discrete-log-style crypto; all known current solutions require lattice-based cryptography.

EDIT: reading the comments on your question, it seems you want to leak only whether the output is zero or not, by masking with a large random $r$ multiplicatively. But the standard BGN cryptosystem already allows that: the parties can always decrypt $g_t^{\mathsf{DFN(x)}}$ with BGN ($g_t$ is a generator of the target group), only the discrete logarithm at the end requires the message space to be small. However, seeing $g_t^{r\cdot\mathsf{DFN(x)}}$ for a large random $r$ already allows to see efficiently whether $\mathsf{DFN(x)} = 0$ or not: if it is equal to zero, then $g_t^{r\cdot\mathsf{DFN(x)}} = 1$; otherwise, $g_t^{r\cdot\mathsf{DFN(x)}}$ is just a random group element since $r$ is random.


Is there a secure cryptosystem that can be performed mentally?

(Converted to answer from a comment.)

If pen and paper are permitted, one could probably carry out the RC4 algorithm fairly easily using 256 numbered pieces of paper (small post-it notes might be ideal, since they'd be harder to move by accident) arranged in a 16 by 16 grid (I'd suggest numbering the notes in hex for easier indexing), with two coins or something to keep track of the $i$ and $j$ indices.  The algorithm itself is simple enough to memorize, too.  To destroy the internal state, just shuffle the notes (and cut them up and burn them if you want to be sure).

The hard part would be key setup.  The usual way of keying RC4 is not only laborious to do by hand (it's more or less equivalent to 256 encryption steps), but doesn't really shuffle the state all that well.  The standard remedy for that is to discard the initial part of the output, which makes for even more work for our would-be computerless cryptographer.  If you can safely carry around the state as a stack of notes, you can do it once and then just keep churning out more of the same keystream for each message, but if not, some alternative key setup mechanism would be highly recommended.

Also, there's always Solitaire, although it needs a deck of cards and has significantly worse biases than RC4.  In fact, the design of Solitaire bears a strong resemblance to RC4, and was almost certainly inspired by it.  Given the known weaknesses of Solitaire, if you want a hand cipher using playing cards it might be better to go with RC4-52 (i.e. standard RC4, only with 52 instead of 256 elements in the state array), although I don't know if anyone's done any serious cryptanalysis of that.  (It's almost certainly weaker than normal RC4, but I'm not sure how much weaker.  Probably still better than Solitaire, though.)


Does adding more characters to the Enigma rotors improve crypto strength?

Does adding more characters to the (Enigma) rotors improve crypto strength?

Not really… since the weaknesses of Enigma go well beyond the count of chars per wheel!

Of course you could – theoretically – think of using very big (read: huge) wheels with an insane char range. But, when looking at the “time” and “resources” you would need to invest each time you’ld merely wanted to encrypt and decrypt things with such a beast, it simply wouldn’t make much sense. Modern ciphers already blow Enigma out of the water in terms of speed, cryptographic-strength, etc.

Differently stated: the gain you would achieve by adding chars won’t be big enough to level-up good old Enigma into the realms of more recent and better preforming algos (like aes, chacha, et al).

Also, as CodesInChaos already hinted in his comment, it would put you on a very slippery road with a good chance that you’ll end up introducing additional attack vectors. In a worst case, you could break one of the stronger parts of Enigma while ignoring the real cryptographic weaknesses that already come with Enigma; which would result in something like a (let’s just call it) cryptographic nightmare.

Yet, don’t get me wrong: for something like a non-public “student project” with the goal to have a truckload of chances to shape your cryptanalytic abilities… this could be fun to fiddle with and maybe worth thinking about for a minute. But if you do, you better be prepared to notice you’ll need to fix a whole truckload of nasty little issues related to Enigma. Simply increasing the char count will not do it.


Why is Curve25519 mostly used for key exchange?

A number of reasons contribute to this.

Curve25519 has a non-governmental origin.

It's a curve that's very safe by design, and impregnable to many side-channel and other weaknesses that other curves suffer from.

Also, it's a curve with 'nothing up my sleeve' coefficients.

Unlike the NSA curves, which NIST endorse.

Although not directly related, after the backdoor in Dual_EC_DRBG had been exposed, suspicious aspects of the NIST's P curve constants led to concerns that the NSA had chosen values that gave them an advantage in finding private keys. Since then, many protocols and programs started to use Curve25519 as an alternative to NIST P-256 curve.

As Kelalaka states, the constant time scalar multiplication provided by the Montgomery ladder is also pretty cool.

You cannot directly encrypt arbitrary amounts of data direct with elliptic curves.

The public key is a point on the curve and the private key is a number.

There isn't an elegant mechanism to directly encrypt (generalised ElGamal notwithstanding).

That's why key agreement revolves around finding a shared point on the curve and using a digest of the x co-ordinate of that shared point to use with a fast, secure symmetric cipher.


Your understanding is correct. The SPDZ protocol can be used for any number of two or more parties. In fact, this is one of the strengths of the SPDZ protocol. Namely, many recent secure computation protocols such as the various versions of the Yao protocol or the TinyOT protocol are limited to two parties. So it may sometimes be overemphasized that SPDZ goes beyond two parties.

There is no drawback to using SPDZ with just two parties compared to three parties. Certain aspects such as the required broadcast actually becomes simpler in the two party case. So you should never try to add additional parties beyond what you need, it will only make you application less efficient.

However, there are many trade-offs to consider when choosing a secure computation protocol. Therefore, there could be good reasons to pick an other protocol than SPDZ in a two party setting. For example, SPDZ is based on arithmetic operations. If your application is heavy on Boolean operations, other protocols such as TinyOT which is based on Boolean operations may perform better. Also, SPDZ has round complexity proportional to the depth of the circuit you are evaluating. Yao has constant round complexity for any circuit. So if you are in a high latency setting or evaluating a very deep circuit, Yao may perform better than SPDZ.


Can someone explain how OPRF (Oblivious pseudo-Random Function) is based on OT (Oblivious Transfer)?

Construction of an "Oblivious Pseudo-Random Generator" from Oblivious Transfer

I will try to explain Section 4.3 of the paper you refer to [1].
Personally this other paper [2], which builds upon the protocol of [1],
helped me a lot.

Here is the basic idea:

the sender and the receiver agree on hash functions $ h_i $
the sender creates an array $ G $ filled with random values
for each element $ x $ of its set $ X $,
the sender XOR together the items of $ G $ which index are obtained by hashing $ y $ with the hash functions:

$$ m_{P_1}[j] = \bigoplus_i G[h_i(x_j)] $$

the sender sends these values (called "summary values" in [2]) to the receiver
The receiver, for each element $ y $ in its set $ Y $,
will use OT to retrieve the cells of $ G $ corresponding to $ x $,
so that he is able to compute the "summary values" for his own elements:

$$ m_{P_2}[j] = \bigoplus_i G[h_i(y_j)] $$

the receiver compares the summary values he got with the summary values he received
to find out the intersection, that is $ y_i \in X $ if and only if $ \exists j, ~ m_{P_1}[j] = m_{P_2}[i] $.

The use of OT extensions is simply an optimization because $ G $ is quite large
and "standard OT" is expensive.
They also use another optimization made possible by the fact that $ G $ is filled with random,
which simply put allows you not to pay for items of $ G $ you do not use.

Now where is the Oblivious Pseudo-Random Generator here?
First note that this is not an Oblivious Pseudo-Random Function,
it's a Generator.
An OPRF must compute a well-defined, efficiently computable function.
For instance in this paper [3] building an OPRF,
the function is the Dodis-Yampolskiy Pseudo-Random Function:

$$ f_k(x) = g^{1/(k+x)} \text{in group $<g>$ of composite order $n$} $$

In the case of [1] and [2] we are not evaluating a "function" per se
but just "spitting out" random values, which matches the definition given in [1] of a "OPRG".
Actually the first time I saw the term "Oblivious Pseudo-Random Generator" was in [1]
and the way they define it (second text block of Section 4.3) makes me think that
they are the first to use this notion.

Maybe this is what confused you ?
Because you can also build a PSI protocol using an OPRF (see [4]),
but it is not what they are doing in Section 4.3 of [1].


Is a function defined as PRF with a given key a PRG?

Consider a PRF $F$ which on $n$-bit keys maps $n$-bit inputs to $2n$-bit outputs. Consider $F'$ where $F'_k(x) = F_k(x)$ if $k \ne 0^n$ and $0^{2n}$ otherwise.


why was padding changed when keccak became sha3?

It accomplishes 2 things.

SHA-3 hashes of the same input will be distinct from Keccak hashes with the same rate/capacity.
XOFs (SHAKE) with the same rate/capacity will start also with distinct hash output, when compared to both SHA-3 and Keccak

There is no change to security or performance, although having SHAKE share a prefix with a hash of the same input would have been considered a security concern.

Also, padding conventions differ between the implementation and the code, the difference between SHA-3 padding and Keccak padding is minimal. SHA-3 still supports inputs in bits rather than bytes, and the padding is also bit based.


Role of session identifier in Otway-Rees protocol

The $M$ in  Otway-Ress protocol (It is $C$ as the Challenge in the article);

  In mutual authentication, both parties are suspicious of each other and of the freshness of the authentication messages; therefore each must generate independent challenges in order to assure themselves of the
  timeliness of the interaction.
  Its important property is that it has not previously been used to authenticate the two parties concerned.
  This property can be guaranteed either by storing all previously used challenges, by using numbers from a monotonically increasing sequence (e.g. time) or probabilistically by generating a sufficiently large number randomly.

$M$ is used to prevent replay attacks.


Implementing forward secrecy in OpenPGP with public key authentication

I'm going to describe two options that you have. There may be more that I don't know about.

The first is to use long-term signing keys to sign public diffie-hellman keys. Upload a bunch of those to the cloud. Then when someone wants to share a file with you, they:

download your "next" signed public diffie-hellman key
verify the signature using OpenPGP, abort if it fails
generate their own new public diffie-hellman key
use your "next" key to generate a shared secret key (using their private diffie-hellman key), encrypt the file with that (you can actually use OpenPGP for this too, it would be the symmetric key for encryption)
sign their new public diffie-hellman key with their long term secret (using OpenPGP)
upload their signed public ephemeral diffie-hellman key, an index describing which of your temporary public keys they used, and the encrypted message
delete their new public diffie-hellman key, etc.

When you come along later to download the file, you:

download everything they uploaded in #5
check the digital signature using OpenPGP, if it fails abort
use your temporary private key for the given index to compute the shared secret key
decrypt the file
delete your temporary private key, their signed temporary public key, etc.

This is basically what Open Whisper Systems does for encrypted text messages.

Your other option is to throw away OpenPGP and do what is described in A Forward-Secure Public-Key Encryption Scheme and discussed in this answer*.

*Okay, that answer does mention my first proposal too as a "trivial (and hence awful) solution". I've added more detail and the link to Open Whisper Systems. Since Open Whisper Systems is doing it, it can't be too awful, right?


Are there any homomorphic first and second preimage resistant (cryptographic) hash functions?

Fix a finite group $G$ of order $\ell$, written additively, in which discrete logarithms are difficult.  Fix a standard base point $P \in G$ of large prime order.  The function $H\colon \mathbb Z/\ell \mathbb Z \to G$ given by $$H(n) := [n]P = \underbrace{P + \cdots + P}_{\text{$n$ times}}$$ is a preimage-resistant homomorphism: $H(n + m) = H(n) + H(m)$, and finding preimages is exactly finding discrete logarithms.

Of course, if $\ell$ is prime, then $H$ is injective and so doesn't compress its input at all; while if $\ell$ is composite, then $H$ is not collision-resistant since $H(n + \operatorname{ord} P) = H(n)$ for all $n$.  See the linked answers to address collision resistance.


Prove that some Cyphertext C encrypts some plaintext D

Assuming that $D$ is the correct decryption, we have

$$C = g^D r^n \pmod{n^2}$$

for some value $r$.

Someone with the private key can easily recover $r$; hence they can just display it (and you can easily verify the above equation).

Learning the value $r$ does not allow you to derive the private key (if it did, you could encrypt values yourself using a known value $r$, and then use that to recover the private key).

Alternatively, if you need a zero knowledge proof (for example, if the value of $r$ would tell you something about the internal computations that the other side doesn't want you to know), you can do something like this cut-and-choose protocol several times:

They pick a random number $r'$ with $\gcd(r', n)=1$, and send $a = r'^n \bmod n^2$
You then choose either 0 or 1
If you pick 0, they output $r'$, which you can verify by checking if $a = r'^n \bmod n^2$
If you pick 1, they output $b = r \cdot r'^{-1} \bmod n$, which you can verify by checking that $C = a g^D b^n \pmod {n^2}$


S-Box's are invertible. The inverse S-box is simply the S-box run in reverse.

One way to calculate the inverse of an S-box is; all you need to use the S-Box itself to find an element's inverse.

For example; look at the Wikipedia example.

00 maps to 63 in the S-box, 63 maps to 00 in the inverse S-Box
54 maps to 43 in the S-box, 42 maps to 64 in the inverse S-Box

This can be executed by passing only once the elements of the S-Box. The complexity will be $\mathcal{O}(n^2)$ where $n$ is the $row=column$ size of the matrix.


Why this brute force attack doesn't reduce all cryptographic hash functions' security bits against collision attacks to N/3?

Let $M$ be the number of queries to a uniform random function $F$ at distinct points $X_1, X_2, \dots, X_M$.  The probability of a repeated value $F(X_i) = F(X_j)$ for $i \ne j$ is at most $M^2\!\big/2^N$ by the birthday paradox.  For $M = 2^{N/3}$, this is $2^{2N/3}\!\big/2^N = 1\big/2^{N - 2N/3} = 1\big/2^{N/3}$.  If your calculation doesn't fit this bound, there's an error in your calculation.

‘But what if we come upon a short cycle in $H \mapsto F(S \mathbin\| H)$?’, you ask.  The expected number of points before a repeat in a uniform random function on a domain of $2^N$ elements is $\frac12\sqrt{2\pi\,2^N} - 1 \approx 2^{N/2}$ (Harris 1960 Eqs. 3.4 & 3.11, see paper for more details of distribution; paywall-free).  So no, this method doesn't improve the expected cost.

Using a clever tortoise-chasing-hare algorithm to find a cycle, rather than making a big table and checking for duplicates, may reduce the memory or area*time cost of an attack, as in the van Oorschot–Wiener parallel collision search machine, but it doesn't escape the birthday bound!


What advantage is there for using a nonce and a timestamp?

However, if a nonce can provide all the protection a timestamp does, why would they ever be used together?

If you use a timestamp in combination with a nonce, it can help mitigate the risk of nonce reuse.  Guaranteeing that nonces are never duplicated within the relevant scope can often make a system more complicated, because it needs to maintain state reliably while that scope is "alive."

Imagine, for example, that a system that sends packets encrypted with a counter nonce loses power momentarily, comes back up, and resumes transmission with the key/nonce pair that was saved before the power failed.  How do you guarantee that it won't reuse a nonce that it used just before the power loss?

These sorts of problems fall under the rubric of stateful cryptography—cryptographic schemes that require you to keep and update some state between invocations in a correct fashion.  Keeping such state incorrectly or unreliably is a common source of failures.  Timestamps don't always solve state problems, but they sure can help.

In addition they can be helpful for all sorts of non-cryptographic reasons.  For example, timestamps on their own can't generally provide a total order over events because two events may be measured to have happened at the same time.  Adding a counter gives you a way of consistently ordering such simultaneous events—even an arbitrary order (that does not reflect reality in any sense) is often useful if all parties agree on it.

If we're talking about replay in particular, if you authenticate the timestamps as associated data and reject data that's tagged too far in the past, you often cut many of the attacker's options, which is generally a plus.  But that however doesn't require you to use the timestamp as a nonce for an encryption algorithm, but rather as associated data for authentication.


There is no sensible solution to this.  It is impossible, even if this was not a hypothetical question.  It cannot be done for primarily two reasons:-

You cannot have the nodes measure any analogue quantity.  Analogue measurement noise will govern the accuracy of the reading.  Coupled with the typical hash based randomness extractors, the avalanche effect will guarantee that every node will generate a different random number.
So you're left with digital entropy acquisition.  Lottery results are good but there's not a lot of them to get the few bits /hr (maybe just - you'd have to do the math).  This was done for the Million Dollar elliptical curve. Much larger quantities of digital randomness can be obtained from international market information acquired via the appropriate APIs.  This will gradually fail though.  Spotty developers will change the access APIs every 18 months.  The nodes will gradually lose access to the digital entropy.    This gradual degradation of sources will affect the nodes no matter what sources they use.  The API degradation issue would also affect the lottery technique. And.  You can't update the nodes as that would put them under singular control breaking your initial premise.

The only kinda solution (breaking many requirements) is to use a distribution network sending out randomness like the NIST Randomness Beacon.  But it would have to be under international /UN control and inspection and outside of US jurisdiction.  It can't be NIST itself as that is a politically controlled arm of government (US Department of Commerce.)  Or do the same for updating the nodes with new market access APIs.  If the nodes were open hardware /open source based and not sealed, it would then be possible for hackers /scientists and journalists to verify their on going correct function.  But that would then allow prediction of the random numbers as the entropy and algorithm would be known.


Construct PRF with longer output from existing PRF

The $G$ that you have defined is not a PRF at all. I can distinguish it from random in just two queries. Since I have a feeling that this is homework (correct me if I'm wrong), I'll let you work out how it can be broken.


Does SHA-1 meet the strict avalanche criterion?

There is a paper "SHA-1 and the Strict Avalanche Criterion."

From the abstract:

  This work provides a working definition of the SAC, describes an experimental methodology that can be used to statistically evaluate whether a cryptographic hash meets the SAC, and uses this to investigate the degree to which compression function of the SHA-1 hash meets the SAC. The results (P<0.01) are heartening: SHA-1 closely tracks the SAC after the first 24 rounds, and demonstrates excellent properties of confusion and diffusion throughout.


Why this complexity defining AES-GCM counter block?

AES-GCM counter block is defined as nonce || IV || counter

That is not true.  AES-GCM effectively has two different versions.  If you have a 96 bit nonce, then the counter block is (by your terminology) $$nonce || counter$$

However, if the nonce is any other size, it computes a temp value $J = GHASH(K, Nonce)$, and then makes the counter block

$$J \boxplus counter$$

(where $\boxplus$ is addition which ignores the carry from bit 31 to bit 32).

As $J$ is effectively a random number, this second possibility is mostly what you are suggesting.

Now, it has since been found to have inferior security properties compared to the first idea (the proof had a flaw), so I don't suggest you actually use it


Semantic security and indistinguishability

You could use Format Preserving Encryption for either one of the elements. FPE will create a keyed permuation for a specific domain (presuming that this domain can be practically converted to a number representation). That way your identifier can just be a sequential number.

You could see a block cipher as an FPE for a specific domain with $2^n$ elements, where $n$ is the block size in bits. If you can define your domain to have that many elements (even unused ones) then yes, you could use a block cipher. This could be an issue if you cannot handle a relatively large output size (you cannot store $2^{32}$ bits or more, for instance).

You can also create a random nonce, but due to the birthday problem, you will have to generate a pretty large value to avoid collisions in the element itself (and, of course, the encrypted element as well).


I don't believe you're really asking 'why did they select an SBox with 0 being mapped to something other than 0"; essentially, that's what the designers picked.

Instead, it is "why does $S(0) \ne 0$ prove that S is nonlinear".

And, the answer to that is, yes, it does, but only pedantically.

A function $S$ is linear if $S(a) + S(b) = S(a + b)$ for every $a, b$ (and some reasonable addition function "+", generally, we use bitwise xor).  (And, this isn't quite sufficient if the range of $S$ is infinite, we never have to worry about that in crypto).

Now, if we select $a = b = 0$, this simplifies to $S(0) + S(0) = S(0+0) = S(0)$; or $S(0) = 0$.

Hence, if $S(0) \ne 0$, we know that the definition of linearity doesn't hold in all cases.

On the other hand, in crypto, when we talk about linear functions, we often really mean affine; the definition of this is $S(a) + S(b) = S(a + b) + c$, for all $a, b$ and some constant $c$ (which is independent of $a, b)$.  The reason we're interested in this is that essentially all the mathematical tools an attacker can use against a linear function also work against an affine one, and so we tend not to make a strong distinction.

And, just looking at $S(0)$ won't tell you if a function is affine, as we have $S(0) = c$, and $c$ can be any value.  If + is bitwise xor, you need to examine at least 4 values to prove that an Sbox is not affine.


Wikipedia pseudo code is unclear about how to pad SHA-512

Richie is of course correct; the padding needs to be done to form a final block that can also contain the length. As the length encoding is itself static in size, there is no need to pad the length itself.

This is the same as SHA-1 except that the size of the various elements (block size, length encoding) differs.


Is this zero knowledge protocol for honest verifiers?

Can you give me some hints?

It's not a proof of knowledge, as someone without knowledge of $x$ can complete this protocol successfully with an honest verifier.
Hint: what happens if the ignorant prover sends $y = h^{-1}$?


State of the art in zero knowledge proof compilers?

A protocol for double discrete log proofs is given in M. Stadler, "Publicly verifiable secret sharing", Eurocrypt '96, Section 3.3.

In Stadler's notation, given $g$, $y$, and $V = g^{y^\alpha}$, and $A = h^\alpha$ for some generator $h$, Stadler's protocol shows how to prove that $\log_h A = \log_y(\log_g V)$. Now, to solve your problem, let $V$, $g$, and $y$ be known. To prove knowledge of $\alpha$, have the verifier choose a generator $h$. The prover provides $A = h^\alpha$ and uses Stadler's protocol to prove that $\log_h A = \log_y(\log_g V)$.


Using SHA-256 with different initial hash value

With the message padding scheme of SHA-2/SHA-256 as it stands (add one 1 bit, a minimal number of 0 bits so that the overall padded message will end on a block boundary, then the original message length over some fixed number of bits), I know no attack enabled by allowing a different IV.

However, allowing an arbitrary IV renders ineffective one of the two redundant safeguards built into SHA-2's padding scheme. If the message length was removed from the above padding scheme, then an adversary having the ability to decide the different IV could do so nefariously; in particular, such that he knows a secret backdoor block $B$ that can be inserted at the beginning of any message, leaving the hash invariant. Proof: one round of SHA-2 transforms the state $S$ according to $S_{j+1}=F(M_j,S_j)\hat+S_j$, where $F$ is a cipher with the (padded) message block $M_j$ used as key, $\hat+$ is addition with some carries suppressed, and $S_0$ is the IV we are discussing. One able to choose the IV could choose it as $F^{-1}(B,0)$, thus such that $F(B,\mathtt{IV})=0$, thus such that $M_0=B\implies S_1=S_0$.


You have to be a bit careful here, I think.

The SWIFFT hash function is linear and does not behave like a random oracle. It is second pre-image resistant in an asymptotic sense. The fact that this property seems to depend on "a relatively mild assumption about the worst-case difficulty of finding short vectors in cyclic/ideal lattices" would seem to suggest (subject to verification) it might be post quantum secure (like NTRU which is also based on cyclic/ideal lattices).

However, the SWIFFT function is defined for fixed input length. Hence it cannot be directly used as a one way hash function for arbitrary length inputs, maybe it could be a building block for a post quantum secure one way hash function, I am not sure.


Do Cryptographic Hashing Algorithms operate only on Integers?

Mostly yes: usual cryptographic operations, including hashes, are defined using operations on integers and bit vectors, not Floating Point Numbers.

I think the  main reason is that in cryptography, we need different computers (e.g. the one that hashes a file to protect its integrity, and the one that verifies the integrity) to get the exact same result, and that is hard to ascertain for Floating Point operations.

Historically, computers used different format and precision for representing Floating Point numbers, and that would cause huge portability problems.

Nowadays virtually every recent CPU with FP support (which is only a tiny fraction of the CPUs manufactured) can use at least one of the 32-bit, 64-bit or 128-bit format of IEEE 754, so this is slightly less a concern than it was. But still, many computer languages and dialects give no way to precisely control rounding, or to efficiently convert arbitrary information as found in a generic file into FP format and back. It remains a mess to even get exactly the same result for FP addition on two machines programmed in different languages. Further, I would not bet that the same program using 128-bit arithmetic allays gives the same result on two different x86 PCs with built-in FPU when even multiplication is involved, much less division (maybe some designs differ by one LSbit in some edge case). Notoriously the result for transcendentals (e.g. $\sin$) differ.

There are a few uses of FP in the implementation of some cryptographic algorithms, or even hashes. I have seen an implementation of MD5 using 80-bit FP for accumulating the length of the input, to workaround the lack of 64-bit integer variables. It is not unusual that an implementation of multiple-precison integer arithmetic uses FP, more or less extensively.

An example where FP is put to heavy use in something reminiscent of a hash is Poly1305-AES for generic computers with IEEE floating point; that's a message authentication code which can be turned into a hash by making the key a public constant. Notice the caveat that it will not work on x86 computers running Linux, because GCC (at least, historically) did not support the required FP format.


Are all public-key encryption protocols based on one-way functions?

Yes, all public-key cryptography based on one-way functions. Every one-way function builds on some hard problem. There is many one-way functions in lattice-based crypto, that based on SVP. For example, NTRU one-way function, LWE one-way function, etc.


What are the methods to construct a primitive binary nonlinear feedback shift register (NLFSR)?

Update: A general method is given by Elena Dubrova: A Scalable Method for Constructing Galois NLFSRs with Period $2^n-1$ using Cross-Join Pairs, in IEEE Transactions on Information Theory, Volume 59, Issue 1 (alternate link). It gives an extensive bibliography of earlier constructs.

These constructions reorder a small number of fragments of the output sequence of a maximum-length LFSR. It does not achieve (or aim at) cryptographic security: it remains trivial to reconstruct the state of the generator from its output, from any unbroken fragment of at least $n$ bits. With slightly more bits, it is possible even if details (like $n$ and the polynomial) are unknown, using an appropriate variant of the Berlekamp-Massey algorithm.

Other than tweaking a LFSR to reorder fragments of its output sequence, I know no general method to construct Non-Linear Feeback Shift Registers with $n$ bits and period $2^n-1$, beside basically trying one by simulating the NLFSR for that number of steps, with cost $O(2^n)$ when done naively.

Large speedups are possible depending on the construct; in particular, if it is possible to explicitly compute the states that could reach the original state within $s$ steps, and performs $s$ steps as fast as one step, we can save a factor of $s$. But still the cost of establishing that a NLFSR with $n$ bits is near-maximal-period would be, it seems, at least $O(2^{n/2})$ steps with $O(2^{n/2})$ memory. However it is clearly easy to go much further that $n=25$ bits. Caveat: this is out of my head, I have no reference to quote.

In practice, it seems open cryptography seldom use maximal-length NLFSR; they could however make some sense in a cascaded construct, similar to the Alternating Step Generator or Shrinking Generator.

Also: There is simple method to construct a NLFSR with period $2^n$ using a binary shift register of $n$ bits. We start from a maximal-length LFSR with period $2^n-1$ constructed from a degree $n$ primitive polynomial over $GF(2)$, and tweak it into a binary De Bruijn sequence by inserting a single $0$ bit at the point in the sequence where $n-1$ consecutive $0$ occur. For a LFSR implemented as a shift register with a feedback term the XOR of some state bits, that's simply adding an additional XOR term with the NOR of the $n-1$ bits in the shift register that are closest to the feedback term. As a bonus, we can now start the generator in any state, including all-zero. See this related answer for details. Of course, that's not cryptographically secure.


What is the proof that a hash output contains random binary numbers

Whilst the random oracle model(1) is the theoretical construct that should produce random 'looking' hash output, the scientific principle also requires that we test the hypothesis for proof.

So let us assume a simple set of inputs to the function. If the null hypothesis is that the output will appear random(2), the output will have certain testable properties:-

For a simple counter input, we expect that any output bit will all uniformly distributed with $P(X = 0, X = 1) = \frac{1}{2}$, and for multiple conditional bits, $P(X | Y) = \frac{1}{2}$. These formulae extend as $P(\dots)= \frac{1}{2^n}$  and $P(\dots|\dots)= \frac{1}{2^n}$  for $n$ bit tuples.
For randomly entered bits, we can count the numbers of set input and output bits and determine whether an avalanche effect is occurring. We expect that 50% of the bits will change per any random input. The actual probability mass function of the changes is expected to be Binomial, tending to a Normal probability  distribution as the block width $(n)$ increases. We'd expect $\mu = 0.5n, \sigma = 0.5 \sqrt{n}$.
Standardised randomness testing (Diehard, NIST etc.) can also be used, and we expect SHA-512 to pass all of them whilst hashing simple inputs. There is also no specialised distinguisher and can separate the hash output from a pseudo random sequence (3).

This 'random' hypothesis has so far held in the laboratory. So in your parlance, the output is random, and no one has yet proved otherwise. Some of these experiments might have shown it up otherwise, depending on the degree of bias.

Notes.

(1) A very imperfect model, as explained here.

(2) By random output, I take it you mean independent and identically distributed bits, not easily related to the input, or each other.

(3) Just be aware that these lab tests cannot determine any form of security measure.


Elaborate their claims / point me to some source where I can get an overview of the concepts to eradicate my suspicion

This answer will focus on this part of the question: elaborating on the listed claims.

  All data is encrypted, including Entry names, Category definitions and the data itself.

As long as that doesn't impede functionality such as retrieving information from the database then it should be fine.

  Encrypts data using AES and Blowfish algorithms with key sizes of 256, 192 and 128 bits.

I am hoping/presuming this means it provides the option of these key sizes, and not that it uses AES-256, AES-192, and AES-128 to encrypt each block of data. That would be a very bad sign if it did, not for cryptographic vulnerability reasons, but more so because it would imply the author doesn't understand what they're doing.

There is no benefit from using Blowfish. Even the author of Blowfish thinks that people should stop using Blowfish.

There might be complications due to Blowfish having a small block size, but without knowing exactly what is being done such as what order the ciphers are applied in, it's hard to know.

  When the data file is decrypted, up to all combinations of algorithm, key size and cipher mode of operation (CBC, CFB, OFB and ECB) are tried with the Master password to unlock the data file. This makes brute force attacks longer. The app itself does not store any hint to the actual cipher, key size or cipher mode of operation.

This is simply a waste of the users time and the devices battery, assuming that the cipher, key size, and mode of operation are secure. This is not a good sign, and is trying to provide security by obscurity.

If there are only 4 modes of operation - none of which provide authentication - and they are selected at random, then guessing the mode of operation provides a maximum of 2 bits of security.

If there are only two cipher choices - AES and Blowfish - and it is randomly selected for each cryptogram, then it provides an additional 1 bit of security.

If there are only 3 key sizes - 128, 192, and 256 bits - and it is randomly selected for each cryptogram, then it provides an additional 1.5 bits of security.

Assuming these are all invoked with random choices for each cryptogram, then it provides a maximum of 4.5 bits of extra security.

The correct way to slow down brute force would be to use a significant number of iterations with the key derivation function that is applied to the password.

Note that using ECB mode at all is a big red flag.

  Uses a randomly generated 'salt' combined with the Master password. Salt helps to protect from off-line dictionary attacks.

This is good. However, using a 512-bit salt is twice as large as it needs to be.

  The key to open the data file is created by combining your master password with the 512-bit 'salt'. The result is hashed 1000 times by SHA-256. Repetitive hashing makes a brute force attack more difficult.

1000 iterations of SHA-256 is not sufficient, and provides only a meager improvement in security. The design of SHA-256 does nothing to prevent an attacker from using GPUs/FPGAs/ASICs to compute obscene numbers of password guesses per second (on the order of billions).

Ideally, an actual key derivation function such as PBKDF2, scrypt, or Argon2 would be used with a much larger iteration count (100,000-1,000,000) and set to consume as much memory as is possible/tolerable in order to drive up the cost of custom hardware and reduce an attackers advantage as much as possible.

Maybe users don't want to burn up battery with 100,000 iterations - However, in that case the iteration count should be configurable with a reasonably secure default. 1,000 iterations of SHA-256 is not a reasonably secure default.

Lack of Authentication

The descriptions do not mention anything about authenticated encryption. The lack of authentication implies that an adversary can modify ciphertexts and the user will have no way of detecting the modification.

Not providing authenticated encryption is a huge red flag.

Conclusion

All these points considered imply that the author of the software in question does not fully understand what they are doing. You should strongly consider finding an app that is more heavily vetted and was written by more knowledgeable people. Some of the flaws are quite serious that could lead to compromise of users data in the real world.


Using a Non-Random IV with modes other than CBC

Each mode of operation has its own IV requirements. Some need uniform, unpredictable randomness. Other are equally happy with just uniqueness.

CBC is well-known for its need of an IV chosen randomly and uniformly among the possible IV values, and such that an attacker who can choose the text to encrypt may not predict the IV value before submitting the said text.

PCBC is similar to CBC in that respect. When encrypting, PCBC is equivalent to applying a linear transformation on the input data, followed by CBC encryption. So PCBC also needs a uniform unpredictable IV.

CFB and OFB require only uniqueness: for a given key, each IV value shall be used at most once. The is no need for unpredictability or uniformness because the IV is first encrypted "as is" (before any operation with the plaintext) and encryption of a sequence of values with a good block cipher, using a key that the attacker does not know, is a good PRNG. This means that CFB and OFB somehow include what it takes to elevate a unique IV to appropriate uniform randomness.

CTR is somewhat similar to OFB. CTR encrypts the successive values of a counter, and the IV is the initial value for the counter. Security is achieved as long as no counter value is ever used twice with the same key. Hence, using CTR "burns" a range of consecutive values, beginning with the IV; none of these values shall be used afterwards as IV.

Note that OFB also generates a pseudo-random stream, and using as IV one of the block cipher outputs in a previously generated stream means that you regenerate the same stream from that point. So OFB also "burns" a bunch of values. However, these values are uniformly distributed in the set of block values, and not numerically consecutive as with CTR. The consequence is that a +1 policy on IV management (you emit several messages, each encrypted separately but with the same key, and simply increment an internal counter to get the next IV) is acceptable for OFB mode -- but not acceptable at all with CTR.

Remember the bit about CFB and OFB including their own PRNG ? The idea has been reused. Many modern block cipher modes, especially those which include checked integrity such as EAX or GCM, do the same kind of trick, and only require uniqueness.

Uniqueness and randomness are two distinct properties. Randomness is hard to get in some context; most desktop machines and servers manage to maintain an acceptable source of randomness (/dev/urandom, CryptGenRandom()... the name depends on the OS), but many embedded systems cannot. On the other hand, uniqueness is not totally free either: it needs some kind of memory, which resists across reboots. Using the current time as IV is tempting but delicate, unless you can guarantee a monotonous clock (otherwise, an attacker could reset the clock to trigger IV reuse).

However, appropriate cryptographically strong randomness yields uniqueness "for free" with overwhelming probability (if the block size is large enough, but you want to use 128-bit blocks for other reasons anyway). Therefore, if you have a strong PRNG on hand, you can use it to produce your IV for all modes.


How to prove knowledge of discrete logarithm in a product?

$$(x,r) = g^x h^r$$
$$C = (x,r)^ \mu$$

Now you have two standard proofs of knowledge.


Sigma protocol for AND-composition involving the same secret

Proving this statement for groups $G_1, G_2$ of different order is a bit tricky. If the groups are of the same order, one can simply use EQ-composition (see [4], which are the lecture notes corresponding to reference [3] above).

For groups of different prime orders $p_1, p_2$, a simple $\Sigma$-protocol runs as follows. Let $n=p_1 p_2$.

Prover sends announcement $(a_1,a_2)$, where $a_1=g_1^u$ and $a_2=g_2^u g_3^v$ with $u\in_R\mathbb{Z}_n$ and $v\in_R\mathbb{Z}_{p_2}$.
Verifier sends challenge $c\in_R\mathbb{Z}_{\min(p_1,p_2)}$.
Prover sends response $(r_1,r_2)$, where $r_1=u+c\,r \bmod n$ and $r_2=v+c\,m \bmod p_2$. Verifier accepts if $g_1^{r_1} = a_1 C_1^c$ and $g_2^{r_1} g_3^{r_2} = a_2 C_2^c$.

To show special soundness, consider accepting conversations $(a_1,a_2;c;r_1,r_2)$ and $(a_1,a_2;c';r'_1,r'_2)$ that share the same announcement $(a_1,a_2)$, but have distinct challenges $c\neq c'$. Hence, we have:
$$g_1^{r_1} = a_1 C_1^c,\quad g_2^{r_1} g_3^{r_2} = a_2 C_2^c,\qquad g_1^{r'_1} = a_1 C_1^{c'},\quad g_2^{r'_1} g_3^{r'_2} = a_2 C_2^{c'}.$$
Dividing these onto each other leads to:
$$C_1 = g_1^{\frac{r_1-r'_1}{c-c'}}, \qquad C_2 = g_2^{\frac{r_1-r'_1}{c-c'}} g_3^{\frac{r_2-r'_2}{c-c'}}.$$
The witness is extracted by setting $r=(r_1-r'_1)/(c-c')\bmod n$ and $m=(r_2-r'_2)/(c-c')\bmod p_2$.

Note that the statement has to be interpreted with care: the values of $r\bmod p_1$ and $r\bmod p_2$ will in general not be equal, so the actual numbers appearing in the exponents of $g_1$ and $g_2$ may be very different from each other!

[4] https://www.win.tue.nl/~berry/CryptographicProtocols/LectureNotes.pdf


Why is Poly1305, which is based on AES, faster than AES?

Poly1305 is not based on AES, it was used together with AES in Bernstein's first description http://cr.yp.to/mac/poly1305-20050329.pdf. For pseudocode of the Poly1305 algorithm see e.g. https://tools.ietf.org/html/rfc7539#section-2.5.1.

GHASH is the 'hash function' in AES/GCM.

So if Poly1305 is faster than GHASH on some hardware this is no contradiction. And note that the peek values on your linked site are comparable: Poly1305 1730.92MB/s, GHASH 1740.96 MB/s.


Is it possible to truncate AES output and keep uniqueness (no decryption needed)?

For the parameters you gave, the birthday paradox will kick in and you will get collisions, since the set of integers you want to process is much larger than $\sqrt{2^{30}}$.

A very simple countermeasure would be for input $x_k$ to use bits $(y_{k,1}\ldots,y_{k,30})$ of the AES output
$$
(y_{k,1}\ldots,y_{k,128}):=AES_K(x_k)
$$
(for a fixed randomly chosen secret key $K$, you can use some fixed padding on $x$ if you wish).

Say you you have processed $x_1,x_2,\ldots,x_m$ with no collision and placed the outputs
$$
(y_{1,1}\ldots,y_{1,30}),\ldots, (y_{m,1}\ldots,y_{m,30}),
$$
in a sorted list. Say $(y_{m+1,1}\ldots,y_{m+1,30})$
collides with a previously chosen output vector. Then keep checking
$$
(y_{m+1,j},\ldots,y_{m+1,j+29}),\quad j\geq 2,
$$
until you get a 30 bit pattern that doesn't collide with that vector. Due to the good randomness properties of AES this will succeed in a few iterations after each collision, with high probability.

You can then store the cordinate index  $j_x$  used to generate this vector together  with $x_{m+1}$ if reproducibility is required.


Pseudorandom permutations on domains of arbitrary (i.e. not a power of 2) size

Yes. This is called format-preserving encryption.

The most flexible algorithm is FFX, which uses a Feistel network with AES-based round-functions, but performs addition modulo $m$. For certain values of $m$, the range of the round function is extended in order to limit statistical biases to negligible values.

When $m$ is very small, this approach isn't that great because its provable security gaurantees start to vanish if the adversary can see around $\sqrt{m}$ queries. If this is a concern, you can look at slower but more secure algorithms like Sometimes-Recurse Shuffling.


Why are LFSRs represented as polynomials?

why are LFSRs represented as polynomials?

Because it gives useful insights into the behavior of the LFSR.
If the feedback terms are represented by the polynomial $P$, and if the initial state of the LFSR is represented by the polynomial $Q$, then the state of the LFSR after $n$ steps will be the polynomial $x^n Q \bmod P$ (where the calculation is done on polynomials, and not on the underlying field - algebra on polynomials is not difficult, however it is different than what you may be used to).
Why is this a useful insight?  Because we can determine the long-term behavior from this observation.  For one, we have $x^n Q \bmod P = (x^n \bmod P) \times Q \bmod P$; assuming that the constant term of $P$ is relatively prime to the field characteristic, then $x^n \bmod P = 1$ for some $n$, and so the LFSR will eventually return to its initial state (and not fall into an intermediate-state loop).
Furthermore, we can deduce that, as long as $Q$ is relatively prime to $P$, then the number of steps that the LFSR will take before it returns to the original step is independent of the actual setting of $Q$.
Thirdly, if $P$ is an "irreducible polynomial", that is, if there do not exist polynomials $R, S$ with degree > 0 s.t. $P = R \times S$, then the amount of time taken before the LFSR returns to its initial state will be a factor of $p^k$, where $p$ is the size of the field used (2 if we're doing out LFSR in a binary field) and $k$ is the degree of $P$.
These observations (except for the first) are not obvious from the abstract definition of an LFSR.
And your final question:

What is the final constant in the polynomial?

It's just another feedback term from the LFSR.  The LFSR can be represented in 'Fibonacci' or 'Galois' modes (and the above abstraction works for both, so it doesn't matter which for the above discussion).  In the 'Fibonacci' mode (which appears to be what you are asking about), this constant term corresponds to the sum of the feedback terms that is used to generate the new bit within the LFSR.


The unicity distance is defined to be the minimum number of ciphertext characters needed to have a unique significant decryption.
It answers the question 'if we try all the keys, how much ciphertext would we need to be sure our solution was the true solution?'.
The answer depends on the redundancy of the language in which the plaintext was written.

To find the unicity distance of a given cipher algorithm you calculate the ratio of the number of bits required to express the key divided by the redundacy of the language in question. Assuming the plaintext was written in English and that the Playfair Cipher is used to encipher it, we have that the unicity distance equals to 27 characters.

For a slightly more detailed discussion consider practicalcryptography.com


If CPA-security is sufficient, then CTR is sufficient. If you need authenticated encryption (or CCA), then neither XEX/XTS nor CTR is sufficient and you should be using AES-GCM or something similar. In general, as soon as you want something that is "less malleable" then you consider malleability a threat and you should be using authenticated encryption. If you are worried about nonce misuse resistance, then likewise you should be using such a scheme (SIV or GCM-SIV, etc.).

There is just no good reason to use XEX/XTS, except when you have a severe limitation like in disk encryption that you cannot increase the sector size.


Python. RSA common modulus attack problem

I have solved this problem. @fgrieu  was right! Thanks for him and other!

Calculating modular inverse

if a < 0:
    _, eM1, __ = gmpy2.gcdext(eM1, N)
elif b < 0:
    _, eM2, __ = gmpy2.gcdext(eM2, N)

Calculating source message M

M1 = pow(eM1, abs(a), N) #I just realized, that always i need to use modulus pow(a,b,n)
M2 = pow(eM2, abs(b), N) #In this way all calculations are really fast!
M = (M1 * M2) % N # And final multiplication uses modulus same as previous expression


Is it generally okay to substitute “like for like”?

Broadly speaking, the answer is yes IF the protocol was designed to be modular and not depend on any particular properties of the underlying algorithms.

If the protocol has a proof of security that abstracts the underlying primitives (i.e. if the theorem statement contains a phrase like "Let $blah$ be an AEAD scheme" and the proof contains a reduction to the AEAD security of $blah$) that proof should still more or less hold. If there is no proof of security you have two options: (a) write one and make sure the reduction goes through or (b) just make an educated guess. I recommend (a).

Some details, in particular exact security bounds, may change slightly when different primitives are used. For example, AES-GCM has a relatively low authenticity bound compared to something like AES-CTR-HMAC-SHA256. This really only matters if you're planning on encrypting huge numbers of very large messages with the same key, but it's worth checking nonetheless.

Standard caveats about side-channels and things like that apply, obviously.

EDIT: Just saw your question asks about hash functions too. Hash functions are sometimes trickier to reason about, especially if the random oracle model is involved. If the protocol is just reducing to the collision-resistance of the hash function, swapping one good hash function for another is probably fine. However, if the hash function is being used to instantiate a random oracle, you need to make sure the hash function you want to swap in is indifferentiable from a random oracle. So, for example, it's not ok in general to use SHA256 in place of SHA3, because the former is not indifferentiable from a random oracle.


Mechanism of PBKDF in encryption key generation with passphrase

The salt is indeed randomly generated. If the salt is random then it becomes impossible to pre-calculate the hash, thus making it impossible to build a lookup table hash -> password called a rainbow table. The salt only has to be unpredictable and unique, so the amount of security relying on the salt to be unique is relatively small.

Once the salt is known it is stored so that the password derivation is otherwise deterministic. This lets you regenerate the same hash for the same salt & password combination (and the same work factor or iteration count).

Key stretching (or rather, key strengthening) may need to be used within PBKDF's because the input key material is generally not strong enough to be used as a key. A password commonly has only around 50 bits of security or so. Key strengthening can add a few bits of security if the password isn't strong enough. This adds an amount of of work to an adversary per password tested.

Key strengthening makes it infeasible to perform a dictionary attack against a large amount of hashes in a database, as each password / salt combination should be tested, and each test would be a relatively large amount of work. This comes at a cost of course: each time the password hash is generated the work factor is also incurred on the user.

Note that the output size of the resulting key doesn't increase the amount of randomness of the input keying material. So just outputting a larger amount of bits won't increase the security. Outputting a 128 or 256 bit AES key won't increase the security if the input keying material has a lot less entropy than the input key.

A password should not correspond to a unique hash. A password / salt combination should, for a given password hash and work factor, correspond to a certain hash.

Otherwise you or anybody else could be using the same password for different purposes, and the calculated hash would be identical at the different locations. This leaks information about the password, possibly even leading to compromise of the hash, for instance if somebody would use the same password and finds out that the hash is repeated elsewhere.


How many messages before Sphincs(+) becomes insecure?

For all SPHINCS-like constructions, security is slightly more complicated to analyze than for say a hash function. For SPHINCS we do not only have two dimensions as for hash functions where we got the effort an attacker spends and the corresponding probability. For SPHINCS there is a third dimension, namely an 'attack effort' - 'probability' pair occurs only with a certain probability. This latter probability slowly increases with every signature an adversary sees. However, parameters are selected such that the probability that an 'attack effort' - 'probability' pair occurs times the inverse of the effort needed to achieve probability 1/2 under this pair is below a targeted value (this is what is considered the full attack complexity). E.g., for SPHINCS-256 this target value is $2^{128}$ considering quantum adversaries. This is not entirely true, as I said that the probability of occurrence increases with each signature. Hence, for every target value, there is a threshold for which it will be passed. Therefore one has to decide for how many signatures that target must not be passed. For SPHINCS-256 the target holds for $q = 2^{50}$ signatures. For SPHINCS+ the target holds for $q = 2^{64}$ signatures. If a user does more than $q$ signatures the attack complexity starts to decrease. Actually, the SPHINCS and SPHINCS+ specification/paper give formulas for the bit-security. You can answer your question yourself as follows:

In the case of SPHINCS-like constructions, a bit security of $b$ bits corresponds approximately to a success probability of $2^{-b}$. Just fix $b$ accordingly and solve for the number of signatures $q_{sign}$ in the formula.


Can we prove possession of an AES-256 key without showing it?

Yes she can. She would do so by relying on a boolean circuit that takes $K$ as input, uses it to encrypt the plaintext $X$, compares it to $Y$, and outputs $1$ if and only if the comparison succeeds. Given such a boolean circuit $C$ (that both parties can construct), Alice must prove that she knows an input $K$ to $C$ so that $C(K) = 1$.

The task of proving knowledge of a witness for a relation described by a boolean circuit (in zero-knowledge, hence without leaking any information about the witness) has been studied a lot in the cryptographic community. Several protocols exist for this task, Zkboo is one example. It has three moves, and is based on the MPC-in-the-head technique introduced in this seminal paper.

Other solutions (see also this paper and the related but somewhat different solution presented in this paper) achieve a comparable efficiency, and are based on garbled circuits: Alice will hand Bob a "garbling" of $C$, which takes as input an encoding of her witness $K$, and evaluates the circuit on $K$ in a hidden way, and outputs $C(K)$ (the details are quite technical, so I'll stick to this high level explanation unless you want a deeper overview of how it works).

EDIT: corrected the statement that Zkboo was based on garbled circuit, I had confused it with another paper, thanks to redplum for pointing this out.


Tests to distinguish between PRNG and a CSPRNG

What are the tests which a regular PRNG would fail but a CSPRNG would succeed?

The goal of a PRNG, and the duty of a CSPRNG, is to have an output that can't be distinguished from true randomness (with a significant advantage, by a program that can actually be run). Thus it's a failure of a PRNG, and a capital offense for a CSPRNG, if it does not pass all randomness tests it receives (assumed correct and well used, including correctly interpreting the results, which by nature are uncertain to a degree).
Nevertheless, a few bad PRNGs which fail some generic statistical tests like Ent, Diehard, Dieharder, TestU01, NIST SP800-22 rev 1a. More PRNGs fail only specific tests designed with knowledge of the PRNG design.
A well-designed and well-implemented CSPRNG will, by definition, pass all tests. That's including the above list of tests. We can have a (faint) hope that running some tests in this list disprove that a PRNG is a CSPRNG.
Caveat: that's essentially useless to argue (much less, prove) that a PRNG is a CSPRNG (which requires analysis at the design) or well implemented (which require looking at the implementation, and test vectors). Much like analyzing statistics on winning a lottery is not useful to argue that this lottery system is run honestly.
Addition (as rightly suggested by @SEJPM): We can't stress it too much, don't count on generic statistical tests to find weaknesses in PRNGs, or worse CSPRNGs (rather, count on CSPRNGs to help debug statistical tests). A CSPRNGs requires a sound design, and years of analysis, of its design and/or of the primitive(s) it uses, by smart motivated cryptanalysts. Only after they failed to find a theoretical distingisher do we have a serious candidate CSPRNG.

Would a PRNG which is not a CSPRNG pass the Chi Square tests?

That depends on PRNG and test parameters (that might also depend on the seed used). For many non-crypto PRNGs in actual use, and all CSPRNGs, yes. For others, that depends a lot on if the test is run for a long enough sample, and on if the χ2 test is bidirectional or not.

Why do you need to know the PRNG Design?

In cryptography, adversaries are assumed to know everything about the system attacked except the key (that is, for a PRNG, the seed), by Kerckhoffs's principle. They will design clever algorithms, perhaps dedicated hardware (e.g. the bombe), in order to break the system (that is, for a PRNG, distinguish the output from random, or worse predict future output from past output).
And in practice, that makes a helluva of a difference. It's easy to devise a test that predicts the next outputs of MT19937 knowing earlier ≈19968 bits, using a specifically designed test for that generator. Most tests not specifically designed for the class of generators MT19937 belongs to will give its output a clean bill of health.

Why can't the next-bit test be used to distinguish a CSPRNG from a PRNG without knowledge of the PRNG design?

The next bit test is theoretical. Unlike the 5 families of statistical tests I linked to, it's not a program that can be run to completion on a sample of the output(s) of the PRNG tested.
No practical test on the output of a candidate CSPRNG can confirm it's one.


A problem in secret sharing and mixed operators over $\mathbb{Z}$

I'll consider that 2's complement is used for negative numbers in $\Bbb Z$, or that $A\ge B\ge0$. Even with such provision, the question's claim is too imprecise to be settled:

  having $(A-B)\oplus C$ and $B\oplus C$, we cannot find $A$

Fact is, what we learn about $A$ from $(A-B)\oplus C$ and $B\oplus C$ depends heavily on $D=(A-B)\oplus B$, which we can compute from the givens as $D=((A-B)\oplus C)\oplus(B\oplus C)$ (and this reduction of the two givens to the single $D$ did not change what we can learn from $A$, if nothing was known from $C$ we eliminated).

That information we get on $A$ from $D=(A-B)\oplus B$ varies from

the low-order bit of $A$, which always matches the low-order bit of $D$;
to (at least) the low-order $k$ bits of $A$: we can prove by induction that for any integer $k$, $D\equiv-1\pmod{2^k}\implies A\equiv-1\pmod{2^k}$;
or even the whole of $A$: using 2's complement, when $D=-1$, $A$ can only be $-1$ and $B$ can take any value.

A true statement could be: for random choice of the low-order $k$ bits of $A$, $B$ and $C$, probability that we can determine with certainty the low-order $k$ bits of $A$ from $(A-B)\oplus C$ and $B\oplus C$ decrease as $O(2^{-k})$.


Create a TOTP for machines using HMAC or AES

Be reassured: both $\text{HMAC}(k,m)$ [instantiated with a strong hash function, e.g. SHA-512; even SHA-256 would do] and $\text{AES}(k,m)$ [understood as direct encryption of 128-bit $m$ with the block cipher] are believed to be computationally secure Message Authentication Codes for the foreseeable future when the key is 256-bit, irrespective of how many message/cryptogram pairs are available. Both can be truncated: 64-bit would be ample if the verifier limits the attack rate.
$\text{HMAC}$ has the security advantage of being less susceptible to cache-based side channel attacks than $\text{AES}(k,m)$ is, for implementations in software without AES-NI on CPUs with caches.
From a functional perspective, $\text{AES}(k,m)$ has the slight advantage that (if kept 128-bit) it conveys the timestamp $m$, which can be recovered by decryption. Otherwise  we may need to transfer or guess some low bit(s) of the timestamp to fix any drift there may be, especially at startup.
Whatever the MAC, one operational vulnerability is likely to be the establishment and storage of the long-term 256-bit key $k$. There might be other attacks on the protocol, which is not described.


$\newcommand{\AE}{\mathit{AE}}$
Let $\AE$ be an authenticated cipher (AES-GCM) and $E$ an unauthenticated cipher (AES-CBC).

Let $k_1$ and $k_2$ be independent uniform random.  Let $m$ be a message.  Let $c_1 = \AE_{k_1}(m)$ and $c_2 = E_{k_2}(c_1)$.  If the adversary knows $k_1$ and $c_2$, but not $k_2$ or $c_1$, can they learn anything about $m$?

The answer is no: the security of $\AE$ and the randomness in the initial choice of $k_1$ is irrelevant; if an adversary could learn anything about $m$ from the ciphertext $c_2$, that would violate the semantic security of $E_{k_1}$.

   In particular, if we had an algorithm $A(k_1, c_2)$ which returned $m$ with probability $\varepsilon$, we could use this as a ciphertext distinguisher for the cipher $E$ with advantage at least $\varepsilon$: pick a key $k_1$ uniformly at random, and submit challenge messages $m_0 = \AE_{k_1}(m)$ and any other $m_1 \ne m_0$; then, given a challenge ciphertext $c = E_{k_2}(m_b)$ for unknown $b$, run $A(k_1, c)$ and guess $b = 0$ if $A$ returns $m$, and $b = 1$ if not.

What if you re-encrypt the same messages with fresh independent keys?  Same deal.

There are operational issues to worry about too:

Is eavesdropping of $k_1$ and $c_2$ (and $k_3$ and $c_4$, etc.) the only power of the adversary, or can they forge and modify things too?
If the adversary can influence $c_1$, motivating the use of the authenticated cipher AES-GCM, can they influence $c_2$?  Naive use of AES-CBC may expose you to padding oracle attacks.
Rotating keys doesn't prevent an adversary from using old keys to decrypt old ciphertexts.  It only prevents them from using old keys to decrypt new ciphertexts or vice versa.  If the adversary ever records old ciphertexts, then any future disclosure of the old keys will reveal the plaintexts.
The narrow cryptographic question here—of whether $m \mapsto (k_1, E_{k_2}(\AE_{k_1}(m)))$ has semantic security or ciphertext indistinguishability—isn't affected by the additional details about key rotation.  But what is the bigger picture here—what resources do you have, what are you trying to do with them, what attack surfaces does the adversary have to exploit these resources, and what are you trying to prevent the adversary from doing?  Do you have a living design document setting all of this down?  This is bigger picture is where you should focus your efforts to make sure your whole design is sound before worrying about little cryptographic details.