What is different between a hash function and permutations with repeats

Are secure hash function outputs different from permutation sets of the same length and value?

Yes, almost certainly because both tend to produce randomized output, and it is unlikely that they will both end up with the same output for the same input message. In principle they may differ in size of course, SHA-224 output is hard to reproduce using a repetition of a 128 bit block cipher.

  If yes please explain how they appear differently.

Ah, now you're talking about appearance. Well, generally the output is randomized so they will be indistinguishable from each other. Of course, with a hash, if you can guess the input message then you can see if the hash value matches that. For block ciphers we generally assume that the adversary doesn't know the key, so that's not possible.

  A non standard permutation algorithm that is impossible to inverse without a key would appear to be the same and be just as secure.

Why would you use a "non standard permutation algorithm"? Remember Kerckhoff's principle! We generally use a keyed permutation which selects a permutation from a limited set of permutations. Assuming that it is reversible this is called a block cipher.

More importantly, now you are suddenly comparing security properties. So that's the third different comparison: comparing values, comparing appearance and comparing properties!

First of all, you seem to be basically compare a MAC and a non-keyed hash function. The MAC function is generally more secure for most situations, as an adversary cannot perform an offline search for collisions without the key.

Second, just repeating a specific permutation (e.g. twice 64 bits for a 128 bit output) is not a secure MAC. For starters, it doesn't provide compression, and moreover, it leaks information if the message is evenly split into two blocks with the same information. Similarly, these blocks may also be found in previous messages.


The main advantage I have heard is reducing the amount of data the client has to send to the cloud.

As said in A Comparison of the Homomorphic Encryption Schemes FV and YASHE:

  [...] ciphertext expansion (i.e. the ciphertext size divided by the
  plaintext size) of current FHE schemes is prohibitive (thousands to
  millions). For example using techniques in [CNT12] (for 72 bits of
  claimed security), sending 4MB of data on which the cloud is allowed
  to operate, would require to send more than 73TB of encrypted data
  over the network.

And to solve this issue, clients could encrypt their data with some block cipher instead of encrypting with a homomorphic encryption scheme.

Then, clients would just send their FHE public keys with the encrypted data.

On the other hand, the cloud would have to encrypt with the FHE scheme the ciphertexts received (using the clients' public key) and homomorphically decrypt them (running the block cipher's decryption function homomorphically) before they are processed.

Since block ciphers have very small ciphertext expansion, sending the data encrypted with AES (for instance) plus sending the public key means sending much less data then sending only the data encrypted with a FHE scheme.

This is also the application commented in Homomorphic Evaluation of the AES Circuit.


How does Twofish avoid weak keys if it uses key-dependent S-boxes?

The key to the answer lies within these two snippets:-

  These results
  help confirm our belief that, from a statistical standpoint,
  the Twofish S-box sets behave largely like a
  randomly chosen set of permutations.

and

  There should be few or no pairs of keys that
  define the same S-boxes. That is, changing
  even one bit of the key used to define an Sbox
  should always lead to a different S-box.
  In fact, these pairs of keys should lead to extremely
  different S-boxes.

Taken together, they describe an  quasi encryption/hash of the key  à la SEAL (but simpler). Perhaps akin to a  CRC calculation or a mini randomness extractor. Even prior to the MDS matrix. There's probably a better scientific term for it.

$q_0$ and $q_1$ are fairly good S boxes themselves. Even though they are random permutations, their arrangement has been numerically optimised for differential and linear characteristics of $ \frac{10}{256} $ and $ \frac{1}{16} $ respectively, and no more than two fixed points. Taken with the permuted arrangement in the three levels deep nested look ups of $q_0$ and $q_1$ within the definition of  $S_i$, it's extremely unlikely that you'd find pre-images that create all weak $S_i$. It's  difficult to algebraically define what a related key might look like for a given pre-image.  That's just a consequence of all nested look ups into   random permutations. The permuted nesting is highlighted below:-

Like you, the authors worried about weak keys too.  Hence a large § 7.2.3 Exhaustive and Statistical Analysis. Monte Carlo simulation seems to confirm their assumptions that weak keys are quite unlikely due to the pseudo permutation and avalanche behaviours. Your "very simple algebraic representation" doesn't occur due to the inherent randomness within $q_i$, where the shortest computational representation of $q_i$ is  $q_i$.


Public SRP verifiers or public hash chain "public keys" when secret is low entropy password

I know PBKDF2 is essentially "useless" against anyone with a GPU rig and I have read that bcrypt is "useless" to anyone with an FPGA setup.

Neither is useless. Newer alternatives like scrypt and the eventual PHC winner make better use of the defenders' resources, but even a thousand iterations of PBKDF2 is useful, compared to doing nothing.

If you assume that $2^{80}$ hash function invocations is infeasible for the attacker (reasonable, though not particularly conservative), then $2^n$ rounds of PBKDF2 allow your passwords to have only $80-n$ bits of entropy. Since $n=20$ is often reasonable, you would remove a fourth of the required password "length", all things equal.

  So, is there any solution to this set up or is this ultimately a case where a user must have some key-like password? If so, would this be a good use case for assigned passwords that are actually keys translated through word lists?

Still, typical user-chosen passwords certainly do not have even that much entropy, so yes, this could be a good case for assigned passwords. Even if the users are unwilling to remember the assigned password, writing it down would not let a typical eavesdropper attack it. Also, users cannot make the passwords they use elsewhere (in situations where offline attacks are prevented) vulnerable by reusing them here.

So, to answer your actual question:

  Is it reckless to use a key derivation algorithm to create a secure password to use with an auth scheme like SRP or hash-chaining in which the untrusted server and the general public will know the resulting verifier or "public" key? Or are KDFs only suited for providing some hope that not all passwords are goners for when a trusted server is broken into by an attacker?

No, I do not think it is necessarily reckless, at least with your idea of assigned passwords (which cannot cause a leak of some reused password). However, it would still be preferable to prevent such offline attacks in the absence of a compromise of the server. I.e. use a trusted server for authentication if at all possible.


Are these hash function compositions collision resistant?

Your first approach $H'(m) = H(H(m)) || H(m)$ will not have any improvement collision resistance. The reason being is that a collision in the right half automatically causes a collision in the left half, since the output of $H$ is identical for the colliding messages. The left half is not a function of the message, but of the message hash, the concatenation will have the same collision resistance as the hash itself, but take up twice the space and require an additional hash iteration, with no improvement in any security property

The second approach will also have identical collision resistance to $H$, but simply take up twice the space, with no improvement in any security property.


Shamir's secret sharing scheme - type of channels

For information theoretic security in Shamir's [m,m] secret sharing scheme, do i need both authentic and confidential channels?

Regular shamir secret sharing provides no protection against modified shares. So we typically assume an honest dealer with authentic and confidential channels. That means the adversary cannot change the message in transit. If a party that receives a share is dishonest, however, they can change the share and go undetected.

  is it true that if the channels are only authentic; then the Shamir's [m,m] secret sharing scheme is only computationally secure?

updated this part of the answer
It appears that without some very non-standard assumptions, using only authentic channels completely breaks the security of the system. While all shares are needed to recover the secret, and one share is kept by each party (not transmitted directly), a function of that share is transmitted which would allow the adversary to recover that share and break privacy.

  If confidential channels are build on the basis of public key schemes; then doesn't that make the entire protocol computationally secure?

Assuming the adversary can see the cipertexts, then yes, using a public key scheme (or any computationally secure cipher) to protect confidentiality results in computational security since an adversary breaking the cipher would result in them finding all the shares, thus breaking the secret sharing.


Do ciphers with a key size of 64 bits still have use under very limited attack models?

I believe that ciphers of low bitwidth still have a place for sensor data and likely, video game data.  Mainly, this is due to the nature of the data.  In the case of a sensor, cryptography generally buys you very little in the practical sense outside of verifying a message, and the same is true in video games.  Your data is "stale" in a matter of seconds, and as long as the scheme takes minutes to brute force, you are likely to be fine.

If you have access of AES-NI, or an equivalent instruction set, you will not be able to make anything faster.  Let's make the assumption that you are not worried about side-channel attacks, do not have cryptographic hardware on your CPU, and just are interested in speed.

I use SIMON in my embedded hardware, and SPECK in software when I cannot get something else to fit in the space.  SPECK is about as fast as you get on an IC without explicit cryptographic hardware.  The cryptographic community while give you a difficult time for these ciphers as the NSA created them, but I know of nothing better.   SPECK64/96 has 26 rounds, on a MIPS 32-bit MIPS core, it takes me 51 instructions (after I expand the keys) to encrypt the block.


Reverse engineering secret key in RSA encryption with the help of signature

In RSA, assuming knowledge of the public key but not the private key, analyzing any number of triplets of matching message, encrypted message, and signature $(m,M,sg)$, does not help (as far as we know) towards recovering the private key $s$ (nor an equivalent). That's regardless of the sensible padding or RSA variant used (as long as neither the padding nor choice of $m$, $M$, or $sg$ directly leak information about the private key, e.g. in some supposedly truly random padding field that really is not).

In fact, the stronger hypothesis that one with knowledge of the public key also temporarily can use a black box containing the private key $s=(N,d)$ that freely allows computing the raw RSA private key function $x\to x^d\bmod N$ for any $x$ (which in turn allows decrypting or signing any message), does not (as far as we know) help in any way towards finding a private key, nor factorizing $N$, nor otherwise building a black box independent of the original one computing the raw RSA private key function $x\to x^d\bmod N$ for random $x$ with sizable odds.

There is no proof of that; proving (or disproving) it is an open research problem.

Note: as pointed in another answer, access to a "frontend for the RSA implementation such that we can give it a message and it will return the encrypted message" demonstrably does not help, for it is possible to perform the same using the public key, with cost growing slower than $O(b^3)$. However, the question mentions that we are also given some signature, and we lack a proof that this does not help.

All the attacks on RSA that we know:

decipher or sign messages without finding a private key (only if improper use of RSA is made, e.g. poor encryption or signature padding);
or find a private key from the public key (typically, by computing a private exponent from the public exponent and the factors of the public modulus $N$, recovered by factorization, because $N$ was too small or its factors improperly chosen);
or extract the/a private key using some information leak.


The hints given refer to unbiasing algorithms, which is the standard answer in cryptography. However, there is a very nice and different solution for the example of generating the $(2/3,1/3)$ distributed bits from an unbiased stream which I will mention here. For clarity call the output symbols $a$ and $b$ with $p_a=2/3=1-p_b$ instead of using binary symbols
Expand the probabilities in base 2 to get:
$$
\frac{2}{3}=0.101010101010\ldots
$$
and
$$
\frac{1}{3}=0.0101010101\ldots
$$
which means these probability atoms have dyadic expansions
$$
\frac{2}{3}=\frac{1}{2}+\frac{1}{8}+\frac{1}{32}+\cdots=\frac{1/2}{1-{1/4}}
$$
and
$$
\frac{1}{3}=\frac{1}{4}+\frac{1}{16}+\frac{1}{64}+\cdots=\frac{1/4}{1-{1/4}}
$$
This decomposition yields the following infinite tree which generates the symbols required:

if the unbiased bit is 0 go left, otherwise go right, when an $a$ or $b$ is emitted start again;

(the first left branch should have the symbol $a$).

In Chapter 5 of Cover & Thomas' Elements of Information Theory book  it is proved that this procedure is optimal, i.e., it gives a tree of expected minimum length generating this distribution.
Edit: As in the comments by @supercat, if $p$ is unknown but the input bits are independent, one can group say $3-$tuples into two sets of desired probability ratio, and also try to maximize the probability that a bit is actually output.  $k=3$ is convenient for this case since the binomial coefficients $\binom{3}{j}$ are divisible by 3, if we ignore the first and last coefficient, so the grouping to obtain a $(1/3,2/3)$ probability [when symbols are output] becomes possible. Concretely

If you see 100 or 011, output $b$. If you see 010, 001, 101, or 110, output $a.$ If you see 000 or 111, throw out the bits and try again.


The OP wants a Key Derivation Function suitable for producing a key for the block cipher TEA, from Password and Salt. He is considering the use of PBKDF2, a common method designed for that purpose, which has a parameter controlling how slow the computation is, and thus the difficulty of password cracking.

PBKDF2 is a giant progress compared to practices such as MD5(Password||Salt) → Key (where || stands for concatenation), but it is significantly inferior to what state-of-the-art allows. See the following table from the paper Stronger Key Derivation via Sequential Memory-Hard Functions defining the Scrypt Password-Based Key Derivation Function.

In the following I discuss the PBKDF2 avenue envisioned by the OP; I might propose a simpler one, illustrating the concept of Sequential Memory-Hard Key Derivation Function, in a later post under preparation.

PBKDF2 requires a Pseudo-Random Function PRF(Key,Message) → Output with variable-length key and message inputs, and fixed-size output. The PRF commonly used is HMAC. HMAC in turn requires a hash function. In order for HMAC's original design rationale to hold, that hash must use the Merkle–Damgård construction, with a round function that is a One-Way Compression Function OWCF(Block,State) → NewState with fixed-size block input and state input/outputs. The simplest construction for an OWCF from a block cipher is the Davies-Meyer construction. In that context, one uses a block cipher with block size the hash's output size, and usually key input at least twice that. In the usual PBKDF2 with HMAC-SHA-1, the OWCF is build from a block cipher with 160-bit block size (the state in the OWCF) and 512-bit key (the block in the OWCF). TEA, with its 64-bit block and 128-bit key, is not a good direct fit for that block cipher.

Further, in that use, the block cipher should be resistant to related-key attacks, and in particular must not have equivalent keys, which trivially turn into collisions; these get up the chain into hash collisions, HMAC key and message collisions, PBKDF2 equivalent passwords and equivalent salts. TEA has equivalent keys (and lesser related-key vulnerabilities). In the context, using TEA as a block cipher in the Davies-Meyer construction, it would be easy to exhibit a class of equivalent passwords and equivalent salt (by toggling bit 7 of some bytes so as to reach equivalent keys in TEA), which shows that a sizable portion of the entropy in the input is lost (1/64 for random input). This would not be a total disaster in practice, but for a recommendable scheme along the above lines, we want to strengthen the cipher w.r.t. related-key attacks, and (as lesser need) double its block and key size.

One sound scheme to construct that 128-bit block, 256-bit key cipher DTEA is a 4-rounds symmetric Feistel cipher with TEA as the round function, using at each round a 128-bit sub-key, derived as two 64-bit halves, each obtained by a CBC-MAC of DTEA's 256-bit key, using CBC-MAC with TEA keyed by an arbitrary 128-bit constant. We need 8 such constants (2 per round), and a total of 36 TEA per DTEA. This is slow, but in the context slowness that can't be optimized out is no issue. The paranoid could even use D2TEA derived from DTEA the way DTEA is derived from TEA; that would raise the difficulty of exhibiting even two equivalent passwords or salts from about $2^{64}$ DTEA (hard but feasible) to $2^{128}$ D2TEA (infeasible in the predictable future).

Thus my answer to the question is: If you want to use PBKDF2 with TEA as the core function then

use TEA to construct a wider cipher DTEA better protected from related-key attacks, using the Feistel construction with sub-keys derived by CBC-MAC, as above;
use DTEA in the Davies-Meyer construction to build an OWCF;
use that OWCF in a Merkle–Damgård construction to build a hash function;
use HMAC to turn that hash into a PRF;
use that PRF in PBKDF2;
build salt as the the concatenation of context information (user or file name..) and if feasible 256 bits of true random (else use date and time to the best accuracy available);
generate the desired key as PBKDF2(Password, Salt, c, dkLen=16), with iteration count c set as high as practical.


TLS RSA Certificate with Elliptic Curve Negotiation

I found another link, as the purpose of this was to use both RSA and ECDSA for signing, but that, to my understanding, requires different public/private keys and therefore different certificates

See the following link https://security.stackexchange.com/questions/43360/is-possible-that-a-tls-server-send-more-than-one-certificate-to-the-client-for-t

  For signature algorithm support, there is a standard TLS extension
  specified in section 7.4.1.4.1, by which the client can tell to the
  server, early in the handshake (in the ClientHello, which is the very
  first message of the procedure), which hash functions and signature
  algorithms it supports. This allows a server who owns, for instance,
  both a RSA-signed certificate and an ECDSA-signed certificate, to send
  one or the other, depending on what the client supports. This is
  typical of how things go in TLS: the client suggests, the server
  chooses.

So it seems to support both ECC and RSA you HAVE to get the client supported algorithms early then play a 'trick' by swapping out the cert. It seems there is no way to just have it be based on the support list of ciphers where you can send multiple certs and have one be your RSA one and the other your ECC one.

EDIT

Here is another link https://security.stackexchange.com/questions/8343/what-key-exchange-mechanism-should-be-used-in-tls that confirms that the certificate and the key exchange and cert keys have to match up

  You may use a key exchange (as part of a cipher suite) only if the server key type and certificate match.


The definition and origin of Schnorr groups?

What (and where) is the actual definition of a Schnorr group?
  Where have Schnorr groups first been introduced and who called them Schnorr groups?

I don't know who first used the term—the earliest use I can dig up quickly is actually the Wikipedia article, initially drafted in November 2004 by Paul Crowley[1], who also used it a year earlier on sci.crypt[2].  What it means is a subgroup of prime order $q$ of the multiplicative group of the finite field $\mathbb Z/p\mathbb Z$, where $p$ is large enough (say 2048 bits) to resist index calculus on the field and $q$ is large enough (say 256 bits) to resist Pollard's $\rho$ or other generic discrete log attacks on the subgroup.

Cryptosystems defined in terms of Schnorr groups usually do not involve furnishing adversaries with oracles for $h \mapsto h^x$ for secret $x$, so minimizing $(p - 1)/q$ is not important as it is for, e.g., Diffie–Hellman; instead we make $q$ as small as we safely can to improve exponentiation performance.  So usually we don't consider the order-$q$ subgroup of $(\mathbb Z/p\mathbb Z)^\times$ with a safe prime $p = 2q + 1$ to be a Schnorr group.  But you wouldn't be disinvited from parties if you called it a trivial case of a Schnorr group with bad performance.

  Where was a procedure to generate Schnorr groups first published?

The generation procedure—randomly choose prime $q$ of appropriate size, randomly choose $k$ of appropriate size until $p := kq + 1$ is prime, and randomly choose $h$ until you find a generator $g := h^k \not\equiv 1 \pmod p$—is obvious enough that it's easy to imagine that nobody bothered to write it down in a paper to publish in an academic venue.

    results for other signature schemes like Schnorr's are considered as folklore results but have never appeared in the literature

What the ‘folklore’ comment means is that everyone tacitly felt they understood the result to be (perhaps intuitively or obviously) true, but nobody bothered to write a proof down or publish it, so there was nothing in the literature to formally cite.


Decrypting LFSR, knowing the beginning of the cyphertext, and nothing else

It's used the right tools, apparently with the right input, but missed how to use their output.
If, when given the first 84 bits of keystream, a proper Berlekamp-Massey implementation outputs a polynomial of degree 27, then it also has found a 27-bit initial state, such that the 27-bit LFSR with this initial state has output starting with the 84-bit keystream. And one can have high confidence ($p\approx1-2^{2\cdot27-84}>99.9999999\%$) this is not by accident.
Next steps:

Understand where in the Berlekamp-Massey code used lies the 27-bit initial state, and output that. Basically, if the LFSR convention is that of a Fibonnaci LFSR, that initial state is the 27 first terms of the input sequence analyzed (which is why it is often not an explicit output).
Make an auxiliary program that implements this LFSR and produces keystream.
Verify correctness of the above by checking that the first 84-bit output is the input to the Berlekamp-Massey code / the known keystream. If not, fix whatever is wrong.
Generate as much keystream as needed to decipher.

Note: I recall I helped fix Berlekamp-Massey code in C. Try it online!. And someone wrote some elements of the auxiliary program (but it's non-trivial to link the two). Help on use of a particular tool is off-topic, especially for CTF or homework. And writing the auxiliary program (perhaps as an extension of the  Berlekamp-Massey code) is a simple and essential exercise.


Is there a construction for a variable length block cipher that uses a fixed length one?

Yes, there is standard work on this. You should see "On the Construction of Variable-Input-Ciphers" by Bellare-Rogaway (PDF). They give definitions and constructions.


How secure would this code be against cryptanalysis?

What you have is a type of substitution cipher, at the level of words rather than letters. Using multiple ciphertexts to correspond with the same plaintext atoms is called homophonic substitution. Homophonic substitution does make frequency analysis on atoms more difficult, but by no means impossible. You merely need more ciphertext to analyze.

Frequency analysis can also be performed on digrams (i.e. pairs of words) or longer sequences. For example, a word that usually precedes a noun has a high probability of being a or the.

Compared with an alphabetic substitution cipher, yours requires a huge key: the key needs to describe all possible substitutions, so it must contain one or more entry per word. Rather than apply complex rules based on such a large key, you'd do better to generate a random key of the same length and use it as a one-time pad. That one-time pad would be good for a plaintext that's as long as your dictionary, whereas frequency attacks would begin in practice long before your dictionary was exhausted.

Adding instructions such as “skip” or “rotate key” in the stream doesn't fundamentally improve things, It does make frequency analysis a lot more difficult if you use them correctly, but not impossible the way modern cryptography does (every byte has exactly the same chance of having any given value, to someone who doesn't know the key). You need to describe the rules in the key, making it even larger.


Why doesn't steganography increase the size of an uncompressed image?

If you consider the mechanics of embedding the image in it's simplest form, then all you do is repurpose some of the existing bits.  The following is a Wikipedia extract from an article on steganography:-

  For example, a 24-bit bitmap uses 8 bits to represent each of the three color values (red, green, and blue) of each pixel. The blue alone has $2^8{}{}$ different levels of blue intensity. The difference between 11111111 and 11111110 in the value for blue intensity is likely to be undetectable by the human eye. Therefore, the least significant bit can be used more or less undetectably for something else other than color information. If that is repeated for the green and the red elements of each pixel as well, it is possible to encode one letter of ASCII text for every three pixels.

which kinda looks like this:-

except that your message is encrypted.  So the image remains exactly the same size.

The issue facing you (and your software) is how many bits can you alter and remain unnoticed?  One certainly.  The above example uses two and the altered image looks similar.  Could you use three then?  Clearly seven bits would totally destroy the image and tip off the attackers. It's a balance between leveraging the unavoidable noise introduced by the image digitisation process, the artistic scene and how dangerously you like to live.

Generally the blue channel is the noisiest from a CMOS/CCD sensor point of view.  You might be able to inject additional bits into that channel without significant human detection.

Note: There are more advanced embedding methods that can alter the discrete cosine transform coefficients inside a JPEG file.  This allows JPEGs to hide messages that would otherwise be impossible in this lossy format. There's a pretty good summary of advanced methods within the introduction to Data hiding inside JPEG images with high resistance to steganalysis using a novel technique: DCT-M3.


Difference between Zero Knowledge Proofs and Multi Party Computation

A zero knowledge proof allows the prover to prove a statement to someone else, without giving any bit of information. Consider the following "game":
Bob tells Alice he knows how to open a door, and Bob does not want to tell her how. Say this door is in the middle of a tunnel, that has two entries. So people can enter it, open the door in the middle of it, and exit on the other way.
Now, Bob enters the tunnel from some side, say left, and Alice didn't see him. Then Alice yells: "Bob, can you get out from the right side of the tunnel, please?". If bob knows the secret, opens the door and exits on the other side, otherwise he got lucky and exits from where he entered. What is the probability for bob to fool Alice the first time? 50%, right? Because is Alice that chooses from where he must exit, once he is inside the tunnel. Think Alice and Bob repeat this protocol many, many times, say 200. The probability for Bob for exiting always from the side asked by Alice, without him knowing the secret, is 1/2^200. This is just an example, but in reality, making a proof be zero knowledge is very difficult.

For more details on it, see also the answer here

Unfortunately, regarding the MPC I don't know very much, so let's hope someone else can help you.


How broken is a xor of two multiply with carry generators?

I see no reason to expect your construction to be cryptographically secure.  A single MWC generator is not something that was ever designed to be cryptographically secure.  A cryptographically-strong PRNG needs to be designed in a very different way from a non-crypto PRNG.  In particular, it sounds like MWC was designed to have a long period.  But having a long period does not guarantee that a PRNG will be crypto-strength; not anywhere near it.  And xor-ing two non-crypto-strength PRNGs is not in general a good way to build a crypto-strength PRNG; there's no reason to expect that such a scheme will be secure.

Crypto-strength PRNGs have much stronger requirements, so there is no reason to expect that a statistical non-crypto PRNG will be cryptographically strong (it almost certainly won't be, if it wasn't designed to be).  If you want a crypto-strength PRNG, you need to pick one that was designed to be that way from the start; you're not likely to fare well by picking a non-crypto PRNG and then trying to tweak it.

In any case, this approach seems misguided.  We have crypto-strength PRNGs that are secure, fast, and well-vetted.  I don't know why one would mess around with trying to design your own based upon a non-crypto PRNG; that way tends to lead to insecurity.  If you think you can do better than the entire field at designing fast crypto-strength PRNGs... well, maybe you can, but I doubt the odds are on your side.  Instead, I recommend you use a standard crypto-strength PRNG, if you need crypto-quality pseudorandom numbers.

I recommend take a look at What stops the Multiply-With-Carry RNG from being a Cryptographically Secure PRNG?, as well as by KISS: A Bit Too Simple (PDF).  The first one handles the plain MWC construction by Marsaglia; the later analyzes the non-cryptographic scheme by Marsaglia named KISS (which combines the output from two MWC generators as well as a linear congruential generator and a  binary linear generator).  Both do not exactly represent the same construction, but the broad lessons probably apply here as well.  I've paraphrased from my answer there and extended it to apply to this specific question as well.


How to protect a device which has different levels of access to its storage?

This question may be more suitable for other forums (https://security.stackexchange.com/ ?) This is not about cryptography.

I don't think cryptography will help you to secure the devices to protect your IP to the extend you'd like. Once you hand over the hardware to the 3rd party, there isn't much you can do.

Please do not count this as an answer, as it won't help you to achieve your goals. This "answer" should help you to clarify some options

  stealing software #1 and #2...
  change in a single jump instruction to bypass the "if"

So you are already assuming the SBC running the frontend could be fully read and the software modified (this is often so). If you give the adversary this power, you cannot do much about it. In that case "obfuscation" is the best what I can see (any better idea?).

  or the attacker to read the memory (either volatile or non-volatile) of the microcontroller in #3 is to be considered impossible

That's a very strong assumption.. though you've linked a "secure microprocessor", maybe you've already have something like that in mind  (smart card with crypto features? hms?)

  The commands sent from #2 to #3 will be encrypted by the public key.
  The replies (mainly status messages about the states of the controlled  machinery) sent from #3 to #2 will be encrypted with the private key.

Encryption is done with public keys, you could decrypt with a private key. So the microcontroller and the frontend both need each its own keypairs (private and public). PKI encryption will blow the message a lot, it is very performance expensive.

However - when you already came to an assumption that the adversary could read everything off the frontend (including the private key), the adversary could inpersonate the frontend and read/decrypt the messages anyway (accessing the private key of the frontend).


Why XOFs are more convenient than Hash Functions in modeling Random Oracles

Suppose you are instantiating a cryptosystem, such as RSA-FDH signatures with 2048-bit modulus, or EdDSA over a $b$-bit curve for $b \gg 256$ like edwards448, which needs a sizable hash function modeled by a random oracle.  But the hash functions available at your disposal are only SHA-2.

EdDSA needs a $2b$-bit hash function.  For edwards25519, it was enough to use SHA-512, but not for edwards448.
RSA-FDH with a 2048-bit modulus needs a ${\approx}2048$-bit hash function.  None of the SHA-2 hash functions are big enough for this.

What do you do?  In order to instantiate one of these cryptosystems, you have to pick some way to compose the SHA-2 functions into a larger-output hash function.  It's not a priori obvious what instantiation to choose.

One might naively choose $H(x) \mathbin\| H(H(x)) \mathbin\| \dotsb \mathbin\| H^n(x)$, but this is manifestly not indifferentiable from a random oracle.  (You and I might not choose this, but I have seen people reach for it in practice.)
One might choose $H(x \mathbin\| 1) \mathbin\| H(x \mathbin\| 2) \mathbin\| \dotsb \mathbin\| H(x \mathbin\| n)$; of course, one must also choose how wide the numbers are, how they're padded, etc.
One might choose $H(H(x) \mathbin\| 1) \mathbin\| H(H(x) \mathbin\| 2) \mathbin\| \dotsb \mathbin\| H(H(x) \mathbin\| n)$ like you suggested, but it's not clear what purpose the extra $H(x)$ serves.

Personally I would choose option (2) with little-endian 64-bit integers, but justifying that choice requires further thought and explanation, and not everyone will make the same choice.  With a standard XOF there is no need to think about these questions: you just ask SHAKE128 for as long an output as you want.

This is part of why Ed448 was designed not to use SHA3-512 (in some counter mode or whatever) by analogy with Ed25519's use of SHA-512, but instead uses SHAKE256 with an appropriately long output.  The complexity of the OAEP standard arises in part because there were no XOFs available so one had to be invented (the ‘MGF’); it would have been much simpler and easier to understand if XOFs were available.


Private evaluation public quick verification VDF

A Survey of two verifiable delay functions authored by Dan Boneh, Benedikt Bunz and Ben Fisch is the best resource for understanding the most promising implementations of VDFs. It is a succinct review of two recent beautiful Verifiable Delay Functions, one due to Pietrzak and the other due to Wesolowski.
There are currently three candidate constructions that satisfy the VDF requirements. Each one has its own potential downsides. The first was outlined in the original VDF paper by Boneh, et al. and uses injective rational maps. However, evaluating this VDF requires a somewhat large amount of parallel processing, leading the authors to refer to it as a “weak VDF.” Later, Pietrzak and Wesolowski independently arrived at extremely similar constructions based on repeated squaring in groups of unknown order.
The security of Pietrzak’s scheme relies on the the security of the low order assumption: it is computationally infeasible for an adversary to find an element of low order in the group being used by the VDF. The Wesolowski scheme assumes the existence of groups that satisfy something called the adaptive root assumption, which is not well studied in the mathematical literature.
Recently, Starkware, the Cryptography Engineering firm led by Eli Ben Sasson has come up with a VDF service known as Veedo, deployed on Ethereum TestNet and MainNet. Please find the details in the following post.


What prevents a padding standard to cause a data loss?

Padding is always added, even if the plaintext is a product of the block size. This way the algorithm look for the last byte(s) and can safely interpret it as padding data. In case of alignment to the block size, a full block is added just for padding purposes.

So if your example shows 8 bytes of data and you are using a 64-bit block cipher, a block of eight 08 would be added as padding.


Yes, that is possible: It is quite obvious from the description of the key schedule that all involved operations are invertible. An implementation of that inversion is the function aes128_key_schedule_inv_round found in this C file.


Do I need to worry about the IV if I use a 32 byte random salt with SCrypt and AES-GCM?

If you use the key only once, then there is no danger of reusing a nonce with the same key because you're not even reusing the key!

A collision in the salt and password would lead to the same key, but though the probability of such a collision may be nonzero, it is nevertheless negligible for a 32-byte salt—unless, of course, you roll back your VM state and get the same initial RNG state, or equivalent.

Do make sure to use AES-256, by the way, and not AES-128, if you want a 128-bit security level.


How to break a 32 bit block cipher without key?

The block size does not directly determine the security of a block cipher. Even with a 32 bit block cipher the number of possible permutations is 2^32!, a stupendously big number.

Small block sizes are however cumbersome to use in secure modes of operation as the input is limited. For instance, it would be easy to have repeating counters in counter mode encryption.

So attacks generally rely on low key sizes or - of course - the construction of the algorithm itself. Now for Skipjack there don't seem to be any known attacks. The key size is not very large, but brute forcing it seems still (just) out of reach.

Skip32 seems to use the same key size. It seems to use largely the same structures and 24 out of the original 32 rounds. Skipjack has only been attacked successfully for 16 rounds. So it is very possible that it is secure. The problem is that this cipher doesn't seem to have any paper or design document assigned to it. Basically there is just code and comments. This is a likely reason that no crypto-analysis can be found.

So basically: there is no generic attack against 32 bit block ciphers. Skip32 could well be secure, but as it hasn't been analyzed, nobody knows for sure. AES and DES on the other hand are well used and analyzed (and survived pretty well under those circumstances).

If you want to attack it, it might be best to check if the the way it is used is secure or not, because the 32 bit block size will certainly influence that.

If you just want to encrypt 32 bit values you should also have a look at Format Preserving Encryption (FPE). Those modes of operation can use standardized ciphers while achieving the same goal (although possibly at the cost of efficiency).


For which RSA moduli, precisely, is $e=d$ for all $e$?

I wondered if there is a "simple" description of the set of numbers n that have this property.

Yes, there is; $n$ has a prime factorization $p_1 \cdot p_2 \cdot ... \cdot p_n$ such that all the primes are unique (i.e. $n$ is square-free), and for each prime factor $p_i$, $p_i-1$ must be a divisor of 24.  In other words, each prime must be a member of the set $\{2, 3, 5, 7, 13\}$

Why is this?  Well, $e^2 \equiv 1 \mod \lambda(n)$ (for $e$ r.p. to $\lambda(n)$) is equivalent to $e^2 \equiv 1 \mod p_i-1 $ for all $i$ (for $e$ r.p. to $p_i-1$); this latter holds only if $p_i-1$ is a divisor of 24.

As a consequence, we see that there is only a finite number of such modulii; if we restrict ourselves to modulii with two factors, we see that 91 is the largest possible.  If we include multiprimes, then the largest possible is $2730 = 2 \times 3 \times 5 \times 7 \times 13$


Prove monoalphabetic cipher is a valid symmetric cipher

The lemma you need for this is that $$((a \bmod m) + b) \bmod m = (a + b) \bmod m \tag{1}$$ for all integers $a$, $b$ and for all positive integers $m$.  In other words, this lemma says that, if you're going to add (or subtract) a bunch of numbers together and then reduce the sum modulo $m$, it doesn't matter whether or not you reduce any (or all) of the summands modulo $m$ first.

The easiest (and most usefully generalizable) way to prove the lemma (1) above is via the notion of modular congruence.  Basically, we define $a$ and $b$ to be congruent modulo $m$, written as $a \equiv b \pmod m$, if $a = b + km$ for some integer $k$.  From this definition, it immediately follows that $$(a \bmod m) \equiv a \pmod m$$ and, in fact, that $$(a \bmod m) = (b \bmod m) \iff a \equiv b \pmod m.$$

We can also show that the modular congruence relation $\equiv$ obeys many of the same algebraic laws as normal equality.  In particular, we can show that it is transitive, i.e. that $$a \equiv b \text{ and } b \equiv c \implies a \equiv c \pmod m,$$ and that it is compatible with addition in the sense that $$a \equiv b \iff a + c \equiv b + c \pmod m.$$

Applying these properties of modular congruence, we can see that $(a \bmod m) \equiv a \pmod m$ implies $(a \bmod m) + b \equiv a + b \pmod m$, which then implies lemma (1).

  Bonus exercise: Also show that modular congruence is compatible with multiplication in the sense that $$a \equiv b \implies ac \equiv bc \pmod m.$$

Now that we've proven lemma (1), the rest is simple: $$\begin{aligned}
D_k(E_k(p)) &= ((p + k) \bmod 26) - k) \bmod 26 \\
&= (p + k - k) \bmod 26 \\
&= p \bmod 26.
\end{aligned}$$  If $0 \le p < 26$, then $p \bmod 26 = p$, and we're done.  (We do need to make this additional assumption for the encryption to be reversible, since it would not hold if $p$ could take other values!)

Of course, we could've also skipped lemma (1) entirely, and just appealed directly to modular congruence, and in particular to the fact that $$E_k(p) = (p + k) \bmod 26 \equiv p + k \pmod{26}\,\,$$ and $$D_k(c) = (c - k) \bmod 26 \equiv c - k \pmod{26},$$ from which it follows that $$D_k(E_k(p)) \equiv p + k - k = p \pmod{26}.$$


Shamir's Secret Scheme : Knowing the threshold

Yes. If all of the shares you have are valid, you can tell when you have reached the threshold. Reconstructing the secret from $t+1$ shares will yield the same result as reconstructing the secret from $t+2$ shares. Reconstructing it from $t-1$ will however (always) yield a completely different result. Reconstructing the secret from $t-2$ or fewer shares will yield a different result with probability $1-1/q$, provided that all of the coefficients (except order $0$ and order $t-1$) are selected uniformly from $\mathbb{Z_q}$ and the high order coefficient uniformly from $\mathbb{Z_q^*}$. If "weak sharings" are avoided by selecting all coefficients to be non-zero, the probability will be slightly off.

For instance, if you are using Lagrange basis polynomials for reconstructing the original polynomial, adding more shares over the threshold will not increase the degree of the resulting polynomial and the zero degree term will remain constant.

There exist variants of Secret Sharing that will allow you to verify if a share is valid or invalid, such as Pedersen Verifiable Secret Sharing.


preferred method for generating k for DSA / ECDSA

The "normal" way of generating the k value is by doing it randomly, which is what FIPS 186 describes. FIPS 186-4 does not conceptually deviate from previous incarnations of FIPS 186 in that respect.

It so happens that having a good random generator is a tough requirement; some systems (especially embedded) do not have such a generator; it can also be quite inconvenient to make an external PRNG available to the signing engine (it's an extra parameter to pass through several API layers).

One particularly vexing characteristic of random number generation is that it cannot be tested. If you implement ECDSA with a poor generator, then signing will still happen, verifiers will verify, and all unit tests will report that everything is fine. This is the perfect setup for wide-scale blunders, and, indeed, it happened.

Derandomization is a generic methodology for fixing such issues in signature algorithms: it removes the need for a source of randomness, and since it makes the signature deterministic, it can be tested: unit test will not only check that the generated signature is a valid one, but also that it is the valid signature that should be produced. RFC 6979 is an incarnation of derandomization for DSA and ECDSA: generated signatures are fully compatible with standard DSA/ECDSA verifiers, but they are also deterministic and thus can be tested against the test vectors provided in the RFC.

I wrote that RFC all by myself, and pushed it as "informational"; it was not a mandate by NIST or ANSI or whatever, and it did not receive any such "official" blessing. It still went through some reviewing: the draft has been around since March 2011, the test vectors have been independently verified, the internal construction uses HMAC_DRBG (which has itself been thoroughly reviewed), and nobody found anything wrong with it (from a cryptographic point of view)*. RFC 6979 has found its way into some well-known cryptographic libraries, such as Crypto++ of Libgcrypt; it has also been deployed in implementations of Bitcoin "wallets", following a number of incidents where bitcoins were siphoned out because of poor PRNG.

One may note that the mechanism described in RFC 6979 more or less follows the generation method described in section B.2.2 of FIPS 186-4: it really is works by "testing candidates", and the candidates are produced by an "approved RBG" (HMAC_DRBG is one of the NIST-approved PRNG construction). The real deviation is that in RFC 6979, the PRNG is not seeded by gathered entropy, but by the concatenation of the private key and the hash of the signed message. Thus, it may be argued that you can implement RFC 6979 and still comply to the letter of FIPS 186-4.

It is possible to use RFC 6979 with the internal HMAC_DRBG seeded with not only the private key and hashed message, but also some gathered entropy, at which point the signatures are no longer deterministic, and you lost the ability to test the implementation against test vectors, but you then are fully back into the NIST fold, which might be convenient if you aim for full formal compliance to some set of regulations.

(*) It has been remarked that HMAC_DRBG is relatively heavy-handed with regards to the number of invocations of the underlying hash function. In practice, the elliptic-curve computations will dominate the overall cost, the hashing cost being typically less than 10% of the total cost.


128 bit AES CBC bit flipping on second block

There is only one way I see how to avoid having this block of garbage in you plaintext after CBC bit flipping attack, but it requires to be able to see the result of the decryption and to know the whole plaintext you are attacking, which may not be the case in most practical scenarios.

Say you want to alter the third block of plaintext, P3:

Do your CBC bit flipping attack on P3 by modifying C2, the normal way
get the modified plaintext. P2 should be garbage
now modify C1 in order to “repair” P2, that is, C1 = (the garbage you got) XOR (the original P2)
this is going to mess up P1, so you now you modify the IV to “repair” P1


Where should I start to learn cryptography?

https://gnupg.org/documentation/index.html

Not experienced, just sharing one of the ways, which working for me (Online identity verification issues -> Web of trust -> PGP -> Cryptography).


For example, one could rely on ZKBoo, which in turn builds upon the MPC-in-the-Head paradigm by Ishai et al. The authors even provide an implementation, which demonstrates how to prove knowledge of a SHA-1 and SHA-256 preimage, respectively. The proofs are of linear size in the number of AND gates in the circuit. For more compact proofs you could have a look at SNARKs.

The authors discuss $\Sigma$-protocols, which are in fact interactive. However, as shown here or here, one can make those proofs non-interactive using the Fiat-Shamir transform (yielding security in the random oracle model) or the Unruh transform (yielding security in the quantum accessible random oracle model).


Avoiding collisions by combining MD5 and SHA-2

Currently no collisions are known for SHA-256 and it can be used safely to hash long texts and you can be confident you won't happen to get a collision by chance.
Generally speaking if we have two different hash functions and $f$ and $g$ and you hash some input $x$ with both and use the concatenation $f(x)||g(x)$ the collision resistance of this will be better than either function individually and in some cases much better.  If the functions are unrelated and you are only worried about chance collision the likelihood of a collision will be the product of the likelihood of collision in each function individually. However this last statement will not hold in face of an attacker exploiting weakness in these function. It's still harder that either individually but may not be noticeably harder to find a collision than finding a collision in just one of the two.
Other techniques of combining the functions such as $f(g(x))$ are ill advised and won't add security, since any collision of $g$ is also a collision in the composition.


Does key-length recommendation provided by NIST consider quantum computer?

Does this consider quantum-computer?

No, it does not.  It is generally believed that, because of Shor's algorithm, a Quantum Computer will be able to factor and compute discrete logs (including within an elliptic curve group) in polynomial time, hence algorithms depending on those will be insecure.

As for the symmetric algorithms, the conventional wisdom is that you will need twice the key size to obtain the same level of security.


Generate secure password hashes without access to PBKDF2 or bcrypt

Actually you are quite near on implementing PBKDF2. It is kind of iterated HMAC execution. So have a look here and just implement the missing parts: PBKDF2


Random numbers for Rabin-Miller primality tests

The fundamental property of the Rabin-Miller primality test is that, if the value $N$ being tested is composite, then it will return "composite" at least 75% of the time.  That is, if we define the function $RabinMiller( N, A )$ that runs the Rabin-Miller test against the number $N$, using $A$ as a witness, then for any composite $N$, $RabinMiller( N, A )$ will evaluate as "Composite" for more than 75% of the values of $A$ in the range $[2, N-1]$.

So, you question is "what happens if we don't chose $A$ uniformly from the range $[2, N-1]$; what happens if we chose $A$ from a much smaller range?

The answer to that is that nobody really knows; we know that at least 75% of the numbers in $[2, N-1]$ will reveal $N$ to be composite, however there are no proven results how they might be distributed (there is a proof if we assume an unproven conjecture within number theory, but until we get a proof of that conjecture, it doesn't count).  It would appear to be reasonable to conjecture that they are, in fact, reasonably well distributed, however we don't know that.

Hence, if you select your value $A$ from a smaller range, then while you probably have a good test, you have just voided the probabilistic provability that Rabin-Miller gives you.

In addition, there is also this fact that works in your favor; the Rabin-Miller proof states that, for any fixed composite $N$, that at least 75% of the values $A$ will return "composite", however for a random composite $N$, then $A$ will return "composite" almost all the time.  While there are certain composite $N$ where a random $A$ will have a $\approx 25$% chance of returning "probably prime", however those $N$ values are rather rare (significantly rarer than primes).  What this means is that, in practice, Rabin-Miller works significantly better than the proof would suggest.

So, that's the bottom line?  Well, if you're interested in retaining the provability aspect of Rabin-Miller, you rather have to select values from the full range (and it's not all that expensive when compared to running the Rabin-Miller test).  On the other hand, if you just want something that is likely to work, selecting from a smaller range is, as far as we know, reasonable.


Is it theoretically possible to construct a string that contains its own hash value?

Yes, for any secure cryptographic hash function, it is overwhelmingly likely that there exists a string which contains, or even begins with, its own hash value (in any given encoding, even).  However, if the hash function is indeed secure, it is also exceeding unlikely that we could ever find such a string.

First, let's look on the positive side.  A good cryptographic hash is, a priori, supposed to be indistinguishable from a random function from the set of all bitstrings (or byte strings) to bitstring of a given fixed length $k$.  For such a random function, the probability that a randomly chosen $n$-bit string (where $n \ge k$) maps to its own $k$-bit prefix is $1/2^k$.  Since there are $2^n$ distinct $n$-bit strings, the probability that none of them maps to its own $k$-bit prefix is:

$$\begin{aligned}
(1 - 1/2^k)^{2^n}
&= \exp(2^n \log(1 - 1/2^k)) \\
&\lesssim \exp(-2^n/2^k) \\
&\to 0 \quad \text{as } n \to \infty
\end{aligned}$$

Thus, the probability that there is at least one $n$-bit string that maps to its own $k$-bit prefix tends to $1$ as $n$ increases.  Indeed, the convergence is extremely rapid, being given by the exponential of an exponential.  For example, for a 256-bit hash, the probability that there exists some 260-bit input string that hashes to its own 256-bit prefix is about $1 - \exp(-2^{260}/2^{256}) =$ $1 - \exp(-2^4) \approx$ $1 - 10^{-7}$.  For 261-bit inputs, it's $1 - \exp(-2^5) \approx$ $1 - 10^{-14}$, and so on.

Obviously, the probability that there is an input string that hashes to some substring of itself must be at least as high as the probability that there is one that hashes to its prefix.

In particular, a curious corollary of this result is that, for any secure hash function, the probability that there exists an input string that hashes exactly to itself is very close to $1 - \exp(-1) =$ $1 - 1/\mathrm e \approx$ $0.63$.  (This approximation is good as long as the output bit length $k$ is greater than about 4 or so.  For, say, a 256-bit hash function, it's as close to exact as makes no difference.)  This is a general mathematical result: for any sufficiently large set $S$, a randomly chosen function $f: S \to S$ has a fixed point with probability close to $1 - 1/\mathrm e$.

Now for the bad news: to find such a string by brute force, the expected number of trials we'd need is $2^k$.  For, say, $k=256$, such a search is way beyond not just currently available computing power, but any conceivable computing power achievable in the universe using known physics.

Now, of course, real hash functions are not actually random functions, and it's possible that there might be some way to find such strings more efficiently than by brute force.  However, if such a method were found, it would arguably be good evidence that the hash function in question was not secure, and that its use should be discontinued.

In particular, the ability to efficiently find an input string that hashes to a given value would be a clear break of first preimage resistance, and any hash function allowing it would be considered completely broken.  Technically, just having the ability to efficiently find strings that hash to a substring of themselves, without being able to control what the actual hash value is, would not violate any of the three standard security properties required of a hash function (first and second preimage resistance and collision resistance).  However, it would allow the hash function to be distinguished from a random function, and in practice, any plausible attack that would allow such input to be found would almost certainly compromise other security properties of the hash as well.


What can be said about the order of short Weierstrass curves with $a=1$ and $b=0$?

The curve $E$ given by the equation $y^2 = x^3 + x$ is a Montgomery curve. Those are
are the form $By^2 = x^3 + Ax^2 + x$, so in this particular case we have $A=0$ and $B=1$.
The points of order $2$ have their $x$-coordinate as a root of $x^3 + x$. If $-1$ is a square over $\mathbf F_p$, then the points of order $2$ are $(0,0)$, $(\sqrt{-1},0)$ and $(-\sqrt{-1},0)$. Otherwise there is only $(0,0)$.
On those curves, the closest to a prime for the cardinality is $4\cdot\text{prime}$ for both the curve and its quadratic twist (such as the Goldilock curve), or $8\cdot\text{prime}$ and $4\cdot\text{prime}$ (such as Curve25519).


Would key stretching help mitigate concerns with "verifiably random"?

No, not really. The problem is that these kind of parameters may themselves be chosen deliberately. In other words, NIST/NSA may have performed a pre-calculation to make sure that the key stretching outputs a value that opens the algorithm up to some kind of attack.

Lets take an example, would you trust: SHA-256^2^40("Trust me, I'm an innocent string?"). Is that more or less secure than SHA-256^2^40("Trust me, I'm an innocent string"), i.e. without the question mark? How would I know that e.g. NIST or the NSA didn't do a few of these calculations up front to create their preferred output? the amount of iterations may be varied as well.

It's probably easier to secure the input of the hash. If they would say to a group of trusted experts: you all jot down a string, then concatenate them all (ordered by last name), and finally SHA-256 the ASCII string then the output is determined by the aggregated input of the experts.

The Brainpool curves were created in a controlled environment, which makes them more safe - according to DJB - than the NIST curves. Of course this is still less secure as not having to pre-determine any input values. This is the road taken by the highest level safe curves.


Security of RSA signature using PKCS 1.5

Provided you follow PKCS#1 v1.5 verification exactly, and don't attempt shortcuts like checking only the hash part of the message hash representative, it should be fine.  There's no security reduction to the RSA problem proven, like there is for RSA-FDH or RSASSA-PSS, and certainly no reduction to factorization, like there is for Rabin–Williams, but no weaknesses have been published in RSASSA-PKCS1-v1_5.

If you do take shortcuts like checking only the hash part of the message hash representative, you may set yourself up Coppersmith- or Bleichenbacher-style attacks when $e = 3$, like the attack poncho sketched a while back.


Is Functional Encryption about Access Control over encrypted data alone?

Existing definitions for functional encryption don't support "combining" ciphertexts in the way that you suggest.

As far as doing more than just access control, two very recent papers (to appear next month at STOC 2013) achieve functional encryption for arbitrary functionalities:

Attribute-Based Encryption for Circuits by Gorbunov, Vaikuntanathan, Wee
Reusable Garbled Circuits and Succinct Functional Encryption by Goldwasser, Kalai, Popa, Vaikuntanathan & Zeldovich

Two caveats:

These are feasibility results only, and are not practical (one could probably argue that they cannot be both practical and support arbitrary functionalities)
They achieve slightly relaxed (but still natural & useful) security definitions for functional encryption, where either the number of keys or number of ciphertexts in the system is bounded (I don't remember the exact details).


Help with linear approximation of DES(I don't understand some part of it )

Definition: $$NS_a(\alpha,\beta) = \# \{x| 0 \leq x < 64, (\oplus_{s=0}^{5}(x[s] \bullet \alpha[s])) = (\oplus_{t=0}^{3}(S_{a}(x)[t] \bullet \beta[t]))\}$$

Here, $x$ is your input to the S-box, and $S_a(x)$ is the output of the corresponding S-box. $\alpha$ and $\beta$ are the masks. Then, $NS_a(\alpha,\beta)$ is the number of coincidences that exor of input bits masked by $\alpha$ and exor of output bits masked by $\beta$. Take a look at the following example, where $\alpha = 16$ and $\beta = 15$, namely, $\alpha = 010000$ and $\beta = 1111$, and input is $x=011100$ where we consider fifth S-box: $$011100 \xrightarrow{\text{5'th S-box}} 1110$$
$$\oplus_{s=0}^{5}(x[s] \bullet \alpha[s]) = x[4] \bullet \alpha[4] = 1$$
since $\bullet$ is the bitwise 'and' operation, $x \bullet 0 = 0$ and $0 \oplus x = x$.
$$\oplus_{t=0}^{3}(S_{a}(x)[t] \bullet \beta[t]) = (S_{a}(x)[1] \bullet \beta[1])\oplus(S_{a}(x)[2] \bullet \beta[2])\oplus(S_{a}(x)[3] \bullet \beta[3]) = 1$$
Then, we increment $NS_a(16,15)$ by 1. If you repeat this for all possible inputs(i.e. $0 \leq x < 64$), $NS_a(16,15)$ turns out to be 12 indeed.
So, we keep $\alpha$ constant while we go through each 64 possible input. Since each input bit would be '1' 32 times, and '0' 32 times, this idea sums up to the fact we would always have 32 1's and 32 0's on the left hand side of the equation. Another way to convince, is just ordering the inputs in Gray code order, and omitting every non-masked bit, and since Gray codes toggle 1 bit at a time, our exor would change for each input, thus we would have 32-32 distribution on the left hand side of the equation. For the right hand side of the equation, the same holds, and we would have 32 zeros and 32 ones. Here, think S-boxes as boxes assigning 32 zeros and 32 ones on the left hand side to 32 zeros and 32 ones on the right hand side, and further assume all zeros are assigned to ones and all ones are assigned to zeros. Then, we slightly change our Sbox, to assign a zero to another zero, which is basically swapping 2 outputs of the Sbox, to align two zeros; which then would imply two ones are also assigned to each other. This is somehow a cumbersome way of explaining it, but when I studied Matsui's attack, I convinced myself this way.
In other words, we have 32 inputs with odd number of 1's and 32 with even number of 1's in it's binary representation.   , Then, we have 32 zeros, and 32 ones on the left hand side of the equation. Since for each S-box, there are

I think I have an intuitive way to see this, but I should have a look at my notes, I'll try to edit this section as soon as possible.

Actually, we get 7 key bits, then reverse the process, i.e. begin decrypting the ciphertext in the reverse order, with reordering round keys and using the same structure to obtain 7 more bits. Here, when we reverse the whole scheme, we obtain another best expression with different masks on plaintext and ciphertext for some specific expressions, -not all of them, as far as I know-, where we can express their characteristic by just changing plaintexts to ciphertexts and ciphertexts to plaintexts in the given linear approximation of DES. So, how to obtain 7 key bits? From algorithm 1, or any n-round expression Matsui gave for an n-round DES, we can obtain 1 bit of information directly. If we introduce (n-1)-round best expression to an n-round DES, as you probably noticed, we are left with an expression in terms of plaintext, ciphertext and $F(X,K)$. making use of the term $F(X,K)$, -note each round key is 48 bits, which is 6 key bits effecting an S-box-, we can recover these 6 key bits. Algorithm 2 is the algorithm for searching these 6 key bits. When you recover 7 bits using Algorithms 1 and 2, just reverse the order, and starting from the ciphertext, start decrypting, and apply the analysis algorithm again to recover another 7 bits.

I'm not a mathematician, so I'd rather not talk about "linearity/nonlinearity" in the sense of functions in mathematics, but keep in mind that the linearity of S-boxes add confusion, thus strenghtens it's security, while P-boxes add diffusion, which makes key bits and plaintext bits get in each other as fast and as well as possible.

Note: I'm not an experienced cryptographer, but I'm reading and studying these basic attacks nowadays, if I'm mistaken, I'm sorry.


Well, when we talk about "chosen plaintext attacks", there are two possible flavors for this attack:

The attacker gets to create a list of plaintexts to be encrypted; we'll go through and encrypt them all, and then hand over all the ciphertexts to the attacker.
The attacker gets to ask for a plaintext to be encrypted; we encrypt it and hand over that ciphertext.  Based on what the ciphertext looks like, he can then select another plaintext for us to encrypt (and we'll go through the procedure for a number of plaintext/ciphertext pairs).

This second model is known as "adaptively chosen plaintext attack" model, because the attacker can adapt the plaintext he selects based on previous results.  This is a strictly stronger attack model than the "nonadaptive" attack model, where we insist that the attacker gives us all the plaintext up front before we give him anything.  "Adaptively secure" means that it is secure within this attack model.

Nowadays, this distinction is a bit obscure, mostly because we really don't have much use for a cryptographical primitive that is secure only in the nonadaptive model; hence a "chosen plaintext attack" typically does mean "adaptively chosen plaintext attack".  However, the terminology does turn up when we're being precise.


Even passwords are vulnerable to hash collision attacks?

Data of more than a few dozen bytes can be vulnerable to MD5 collision attacks, but only (as far as is known) when an adversary can inject (choose) enough data of her choice in both the legitimate and forged version, which is feasible in some important scenarios, including certificate signing. There is evidence this was used by the flame malware, and plausible speculation that it went undetected for years.

No, passwords are not  vulnerable to hash collision attacks in the standard use of a password hash, where the hash is stored instead of the correct password and used to test a candidate password; that's because the adversary is assumed not to know the password, and can not inject material in both hashed messages; it is thus immaterial that in such a standard password hashing application, what's hashed is generally below the threshold where MD5 collisions are known to be feasible.

However, hashed passwords can often be recovered when their hash is known, by a different attack, specifically a brute-force (first) pre-image attack: e.g. an MD5 rainbow table if the password was hashed using MD5 without salt; or, even with salt, enumerating plausible passwords using a password cracker. To defend against these attacks, one should avoid a password hash getting known, and when that can't be insured with high confidence must use a good, purposely slowed password hash, such as scrypt with salt and appropriate parameters. Improving password hashing is an active research topic.

Update: CodeInChaos rightly points in a comment below that even in the standard use of a password hash, an adversary allowed to change password (and perhaps, knowing the salt) could use a password collision so as to select a password such that another password allows access, which she could use to discredit the system to some degree.

Update: Ricky Demer rightly points in comments below that in some Password Authenticated Key Agreement (PAKE) protocols, finding collision on messages involving two different possible passwords can give a useful advantage to the adversary: the ability to check these two passwords with a single query.


Is there a hash algorithm that is slow to calculate but relatively fast to check?

It sounds like you're looking for a proof-of-work system.

One way to implement such a system would be, given a message $m$, to ask for a suffix $s$ such that the hash $H(m \operatorname{\|} s)$, where $H$ is some standard cryptographic hash function and $\|$ denotes concatenation, begins with a specific prefix (e.g. $n$ zero bits).

Of course, the execution time of such a scheme is not really deterministic; we can predict the expected time it will take, but the actual time will be geometrically distributed, and so will vary a lot.
Also, the particular scheme I described is very easy to parallelize, so that using multiple processors (or parallel processors like GPGPUs) cuts down the expected solving time in inverse proportion to number of cores used.  Depending on your application, this may or may not be an issue.


How to determine proportion of quadratic residues in elliptic curve group?

I have read that the proportion is close to $\frac{1}{2}$

That is, in fact, correct; it is (for large $p$) extremely close to $\frac{1}{2}$; hence if you need your hashing process to fail with probability at most $2^{-64}$, you need your parameter $k \ge 64$

  I would imagine that the proportion of $x \in \mathbb{F}_q$ that do not result in quadratic residues is calculated $\frac{q - n}{q}$, which would be negligible

I believe that's where you're getting confused; you appear to be reasoning "we know there must be $n-1$ solutions to $y^2 = x^3 + ax + b$; there are $q$ possible values of $x$, and as $q \approx n$, then almost every possible value $x$ must be part of a solution.

The part that you're missing is that, for (almost) every value of $x$ which is a solution, there are two possible $y$ values that correspond to it; that is, if the pair $(x,y)$ is a solution to $y^2 = x^3 + ax + b$, then so is $(x, -y)$.  The sole exception to this is if $(x, 0)$ is a solution, there are at most 3 possible $x$ values that satisfy this; as 3 is tiny compared to $q$, we can ignore this for this analysis.

Because of this, there are approximately $(n-1)/2$ possible $x$ values that are possible solutions to the equation; that is, that result in a quadratic residue.  Because $n \approx q$, $(n - 1) / 2 / q \approx \frac{1}{2}$


Discrete logs on elliptic curve with embedding degree 3 with the 'MOV' attack

Let's take your latter example. We will use the Weil pairing here, since that was the original MOV approach. Let's pick some arbitrary points in your curve:

$$
\begin{eqnarray}
P &=& (6116 : 2715) \\
Q &=& (3034 : 462)
\end{eqnarray}
$$

From now on, we'll actually work in an extension field of $\mathbb{F}_{8111}$, namely $\mathbb{F}_{8111^3}$. For concreteness, we choose the polynomial $x^3 + 4x - 11$ to define the extension field.

Now we need to find some arbitrary point that has order $8269$ but is not a multiple of $P$. We know that the group structure of the points of order $n$ in a pairing-friendly curve is $E(F_q)[n] = \mathbb{Z}_n \oplus \mathbb{Z}_n$, so there are definitely such points out there. An example point would be

$$
R = (3515x^2 + 7098x + 2717 : 3745x^2 + 7258x + 4072).
$$

Now all it's left is to apply the Weil pairing to both points:

$$
\begin{eqnarray}
w_1 &=& e(P, R) \in \mathbb{F}_{8111^3} \\
w_2 &=& e(Q, R) = e(uP, R) = e(P, R)^u \in \mathbb{F}_{8111^3}
\end{eqnarray}
$$

Now we can solve the log of $w_1 = 7474x^2 + 74x + 6953$ and $w_2 = 2625x^2 + 6673x + 243$ over $\mathbb{F}_{8111^3}$. It's $2634$, and it's easy to see that $2634\cdot P = Q$. For large fields, it is considerably faster to find $\log_{w1} w2$ via the number or function field sieve ($L[1/3; c]$) than the elliptic curve discrete log $\log_P Q$ via Pollard's rho ($O(n^{1/2}))$.


You cannot encrypt 720 bits plaintext using just AES-128. AES is a 128 bit block cipher. Such a block cipher has an input of 128 bits of plaintext and an output of 128 bits ciphertext; and that's it. You need some kind of construction to make block ciphers encrypt larger or smaller plaintext.

Such constructions are known as (block cipher) modes of operation. Some of these constructs like ECB (usually insecure) or CBC require padding (what you call "expansion"), most of the others do not. Even ECB and CBC can be used with ciphertext-stealing to avoid padding.

Probably the best way is to chose a mode of operation that doesn't require padding; CTR mode operation is probably the most used mode for new implementations. It is also the most used within authenticated modes of operation such as GCM, which come highly recommended.

If you're stuck with ECB or CBC then choosing PKCS#7 compatible padding is probably the best / most compatible padding out there. Beware of padding oracle attacks though (did I mention authenticated encryption already?).


It's straightforward to find a large set of preimages for any hash value!

For arbitrary $x,z \in \{0,1\}^n$, you can construct $Y(x,z)$ such that $h(x||Y(x,y))=z$. Let $D$ be the decryption function for the block cipher, i.e. $D(x,\cdot)$ is the inverse permutation from $E(x,\cdot)$. The goal $h(x||Y(x,z))=z$, i.e. $E(x,Y(x,z))=z$, is equivalent to $Y(x,z)=D(x,z)$.

Thus for any $x$, all of the inputs $x||D(x,z)$ for $z \in \{0,1\}^n$ are collisions for $h$.


Why do fully homo-morphic constructions use 'ring' or 'lattice' structures?

Lattices are used simply because we do not know how to build homomorphic encryption from any other problems, like factoring or discrete logarithm.  Their mathematical structure was found to simultaneously enable homomorphic addition and multiplication while other bases for encryption could handle at most one of them.  (For the case of ideal lattices/rings, this seems intuitive:  If ciphertexts are elements of a ring then you can naturally add and multiply them, although things are not really that simple.  It was later found that the ring structure could be removed, and that any lattice would suffice.)

Advantages like quantum resistance etc are only incidental.


How to attack a two time pad if the plain text is randomized?

If your PRNG is good and your seed unknown $C_R = pt \oplus PRNG(seed)$ is essentially already an encryption of the plaintext using a stream cipher constructed from a PRNG.

Specifically it is indistinguishable from random.

Therefore $K_2 \oplus C_R$ can be viewed as an encryption of $K_2$. This is not useful but it also doesn't help an attacker.

I would conclude that this scheme is just as secure as constructing a stream cipher from a PRNG.


length extension attack on an MD5 hash of a text file of about 10K Bytes?

First of all, let us explore what a "length extension attack" is; it might not be exactly what you assumed it was.

Suppose we were given the MD5 hash of a bytestring we'll call $A$; we may have no idea what the string $A$ consists of, but we do know its length.

Then, we can create a bytestring $B$ (which depends on the length of $A$, but not any of its contents; it'll be between 9 and 73 bytes long), so that, for any string $C$ we pick, we can compute the value:

$MD5(A || B || C)$

This value will generally not be the same as the original $MD5(A)$ value; so if you're looking to create second preimages, this doesn't help you.  However, you're looking for (say) a way to attack the use of MD5 as a Message Authentication Code, this might.

As for the time taken to compute the value $B$, and the value $MD5(A || B || C)$, well, that's essentially trivial; $B$ can be computed directly from the length, and the time taken to compute the hash is essentially the time it takes to compute $MD5(C)$.

A number of other hash functions share this observation; SHA-1, SHA-256, SHA-512. There are also other hash functions for which this is not true: SHA-384 and AHS (now known as SHA-3) among them.


How to map output of hash algorithm to a finite field

To hash from $\{0,1\}^*$ (or other large domain) into the integers in $[0,q)$ or any set with a natural mapping¹ to that interval, pick a $b$-bit security margin, a hash $H$ at least $h=\lceil b/2+\log_2q\rceil$-bit and unrelated to others used in the cryptosystem, and define the hash of bitstring $M$ as $H(M)\bmod q$, with $H(M)$ considered an integer in $[0,2^h)$ per e.g. big-endian convention.
When $M$ is random and $H(M)$ has at least $b$-bit security against distinguishing attacks, this has at least in the order of $b$-bit security against distinguishing attacks. When $q>2^b$, this has at least in the order  of $b$-bit preimage resistance. When $q>2^{2b}$, this has at least in the order of $b$-bit collision resistance.
E.g. for $q$ up to 400 bits, $\text{SHA–512}(M)\bmod q$ will do if nothing in the system uses SHA–512 (nor something built using the same constants).
If ones needs several independent such hash functions, one should use several independent $H_i$ to start with. That can be constructed from a single hash $H$, e.g. as $H(M\mathbin\|i)\bmod q$.

¹ The mapping between the destination set and $[0,q)$ must be efficiently computable in both directions. Therefore the set can be the finite field $\mathbb F_q$ when $q$ is a prime or a prime power, or the ring $\mathbb Z_q$ (aka $\mathbb Z/q\mathbb Z$). We need a different construction for an Elliptic Curve (sub)group of order $q$ if we posit it's one where the Discrete Logarithm problem is hard.


Proof for exponentiation in modular arithmetic

That is not a conjecture, that is basic number theory and follows from the fact that

$$(ab)\textrm{ mod } n = \big((a\textrm{ mod } n)\cdot(b\textrm{ mod } n)\big)\textrm{ mod } n$$

Write $a=k_an+r_a$ and $b=k_bn+r_b$ and thus $a \textrm{ mod }  n = r_a$ and $b \textrm{ mod }  n = r_b$. Plugging into the left hand side will give you:

\begin{align}\big((k_an+r_a)(k_bn+r_b)\big)\textrm{ mod }  n &= \big((k_a k_b  n + k_a r_b+ k_br_a  )n + (r_a   r_b)\big)\textrm{ mod }  n \\ &= (r_a  r_b)\textrm{ mod }  n\end{align}

The last step is because any multiple of $n$ clearly yields a zero remainder when divided by $n$.

Plug into the right hand side gives you $(r_a r_b ) \textrm{ mod }  n$. This shows the equality which is what you're looking for.

Viewing the exponentiation $m^e \textrm{ mod } n$ as $(m \cdot \ldots \cdot m) \mod n$ (multiplying $m$ with itself $e-1$ times), then you have what you are looking for.


Hashing large messages, how does it work?

While hashing, the messages are divided into chunks and padded so that a message is fit into the chunks, properly. For example in SHA-256 the message appended 1, then many zeroes and finally the message size in 64-bit added. The total size must be $x$ multiple of 512 where $x$ is minimum.

No, they are not separately hashed, they are chained. If not it how would you combine the output? If you don't combine what is a hash there? There is actually, hash trees famously know as Merkle Trees used to verify data blocks, or many files where you only keep the root hash.

SHA-256, for example, uses  Merkle–Damgård (MD) construction in which a compression function $F$ which is

$$F:\{0,1\}^{256}\times\{0,1\}^{512}\to\{0,1\}^{256}$$

The 512-bit input space is the message space. 256-bit input space is the previous hash, if it is the first block then an IV is used.

let $$M\mathbin\|pad=m_1\mathbin\|m_2\mathbin\|\ldots\mathbin\|m_\ell $$ $$H_i = F(m_i,H_{i-1})$$ with $H_0 = IV$ then

$$\operatorname{SHA-256}(M||pad) = F(m_\ell, F\ldots F(IV,m_1)\ldots))$$

This tells you about the MD construction, MD5, SHA-1, SHA-2 uses MD. There is also sponge construction that SHA-3 is based on, which left the OP as an exercise.


Binary representation of the inverse of a big number

The first $k$ digits on the right of the decimal point of the representation of $1/p$ in base $b$ also are the representation in base $b$ of $\left\lfloor b^k/p\right\rfloor$ left-padded to $k$ digits with zeroes.

If we want to perform computations to $k$ places after the decimal point for quantity $x\in\Bbb R$, we can use the integer quantity $\left\lfloor b^k\,x\right\rfloor$, or better $\left\lfloor b^k\,x+\frac12\right\rfloor$.

Any language (e.g. python) or library (e.g. GMP) capable of handling arbitrary precision integers let you make the necessary computations.

E.g. in python 3,

p = 3**161
print("{0:b}".format(2**700//p))

yields a 445-bit bitstring which, padded with 255 0 on the left, and then 0. on the left, is $1/p$ in binary to 700 binary places.


For concreteness, let's take the concrete case of RSA.  You generate your keys -- will consist of a public key -- two numbers (N, e) and a private key (N, d) so that if you use c = m^e mod N to encrypt an RSA message you can use m = c^d mod N to decrypt it.  (In reality its not quite so simple, you have to worry about hybrid encryption, padding, constant-time modular exponentiation).

Certificates will contain the public key, plus data describing the organization, all of which is generally cryptographically signed -- typically by another trusted entity, except for self-signed certificates which are signed by their own public-key.  To sign someone's certificate (which I will call cert) you need the private key S = Hash(cert)^d mod N.  However, to verify that a signature is correct you only need a public key, by checking that S^e mod N is the same as the hash of the original cert.

So to answer your questions:

Certificates are not the public key, but contain (1) the public key along with (2) other identifying information (who the organization is, what resources the certificate should be used for), and (3) a signature from some other trusted organization.
If you want to validate the certificate for say https://crypto.stackexchange.com, your browser (or OS) needs to ultimately follow a chain of trust to a certificate it knows and trusts.  That is the certificate served by stackexchange is valid for *.stackexchange.com is validated to belong to Stack Exchange, Inc. operated out of New York, NY.  It was signed by DigiCert High Assurance CA-3 (who presumably validated the identity of Stack Exchange).  The DigiCert High Assurance CA-3 intermediate Certificate Authority was itself signed by DigiCert High Assurance EV Root CA.  The public certificate for DigiCert High Assurance EV Root CA is self-signed and your OS or web browser needs to have it to be able to trust it (e.g., for an OS may be stored: /etc/ssl/certs/DigiCert_High_Assurance_EV_Root_CA.pem or for a web browser /usr/share/ca-certificates/mozilla/DigiCert_High_Assurance_EV_Root_CA.crt).
I think you had the gist of it.  You create one CA with a CA certificate (acting as a public key + more data) that you share widely, and a private key kept secret only used to sign other certificates.  When one of your machines (call it M) needs a certificate - private-key pair (e.g., to do SSL), then M creates their own private key and a certificate signing request (CSR) -- basically an unsigned certificate (technically it is self-signed - to ensure it wasn't tampered prior to being signed by the CA).  The CSR is securely sent to the computer with the CA's private key, which signs the CSR to create a signed-certificate which is sent back to M.  Now M can create use the certificate plus its own private key to setup SSL connections.


What is the maximum message size when using ECDSA (specifically secp256k1?

The first step of ECDSA (and most signature mechanisms in actual use) is hashing the message, both in signature production and verification. The result of this hash is then truncated to fit the group size; that's truncated to 255-bit for secp256k1.

Hence what limits the size of the message to be signed is the limit built into the hash, typically due to a fixed-size counter. That limit is usually $2^{64}-1$ bit (e.g. for SHA-256, typically used for secp256k1) or more (e.g. $2^{128}-1$ bit for SHA-512 or SHA-512/256, which would be usable as a substitute for SHA-256 with secp256k1).

$2^{64}-1$ bit is just shy of 2 exbibyte and >2.3 exabyte (several days worth of the current mobile traffic worldwide per this source). This is not a practical issue with usual hashes, which are sequential: hashing that at a rate of $10^9$ blocks of 512-bit per second (much more than anything a single sequential device currently achieves) would require more than a year. For hashing real large messages, we need a parallelizable hash, typically a hash tree. It would also be a good idea to sign subtrees of manageable size, to avoid storing exabytes of data only to find afterwards that it does not check.

Some APIs to ECDSA expect the hash to be done externally, and typically start at the truncation step. Technically, they do not fully implement ECDSA. For secp256k1, such API would probably process the low-order 255-bit of their pre-hashed message input. For signature production at least, it is important (prudent and perhaps essential) to only allow a hash (PRF secure in the ROM) to be fed there, as it is necessary for conformance, is an assumption in ECSDA security proofs/arguments, and doing otherwise at least allows existential forgery (perhaps worse).

Further, some APIs to ECDSA signature production take as input the random they use to sign (or the generator they use to generate that). It is then essential to only allow that input to be (or yield, for a generator) a random secret exclusively used for that purpose and a single signature; doing otherwise would jeopardize the confidentiality of the private key.


Why is the second XOR operation in OCB mode necessary?

I am wondering, why the second XOR operation is necessary.

If it is omitted, then an arbitrary permutation of the ciphertext blocks would not modify the tag, and hence any such modification would not be detected.

In the decrypt direction, the checksum (which is what the tag depends on) is an xor of all the values generated by the AES block decryption xored with a key/nonce dependent constant (which is the xor of all the delta's, but that's not important).  If you permute the ciphertext blocks, then you would perform the block decryptions (which would result in the same intermediate plaintexts, just in a different order); they would xor to the same value (xor'ed with the same key/nonce dependent constant), and so the checksum is not modified, and hence the tag is not modified.

The second XOR operations prevents this; with that second XOR, a permutation of the ciphertext blocks would alter the list of internal ciphertext blocks presented to AES (in the decrypt direction), and so alter the list of internal plaintext blocks generated by AES.

  The design is I believe inspired by the XEX construction introduced by DESX.

Nope; Phil Rogaway had a concrete reason for doing what he designed...


Understanding Twist Security with respect to short Weierstrass curves

The twist attack is best explained in Fouque et al's paper.

While the (quadratic) twist of the curve $E : y^2 = x^3 + ax + b \in \mathbb{F}_p$ is indeed of the form
$E^t : y^2 = x^3 + d^2ax + d^3b \in \mathbb{F}_{p}$ for nonsquare $d$, you can also think of the twist as the
set of points $(x, y)$ in $E^2 : y^2 = x^3 + ax + b \in \mathbb{F}_{p^2}$ where $x$ is exclusively in $\mathbb{F}_p$ but $y$ is either $0$ or only defined in $\mathbb{F}_{p^2}$ (plus the point at infinity, obviously). You can map such points from $E^2$ to $E^t$ as $(dx, d^{3/2}y)$. But you don't have to—you can simply solve the logarithm directly in $E^2$.

Here's a Sage example that demonstrates a twist attack on a Weierstrass curve over the integers modulo $2^{127}-1$:

# Setup fields
p  = 2^127-1
d  = -1 # non square in the field
K  = GF(p)
K2.<z> = GF(p^2)

# this curve has prime order, but a 2^44-smooth twist
a  = -3
b  = 2045
E  = EllipticCurve(K, [a, b])
Et = EllipticCurve(K, [d^2*a, d^3*b])
E2 = EllipticCurve(K2, [a, b])

# precompute orders
print E.order().factor();
print Et.order().factor();
print E2.order().factor();

# generate a discrete logarithm to solve
s  = randint(0, E.order())
P  = E([0, 26743016104147931148362869907315104519])
Q  = s * P

# query target with an invalid point
# of order 207464639
P_ = E2.lift_x(randint(0, p))
while P_.order() != Et.order():
  P_ = E2.lift_x(randint(0, p))

P_ *= Et.order() // 207464639

Q_ = s * P_ # query -- pretend this is done with an x-only ladder

# solve the log directly on E2
x1 = P_[0]
x2 = Q_[0]
s_ = E2.lift_x(x1).discrete_log(E2.lift_x(x2))

# map to Et (optional) and solve
x1  = d * P_[0]
x2  = d * Q_[0]
s__ = Et.lift_x(x1).discrete_log(Et.lift_x(x2))

print s % 207464639
print s_, -s_ % 207464639 # either one or the other
print s__, -s__ % 207464639 # either one or the other

So you can see that there is no manipulation of the $a$ and $b$ parameters of the curve: the only thing required in a twist attack is to send an $x$-coordinate for which $x^3 + ax + b$ is not a square in $\mathbb{F}_p$. Note that since both $x$, $a$, and $b$ are well-defined in $\mathbb{F}_p$, an $x$-only ladder for $E$ will also work for points of the twist defined in $E^2$. Perhaps an easier way to understand why it works is to rewrite $y^2 = x^3 + d^2x + d^3b$ as $dy^2 = x^3 + ax + b$.


How to convert a Diffie–Hellman key exchange number to work with different encryption algorithms

As the output of the DH key exchange is a number, it has to be converted into big-endian bytes before running it through a hash - say SHA (SHA2 or SHA3) for example, can convert it into a key of the correct length.

If you need variable-length keys, then you can use XOFs, which provide variable length outputs. This cannot increase the entropy of the result of the DH exchange.

If you need multiple keys, HKDF is an option. The DH output is already of enough entropy, so you can skip the HKDF-Extract step, and use the HKDF-Expand to create multiple keys that cannot be derived from each other.


What vulnerabilities would open up if PGP authentication didn't have integrity checking?

Digital signatures provide authentication, data integrity and non-repudiation. Thus, you are right to say that the authentication check is also basically an integrity check. If it didn't have an integrity check (i.e. no digital signatures) then you cannot be sure that the message you received is the original and unmodified version sent by the claimed sender. But I think in this case, since the authentication is also provided by the signatures, if there is no integrity then you wont have authentication too.


If your environment was fully compromised you could at no point actually decrypt your data, defeating the purpose. So I’m going to assume the user only uses an authentic client and the client’s memory is protected during execution.

Generate a private/public keypair. Store the public key on the server, encrypt the private key with the user’s passphrase and store it (encrypted) on the client.
Now the client can authenticate itself against the server without storing any secret between executions.


is this authenticated key exchange protocol sound? too complicated? obviously flawed?

The standard advice in this situation would: use a well-vetted mechanism, like TLS (or DTLS, or some other similar scheme).  If you're not doing that, you'd better have a good reason, as designing your own key-exchange protocol is non-trivial and unnecessarily risky.


How Paillier cryptosystem can be used practically to encrypt and decrypt big messages "m"?

The Paillier cryptosystem allows to encrypt integers modulo $n$. Therefore, if $m$ is bigger than $n$, encrypting it will lose most of the message - only $m \bmod n$ is retrieved through decryption.

To encrypt a message bigger than $n$, you must break it into blocks, which you encrypt separately. You can for example write $m$ in base $n$, as $m = \sum_i m_i n^{i}$, and encrypt the $m_i$'s separately with Paillier.

Also, regarding how to calculate $g^m \bmod n^2$: note that $g = n+1$, hence

$g^m = (1+n)^m = 1 + n\cdot m \bmod n^2$

(if you develop $(1+n)^m$, you get $1 + nm + n^2\cdot \mathsf{something}$, and the $\mathsf{something}$ disappears modulo $n^2$).


How many codes can I safely generate using the same HMAC key?

I don't think there is any official limitations when it comes from standardization bodies such as NIST. However, there do seem to be some papers such as New Generic Attacks Against Hash-based MACs.

They show that HMAC may have less security than previously thought after the birthday bound. Generally, if you have a hash output size of, say 256 bits for SHA-256 then you may have to start worrying after $2^{128}$ messages. This is of course not a limit that should worry you.

Even for SHA-1 you're probably going to be fine. However, you may want to stop using (MD5 for which the bound is a worrying $2^{64}$) and SHA-1 by now for other reasons than just the output size; there are too many attacks on those hash functions and attacks only get better.

Just use a modern hash function - SHA-2 or SHA-3 - as base for HMAC and you'll be alright. For SHA-3 you might want to take a look at KMAC as well, although support for that particular MAC is sparse.


Security Considerations in using SHA-1 for One Time Passwords

The security property needed for one-time password generation is that of a pseudorandom function. HMAC is assumed to be a pseudorandom function, when the hash function has certain properties. Collision resistance is not a required property for HMAC to be a secure pseudorandom function. However, when collision resistance is broken, this brings into question the general security of the function. As such, although HMAC-SHA1 is not actually broken, it is worthwhile looking at phasing into HMAC-SHA256, when possible.

I will just note that HMAC-SHA1 does not require collision resistance in the normal sense, since it is designed so that the hash of the message is prefixed by a secret key. Thus, the attacker is unable to compute the hash of the message itself.


Should I use distinct MACs for each user, or should I use a *direction* flag when communicating?

Either method is fine.  They're both secure.  You can use whichever feels more convenient, given your application setting.

Better yet -- don't try to design this kind of thing yourself.  Instead, use an existing scheme for providing a secure channel abstraction (e.g., TLS).


Hash collision resistance requirements for Lamport signatures

Yes, it makes sense to truncate the hash to 128 bits. The security proof actually says that if finding a preimage for F requires effort $2^{n}$, then breaking the Lamport signature scheme with $G$ having k-bit digests requires effort $2^{n}/2k$. So strictly speaking, with $F$ truncated to 128 bits and $G$ having 256 bits $(2k=512=2^{9})$, you will have $128-9=119$ bits of security.

This is not an artifact of the security proof: since there are $256*2=512$ public keys, an attacker has 512x more chances to find a preimage compared to a normal, single preimage attack.

In the Merkle signature scheme, the result is the same but you would multiply k by the number of messages that can be signed. EG for 1 million $(2^{20})$ messages, the security level is $128-9-20=99$ bits.

The wikipedia article is about $F$ only: the "input" is one of the private keys, the "output" is the corresponding public key and "message digest size" is the output size of $F$. I think that it just attempts to say that when the private key is very short and regardless of the output size of $F$, it is trivial to find a preimage.