Why was the Navajo code not broken by the Japanese in WWII?

Wrapping up my comment as an answer:

Imagine you’re a Japanese cryptanalyst in the year 1944. There is no such thing yet called “television”, and you’re still decades away from a wordwide network feeding you with all the knowledge you could wish for.

In that case there’s only a minimal chance you’ve ever heard or seen a Navajo. So, you’ll be wondering what “Joe” is talking about as it sure doesn’t sound like English. You‘ll be asking yourself things like: Is that the plaintext in some language I don’t recognize or simply a failed decryption attempt?

Furthermore, even if you would know it is Navajo and assuming you would have some plaintexts to your availability, you would still be wondering about the more simple things of cryptanalysis, like: What’s the character frequency of Navajo anyway?

Even more, since Navajo is a descriptive language. Even having things like character frequencies and plaintexts at hand,  how would you know what is meant by (eg) “wolf feeds bisons when eagle moon embraces cloud rock”?

See, Navajo indians may know “cloud rock” from stories told by their elders and they may know the exact day in the year when the “eagle moon embraces“ it… but you – sitting in your cryptanalysis room in Japan – have a rather minimal chance of even grasping half of it.

All in all, the use of Navajo boils down to a suplemental layer of “security through obscurity”. Maybe it helps if you think of the Navajo communicators as “living codebooks”. Embedding them (especially in key positions) added an additional layer of security to the already used cryptographic protection during radio communication et al.

In fact, take the actively used (radio) encryption during WW2 and add a layer of Navajo language use on top of it, and you’ll end up with something that could almost be called “double encryption”.

edit

To answer the additional question from your comment (now follow-up question added as an edit)…

  I think both of these are good explanations of why this scheme worked. From your explanations it seems to me the primary reason it wasn't broken is because it happened 70 years ago. Am I correct in saying this would never work today?

Under most conditions – Yes, that’s correct.

Of course, this depends on the exact situation. The reason I’m saying that is that there aren’t many Navajos living today (last I heard was something in the thousands). Some specific scenarios might change that “yes” to a “no”. But generally, looking at the means (and resources) available today, I tend to say that – in contrast to the WW2 – they indeed wouldn’t be very helpfull in terms of security. Actually, it’s like using the Klingon language from Star Trek, or Elvish from Lord of the Rings… as long as only a few know it, it might add a minimal bit of security. But nowadays, you can even take online courses to learn Klingon, Elvish, etc. Back in 194-something, the situation was quite different.

As an aside: I used the name “Joe” on purpose, since it was a commonly used nickname for US-American soldiers during World War 2. Another example of such a naming would be “Tommy“, which was used to hint at English soldiers.


Undetectable cheater in Shamir's Secret Sharing scheme

The way to prove this is to follow the same proof that Shamir's secret sharing is perfectly secret. Specifically, given any two points all secrets are possible since there is a polynomial going through every possible secret and the two given points. Since the polynomial is random, all of these polynomials have the same probability. The same thing is happening here: given any set of three points, there is a polynomial going through those three points. Now, assume that you know exactly what the secret is. If you look at any subset of two of the three points, there is a polynomial going through those two points and the secret that you know. Thus, it is impossible to know which of the three parties is cheating, even if you actually know the secret you are supposed to get.


A proof-of-work random number generation system for Pokémon

It is hard to tell from this question, but I suspect that you may have managed to confuse yourself about what problem you have: i.e., that you've gotten caught up in a particular mechanism, and would benefit from taking a moment to step back and look at the actual requirements.  I found it hard to extract the actual requirements from your question.

In these situations, it's always a good idea to ask yourself the question: What is my threat model?  What kinds of threats do you need to defend against?  What kinds of attack vectors are possible for an attacker?

For instance, a crucial question is: do you trust the game software that is running the game?  It sounds like you want to say that you don't trust the software, but that leads you to an unsolvable problem.

Or, to put it another way, it seems like there's a simple solution to your problem.  Your game software can generate truly random numbers using a suitable random number source (e.g., /dev/urandom or CryptGenRandom).  There doesn't seem to be any reason to use a deterministic PRNG, and no reason for the random numbers to be derived from untrusted user inputs.  Doesn't this solve all your problems?  Why are you going into such complicated stuff, when there's a much simpler way to generate random numbers that also happens to eliminate the issues you're worried about?  Is there some requirement that I'm missing?

If you're about to say "but the user could modify the game software's RNG to bias its output", my response will be "yes, that's always possible, and nothing you will ever do will ever be able to stop that".  Realistically, you can't prevent reverse-engineering of your software.  The user who is running your software could always run a modified version of your software that gives them better stats, and no amount of cryptography is ever to make that impossible.
But in any case, these are the kinds of questions you should be working out when you think through your threat model.

I confess I had a hard time understanding what proof-of-work has to do with trusting that the random numbers you generate are trustworthy.


Sextic twist of BN pairing parameters vs security

A current conservative estimate of the security level of a BN curve with an extension field size of 3072 bits, taking into account the Kim-Barbulescu attacks, is 2110. See the paper http://eprint.iacr.org/2016/1102.pdf and the discussion of it at https://github.com/zcash/zcash/issues/714#issuecomment-263007229 . An earlier discussion of these attacks is https://ellipticnews.wordpress.com/2016/05/02/kim-barbulescu-variant-of-the-number-field-sieve-to-compute-discrete-logarithms-in-finite-fields/ .

On the specific question about the sextic twist, G_2 is still an elliptic curve group, not the multiplicative group of a finite field. So index calculus attacks, including variants of TNFS based on Kim and Barbulescu's work, do not apply to it.


Benefits of functional programming languages

These languages have no side effects

Well, yes, kind of. They also are higher level languages, where you don't have (as much) control over e.g. timing or the wiping of memory. Those are the side effects that cryptographers worry about - rather than the mathematical side effects that you are alluding to.

I was wondering if those programming languages would have any benefits over "normal" programming languages when used for cryptographic applications.

Personally I think that any higher level language that provides e.g. memory protection is really a requirement for a secure application. Those kind of memory protection is generally provided by functional languages. It is probably even better than higher languages where you may have mutable variable values.
However, for the cryptographic primitives it makes sense to use machine code and - of course - native instructions whenever they are available. I've seen that bit-ops are generally much slower on these kind of languages. And we're talking about huge numbers here. For instance, Java and C# are already much slower than C if cryptographic primitives are programmed correctly (think a change of 2 x in performance degradation). Most other interpreted languages are much slower than that.
The performance advantages that functional languages may bring - such as delayed execution by passing functions - are not helpful - if not outright dangerous - for cryptographic primitives.

I was wondering if those programming languages would have any benefits over "normal" programming languages when used for cryptographic applications. Is that the case? If yes, why aren't they used more frequently?

Here again we must make a distinction between "cryptographic applications" and "cryptographic primitives". I think that a well tested library of native functions is quite often used within higher level languages. There are e.g. many OpenSSL wrapper libraries in use within higher level languages such as Python. I think this makes sense, although more (array) boundary testing on the used native libraries would be useful.
As for functional languages: I don't see this "proven correctness" as much of a benefit. Unusually there some boundary checks etc. to be made. But otherwise, generally you can work with the test vectors to show enough correctness for the primitive.
I still see purely functional languages mainly useful for mathematical applications and such like. Personally I think that they are complex enough that most developers will not use them for generic applications. Those kind of mathematical applications are generally not the type of applications that require a lot of security.
Whatever you think of the last section (which is rather opinionated), generally we don't choose a language based on the cryptography we tend to use. Security should be an integral part of an application design, but usually it is not the main use case. A language is mainly chosen because it fits the main use case or - of course - simply because of developer familiarity (and purely functional languages still are not the most popular languages out there).


Plain text size limits for AES-GCM mode at 2GB with Sun JCE implementation?

Quoting the comment on the limit value:

    // In NIST SP 800-38D, GCM input size is limited to be no longer
    // than (2^36 - 32) bytes. Otherwise, the counter will wrap
    // around and lead to a leak of plaintext.
    // However, given the current GCM spec requirement that recovered
    // text can only be returned after successful tag verification,
    // we are bound by limiting the data size to the size limit of
    // java byte array, e.g. Integer.MAX_VALUE, since all data
    // can only be returned by the doFinal(...) call.
    private static final int MAX_BUF_SIZE = Integer.MAX_VALUE;

In other words, decrypting has to buffer the whole ciphertext (even if you pass to update in pieces) which it does in a Java byte array, and by the long established JVM spec a Java array can't exceed 2^31-1 elements (or available heap space, if less, but you can't generally determine that in advance). This is actually a problem only for decrypting, but they apparently added the check on encrypting so you can't encrypt data and then be unable to decrypt it and thus permanently lose all the data you considered valuable, which some users would consider undesirable. (Although you could work around it using BouncyCastle, which doesn't enforce the 800-36D restriction -- or OpenSSL, ditto, but less easy to use in Java.)

See previous
Encryption of big files in Java with AES/GCM
https://stackoverflow.com/questions/23864440/aes-gcm-implementation-with-authentication-tag-in-java
https://stackoverflow.com/questions/26920906/how-come-putting-the-gcm-authentication-tag-at-the-end-of-a-cipher-stream-require-internal-buffering-


How hard/easy will be to break a SHA-1 or SHA-256 hash if the attacker knows part of the original text?

It's probably a really bad idea to try and roll-your-own here. If you have to ask a question like this, you would probably just be better off using shrink-wrapped solution like SSL rather than trying to make your own protocol. There are a lot of tricky problems around getting these kinds of things right.

However, if you insist on doing this yourself, there are constructions that allow you to do what you want to achieve here.

What you want is a message authentication code (MAC). You can MAC the hash of the variables and then send this across the insecure channel.

In order to do this safely, you need to use a construction like HMAC. You should particularly use such a construction if you are using SHA-1/SHA-256 as they suffer from message extension attacks.

You also need to guard against replays; that is, where an attacker resends a previously seen message on the channel with the hope of repeating an action or causing some other nefarious effect.

These are just a flavour of the kind of bear-traps that can spring when trying to design your own protocol!


Is there a truly safe signing algorithm?

The signing algorithms most often used nowadays are:

RSA based signature algorithms such as RSA-PKCS#1 v1.5 and the more recent RSA-PSS (currently specified in PKCS#1v2.2)
ECDSA, which is the "Elliptic Curve Digital Signature Algorithm", which will probably become the most used one, if not already, since RSA is not as efficient in practice as ECDSA for signing purpose, while validation of signature is faster with RSA. (You can see the Crypto++ benchmarks to get a better idea of their performance)
EdDSA, which is gaining more and more traction nowadays, as it is both easy to implement and secure, plus it is even faster than ECDSA and has plenty of secure open-source code available to use it.
DSA, which has lost the battle and is now less and less encountered on the field, since it is somewhat too complicated for nothing (we use to say it's because the better Schnorr's signatures were patented, that DSA had to circumvent, which made it a too convoluted algorithm)

None of these algorithm have been definitively broken, but it is true that certain instances of them are known to be weak.

First and foremost, note that RSA with a key of 2048 bits or more, is considered secure and should be fine for the next 10-15 years.
So are instances of the other algorithms such as ECDSA with secp256k1, EdDSA with Curve25519, known as Ed25519, etc.
This basically means that the crypto we use nowadays is not easily broken, since it would require both extreme computing power and patience to break it. (As pointed out in the comments, this translates also into large costs, but estimating the costs of breaking these instances would be a question in itself. See for example this question about 256 bits security and the cost of breaking it and keep in mind that we are generally considering anything that is belove 100 bits of security as broken.)

Typically in the question you linked, the RSA algorithm is used with a 512-bit modulus, which is known to be weak, as it is said to correspond to roughly 50-bits of security.

It is also true for the other algorithm, ECDSA, DSA, etc. that if you use them on too small groups, that it is possible to break them, however RSA is probably the one algorithm which has seen the most teams trying to break always larger modulus, there are even RSA challenges which used to have money at stake (but they were discontinued in 2007).

But the discrete logarithm world (on which most other signing algorithms are based) is not left behind and there are (fewer) teams working on trying to break it too.

So, in the end, there is no need to be questioning the security of everything because RSA has been broken when used with 512-bits modulus, however if someone were to come up with a device (maybe a quantum computer) able to break RSA with 2048-bits modulus, or 4096 bits, in a reasonable (typically polynomial) time, then we should all be worried.

But there is currently a competition to try and find the so-called post-quantum primitives that will safeguard us against such things.


No, the IGE encryption cannot be parallelized. Also the decryption of IGE/ABC is serial.

The input to the block cipher for encryption is the ciphertext of the previous block xor'd with the plaintext (and the result is then xor'd with the previous block plaintext).

For decryption, you have to XOR the ciphertext with the plaintext of the previous block before decrypting (and then XOR the result with the previous ciphertext).

If either ciphertext or plaintext is not available, you cannot processes the next block, or any future block.


CBC-MAC , fixed length, all blocks returned

I'll assume All ciphered blocks means the same as ciphertext for CBC-Encryption with implicit zero IV, while CBC-MAC is the last block of that.

All ciphered blocks is unsafe as a message authenticator for messages longer than one block, for it succumbs to a trivial attack (here with two blocks):

Eve intercepts message $M=M_0||M_1$ and its authenticator $A=A_0||A_1$
she knows $A_0=E(M_0)$ and $A_1=E(A_0\oplus M_1)$
she builds $M'=(A_0\oplus M_1)||(A_1\oplus M_0)$ and its authenticator $A'=A_1||A_0$.

The verifier will then accept as valid $M'$ and its authenticator $A'$ just as well as $M$ and its authenticator $A$.

Addition for completeness: $M'\ne M$ unless $M_1=M_0\oplus E(M_0)$, which is extremely unlikely to occur by chance.


As stated by Dan Boneh:

  Different communities define these (negligible and non-negligible) differently

For practitioners they are basically a scalar $\varepsilon$, where, for example:

$1/2^{30}$ is considered non-negligible because an event with this probability will probably happen after $2^{32}$ bits (1 gigabyte) of data
$1/2^{80}$ is considered negligible because an event with this probability will not likely happen over the life of the key.

On the other hand, in theory, $\varepsilon$ is considered a function $\mathbb{N} \to \mathbb{R}$.

Saying that a function is non-negligible means that the function is bigger than some polynomial infinitely often:

$\exists d: \varepsilon(\lambda) \geqslant 1/\lambda^d$

Saying that a function is negligible means that the function is smaller than all polynomials:

$\forall d, \lambda \geqslant \lambda_d: \varepsilon(\lambda) \leqslant 1/\lambda^d$

where $\lambda_d$ is some integer depending on $d$ and, in both cases, $\lambda$ is an integer.

That said we can see that $\varepsilon(\lambda) = 2^{-\lambda} = 1/2^\lambda$ is negligible, because for any constant $d$ there is a sufficient large $\lambda$ so $\varepsilon(\lambda) \leqslant 1/\lambda^d$.

We can also verify the other example from the link e-sushi provided: $\varepsilon(\lambda) = 2^{-100} = 1/2^{100}$ is non-negligible because if we set $d = 1000$ this function is clearly bigger than $1/\lambda^d$

$\square$

Note: Most of the answer is based on Dan Boneh's explanation about this subject on his coursera course
Note 2: This is also a nice answer on the subject


GCM: Math behind update of AAD after ciphertext has been processed

Well, $\operatorname{GHASH}$ might be better understood as the polynomial:

$$\operatorname{GHASH}_H(X_1, X_2, ... , X_{m-1}, X_m) = X_1 H^{m} + X_2 H^{m-1} + ... + X_{m-1} H^2 + X_m H^1$$

where addition, multiplication and exponentiation are in the field $GF(2^{128})$.  These addition, multiplication and exponentiation operations act algebraically quite a lot like the operators in a more traditional field (say, the real numbers); the usual tricks for rearranging polynomials work exactly the same.

What Bouncy Castle is doing is taking the vector $X_1, X_2, ... , X_{m-1}, X_m$ in two pieces, the AAD vector $A_1, A_2, ..., A_a = A || 0^v$ and the ciphertext $C_1, C_2, ..., C_c = C || 0^u$, and evaluating $\operatorname{GHASH}_H(A_1, A_2, ..., A_a, C_1, C_2, ..., C_c, X_{final})$ (where $X_{final}=[len(A)]_{64} || [len(C)]_{64}$ encodes the length of the AAD and the ciphertext).  One way to rearrange this is:

$\operatorname{GHASH}_H(A_1, A_2, ..., A_a, C_1, C_2, ..., C_c, X_{final}) =$
$H^{c+1}\operatorname{GHASH}_H(A_1, A_2, ..., A_a) + H\operatorname{GHASH}_H(C_1, C_2, ..., C_c) + HX_{final}$

With this rearrangement, we can obviously evaluate $\operatorname{GHASH}_H(C_1, C_2, ..., C_c)$ before we see any AAD data (or even before we know how long it is).

Now, you ask about partial blocks.  It turns out that we don't need to worry about partial blocks; GCM is defined so that both the ciphertext and AAD vectors are zero padded to the next full block; hence we never need to worry about partial blocks.  If you are wondering a collision if we append a zero byte to the AAD, well, that's what $X_{final}$ is there for -- appending a 0 changes the AAD length, and hence the $X_{final}$ value.


A general common technique is used in PGP
"key rings" or "key chains". You generate a master public-key pair and distribute your master public key. Use this master private key to certify your other generated keys so that you can store your private key securely, probably off-line, and use the other keys for daily usage. With your master public key, the certificates of the other generated keys in the chain can be verified.


Hitting a counter example in homomorphic encryption over the integers

The problem is that you're getting an "overflow" of the errors relative to the secret key.

We have $10 \bmod 9 = 1$, and $114100 \bmod 9 = 7$, so the "errors" in your ciphertexts are $1$, $1$, and $7$, which are all odd, hence the plaintext bits are $1$ (as desired).  When you add the ciphertexts, the errors add correspondingly, so you get a ciphertext with error $9$, which normally would decrypt to $1$.  However, in this case your secret key is also $9$, so in fact decryption "sees" an error of $0$, i.e., the "intended" error overflows back to zero.  This is why your final ciphertext decrypts to $0$ instead of $1$.

As the paper explains, the accumulated errors must stay smaller than the secret key in order for decryption to work.  (For simplicity, throughout this answer I'm assuming only non-negative errors, and that the modular reduction returns a non-negative representative.)


Quality of randomness on a Linux system with haveged

TL;DR: do not use HAVEGE, it was flawed. It's evolution HAVEGED (notice the additional D) has improvements, but this answer is about HAVEGE, because the original question was.

I do not buy some of HAVEGE, specifically the claim made here "tens of thousands of unpredictable bits can be gathered per operating system call in average", and the methodology used to support that claim, as found here.

Entropy gathering is described by this pseudocode:

where HARDTICK() is a function that reads a hardware clock counter. An experimental evaluation of the entropy gathered was made as follows:

  We determined the threshold for NMININT above which the content of
  Entrop array can be CONSISTENTLY considered as random, i.e. it cannot
  be distinguished by our battery of tests from truly random numbers
  (i.e DieHard + ent + FIPS 140 +NIST suite).

(Emphasis using bold is mine)

The data gathered in Entrop is built using a Pseudo-Random Number Generator, complete with repeated rotation by 5 bit of each 32-bit word of Entrop, combination by XOR with one bit of the least recently modified word of Entrop, and combination by XOR with the actual source of entropy, HARDTICK() (or rather, the delta between successive HARDTICK() which is to closest to the actual source of entropy). See HAVEGE's paper for more details.

The entropy at the output of that PRNG has been evaluated using an experimental test (not designed specifically against this PRNG). That's a cardinal mistake: any half-decent PRNG will pass this test, even if fed very little actual entropy in its input, which makes its output highly predictable.

While this does not constitute a practical break of HAVEGE, it shows that the justification of its entropy-gathering part is flawed. My recommendation is thus not to use HAVEGE.

The above is advice about HAVEGE, as in the original question, based on references from 2003. In it's successor HAVEGED (notice the additional D) of the 201x, there was some effort made towards a sound methodology, in particular checking the entropy at input of the PRNG, leading to the conclusion: "Most samples failed all tests!". It is acknowledged that theoretical analysis of the source of entropy to build a model suitable to support a demonstration of security "were not sufficient to constitute such a model". This at least is quite believable.


What if message is longer than keystream ?

TL,DR: “arbitrary length” primarily means “the length doesn't have to be a multiple of a certain size”.

  I have read that stream ciphers can be used to encrypt messages/streams of arbitrary length (cf. the description of the stream cipher tag).

That's generally the case, except that most stream ciphers have a maximum length. The maximum length is typically far larger than any practical message, so in practice stream ciphers can encrypt messages of arbitrary length.

The important thing about the “arbitrary length” of the message for stream ciphers is that you can stop the stream at any point. This is unlike block cipher modes, which can only encrypt a message whose length is a multiple of the size of a block. To encrypt a message with a block cipher, you need both a block cipher mode (to reach lengths larger than one block) and a padding mode (to cope with the last block, which in general is only partially filled).

For example, AES is a block cipher with a 16-byte block size. CBC is a block cipher mode (i.e. a way to turn a way to encrypt a fixed-size block into a way to encrypt a list of blocks). You can encrypt a 32-byte message with AES-CBC by running CBC for two blocks, but you can't encrypt a 31-byte message, because this isn't a whole number of blocks. You need to additionally specify a padding mode, e.g. PKCS#7 padding. You can encrypt a message of arbitrary length (in bytes — and again, up to a very large maximum) with AES-CBC-PKCS7 — first pad the message to 32 bytes with the PKCS#7 padding algorithm, then apply CBC for two blocks. In contrast, a stream cipher can encrypt a 31-byte message simply by calculating the cipherstream for 31 bytes. For example, to encrypt a 31-byte message with AES-CTR, you simply calculate 31 bytes of cipherstream and xor that with the message. Because CTR builds a stream cipher on top of a block cipher, calculating the cipherstream involves calculating two blocks (32 bytes) of ciphertext and discarding the last byte.

Padding is a reason to prefer stream ciphers to block ciphers. Padding looks simple, but it's actually subtle. In particular, bad treatment of padding on the decryption side can lead to padding oracle attacks. That being said, if the block cipher is used in a properly designed authenticated encryption algorithm, only the designer of the authenticated encryption algorithm needs to worry about this, not the end-user.

  However, there are stream ciphers that create a keystream of fixed length and XORs message and keystream bit by bit.

If the keystream is of fixed length, then it's a one-time pad, not a stream cipher. That's a matter of terminology.

  Therefore, I wonder, what happens if the message length is longer than the length of the keystream ?

Then you need a more complex protocol, with different keys for different parts of the message (i.e. key renewal). But in practice that basically never happens — if you have that much text to encrypt, it's almost always already split into separate messages.

  Is the keystream applied repeatedly to the remaining parts of the message in this case ?

Absolutely not! Applying the same keystream more than once is very insecure. It's a two-time pad and that can leak the whole message.


It's interesting to mention another type of faulty attack on RSA public modulus. Up to now the majority of research papers are about how to break the system after a fault attack in regular or CRT mode.

An interesting approach (among all the surveys of fault attacks on RSA), is describerd in this paper http://www.normalesup.org/~tibouchi/papers/talk-modulusfault.pdf where the authors try to exploit the CRT combination after a faulty attack on the public modulus. The obtained system is solved by using basic Lattice reduction technics to recover the RSA secret parametrers, which is more powerfull.


In theory, are there algorithms where everybody can read a message but only one person can write it?

If you can decrypt it, it is the right sender and if you can't, someone must have altered it / is not trustworthy.

Then by definition what you're looking for is called a signature. You're asking for something which is a signature, but is not called a signature. Sorry, there's no such thing. A signature is called a signature. And verifying a signature is called verification, not decryption.

It's not that “the signature method is the way to go”. It's that the properties you want are that of a signature. Therefore, anything that does what you want is a signature.


Can we estimate the loss of entropy when applying a N-bit hash function to and N-bit random input?

Actually, no. If it is a good Hash, you should roughly have $N-k$ bits of output entropy for some $k$ of much lower order than $N$.

The problem arises when the input is much longer than $N$ bits.

One way to estimate the entropy loss of such a Hash applied to $N$ bit inputs is to model it as a randomly chosen function on $N$ bits.
This was first done by Odlyzko and Flajolet. There is a nice review with updated results here

Let $\tau_m$ be the image size of the $m$th iterate of the function. The entropy can be related to its behaviour.

If the function is a permutation, $\tau_m=2^N$ for all $m\geq 1$ and there is no entropy loss.

Edit: See the comment and link by @fgrieu which is an estimate of what I called $\tau_1.$ He is saying that
$$
\tau_1\approx 2^{128-0.8272\cdots  }
$$
for $N=128.$


Minimum number of active s box to be resistance to differential cryptanalysis

The maximum differential probability of SBoxes should be first calculated.
Then, after finding the number of active SBoxes for some defined rounds, you should calculate the number of overall chosen plaintexts-ciphertexts by raising the probability to the power of the number of reached active SBoxes for this defined rounds. If the number that we computed, exceeds of some bounds of today's computational power, then this defined round is enough for resistance against differential cryptanalysis. Example: in Present cipher, any five round differential characteristics have a minimum of ten active boxes. If the maximum differential probability of a Present SBox is $2^{-2}$, so for five rounds, that has 10 active SBoxes, is $2^{-10}$. It means that for 5 rounds, this cipher is not immune against differential attack and by gathering $2^{10}$ numbers of chosen plaintext-chosen ciphertexts, we can set up this attack. But in own Present cipher, it has 25 rounds, it has 50 active SBoxes, so $(2^{-2})^{50}$ results in $2^{100}$, it means for setting up this attack, we need $2^{100}$ numbers of chosen plaintexts-chosen ciphertexts that it exceeds the amount available of today's computational power. So, we proved Present is immune in 25 rounds and 50 active SBoxes against differential attack.


Learning Cryptography in academic is something between science and practice. For science part,the aim is to studying and focus on topics related to cryptographic primitives(building block of cryptographic protocols).Based on categorizing these primitives, we can learn them easily:

Unkeyed primitives-----> Arbitrary Hash Functions,One way permutation,Random sequences
Symmetric-key primitives ----->Symmetric ciphers(Block ciphers,Stream ciphers),Arbitrary length hash functions(MAC),Signatures,Pseudo-random sequences,Identification primitives
Public-key primitives------->public-key ciphers,signatures,Identification primitives.

In this category, fundamental Topics like signatures, Hash,Identification,Pseudo-random sequence generators highlighted. Also topics such as Authenticated encryption,secrete sharing and subjects related to key-management based on cryptography.

In the practice part, the intention is to design and implement a cryptosystem, which means that use the logic of cryptographic primitives in an algorithm and then evaluate its soundness based on mathematics. In this side, we can name topics as cryptanalysis and attacks(theoretic  and implementation),methods for designing a cryptosystem,Lightweight cryptography and ways of implementing ciphers and cryptosystems in different devices.

At the end, examination of different ciphers and cryptosystems, gives analyse and design method ideas and also the way of using them in real world.


Discrepancy with reported key size for EDE ciphers in Qualys SSL Labs

DES has been specified to take a 64 bit key, but only 56 of them are used. The remainder are parity bits.

  The key ostensibly consists of 64 bits; however, only 56 of these are actually used by the algorithm. Eight bits are used solely for checking parity, and are thereafter discarded. Hence the effective key length is 56 bits

For 3DES the nominal key size is $3 \cdot 64 = 192$ bits and $3 \cdot 56 = 168$ of them are used.

The 3DES construction suffers from a meet-in-the-middle attack, which reduces the cost of breaking it to about $2^{112}$ operations, leading to an effective security of 112 bits.


Ciphertext-only attack on Simplified DES

Simplified DES is a toy Feistel cipher with 16-bit 8-bit block and 10-bit key, and only two rounds, intended for educational purposes. Here is a preview of the original paper, and an implementation; another; yet another.

If one knows one block of ciphertext, but nothing about the plaintext and key, the plaintext can not be guessed entirely: each of the $2^{10}$ key will lead to a plaintext. Most plaintext will be reached several times, but a few plaintext might be excluded. If S-DES was a perfect toy cipher, it seems that any particular plaintext would have odds about $(1-2^{-8})^{10}\approx1.8\%$ to be impossible (it turns out odds are much higher for S-DES with two rounds, which is far from a good cipher); this in itself would constitutes a practical attack in some contexts (e.g. when one is content to exclude that the plaintext is "OK" or "NO", with some sizable odds). An adversary can also assign odds to each possible plaintext, and is at a sizable advantage over a random guess of the plaintext.

If one knows enough blocks of ciphertext, and something about the plaintext, even so vague as "it is mostly text", then an attack is easy: decipher with all the possible keys, and have a human look at the $1024=2^{10}$ resulting plaintexts, formatted with one line per candidate key. Most likely the right plaintext will be spotted by naked eye+brain within seconds. This can be helped by ordering the candidates according to how well they compress with LZW or similar. Success depends on the length of the known ciphertext, and redundancy in the plaintext. If some bits of the plaintext are known, then very little ciphertext is enough (e.g. about 5 blocks if 2 bits per plaintext blocks are known to be 0, which is the case for ASCII).


How is the x coordinate of a "point at infinity" encoded in a Secp256k1 signature?

Standard encoding of the point at infinity is a single byte of value 0x00 (it is defined as such as least in P1363, possibly also in X9.62). Other representations may exist (such as a lot of bytes of value 0x00), but, in truth, the "point at infinity" does not have well-defined X and Y coordinates.

In the case of ECDSA, you generate a random value k which must lie between 1 and r-1, where r is the (prime) order of the conventional generator point G. Therefore, kG cannot be the point at infinity -- if it is, then the implementation got it wrong, or the key is not correct. Since kG is not the point at infinity, then it always has a well-defined X coordinate, and the problem does not arise. Similarly, if the point at infinity is obtained during the verification algorithm, then something definitely fishy is happening, and therefore the signature should be rejected (this cannot happen with a valid signature).

The same can be said about elliptic curve Diffie-Hellman. To sum up, if the encoding of the point-at-infinity begins to matter, then something went wrong and the best thing to do is to declare a failure (e.g. reject the signature as invalid).


Canonical inclusion map in subfield attack on overstretched NTRU

When $\mathbb{L}$ is a subset (or can be view as a subset) of $\mathbb{K}$, the canonical inclusion map just means
"take an element of $\mathbb{L}$ and treat it as element of $\mathbb{K}$".

In general, we do it implicitly and it is not necessary to think about it. For example, when we multiply a real number $r$ by a complex number $a + bi$, we are actually representing $r$ as $r + 0i$ and using the complex number multiplication.

Most probably, the authors defined this map explicitly to keep things formal and because $\mathbb{L}$ and $\mathbb{K}$ have different dimensions when view as vector spaces over $\mathbb{Q}$, so they want to make sure that there would be no confusion about how to compute the norms and other quantities of elements of $\mathbb{L}$ when we use them as elements of $\mathbb{K}$.

For exemple, if $\mathbb{L} := \mathbb{Q}(\sqrt 2)$ and $\mathbb{K} = \mathbb{Q}(\sqrt 2, \sqrt 5)$, then, the elements of $\mathbb{L}$ are of the form $a_0 + a_1\sqrt 2$ and those of $\mathbb{Q}$ are
$a_0 + a_1\sqrt 2 + a_2\sqrt 5 + a_3\sqrt{10}$.
Moreover, $\mathbb{L}$ can be seen as a vector space of dimension $2$ and $\mathbb{K}$ as a vector space of dimension $4$ over $\mathbb{Q}$.

Thus, it is clear that we can see elements of $\mathbb{L}$ as elements of $\mathbb{K}$ with $a_2 = a_3 = 0$. Thus, when you use the canonical inclusion map from $\mathbb{L}$ to $\mathbb{K}$, you are also taking vectors of dimension $2$ and using them as vectors of dimension $4$.

All that said, notice that the authors do not simply use the canonical inclusion map to  lift elements of $\mathcal{O}_{\mathbb{L}}$ to $\mathcal{O}_{\mathbb{K}}$, as they want to guarantee some properties after lifting (like lifted elements being multiples of the secret NTRU vector $(f, g)$ and being small).


Why is this function pseudo random (PRF)?

This is not exactly the way you're going about it, but I find it an easier way to deal with this kind of construction in general. First we switch to an information-theoretic setting, then go back to the concrete construction. This is very similar to proving the security of counter mode encryption.

First, we replace $F_k$ by a real random function $G$. Every new input to $G$ results in a uniformly random output $G(x) \in \{0,1\}^{n}$. Now we have the corresponding
$$
G'(x) = G(0\|x)\|G(1\|x)\,.
$$
Since every call to $F_k'$ gives you two free calls to $F_k$, we have
$$
\mathbf{Adv}^{\mathrm{prf}}_{F_k'}(D) \le \mathbf{Adv}^{\mathrm{prf}}_{F_k}(D') + |\mathbf{Pr}[D(G') = 1] - \mathbf{Pr}[D(\$) = 1]| \,,
$$
for a distinguisher $D'$ that performs at most $2q$ queries, by the triangle inequality (the first term being $\Delta_D(F_k', G')$, and the second being $\Delta_D(G', \$)$. $\$$ represents the ideal random function).

Our goal now is to distinguish $G'$ from a uniformly random function from $\{0,1\}^{n-1}$ to $\{0,1\}^{2n}$, to determine the second term of the above inequality. Notice that the inputs to $G$ are properly domain-separated: there are never any collisions between $0\|x$ and $1\|x$ for any distinct $x$.

More concretely, take any set of (distinct) queries $((x_1, y_1), (x_2, y_2), \dots, (x_q, y_q))$, where $y_i = \mathcal{O}(x_i)$. The probability that $G'(x_1) = y_1$, $G'(x_2) = y_2$, $\dots$, $G'(x_q) = y_q$ is $\left(\frac{1}{2^{n}}\frac{1}{2^{n}}\right)^q = 2^{-2nq}$. The probability for a random function is also $2^{-2nq}$, as each output has independent probability $2^{-2n}$.

The definition of advantage is
$$
|\mathbf{Pr}[D(F) = 1] - \mathbf{Pr}[D(\$) = 1]|\,,
$$
for any distinguisher $D$. From this we conclude that the advantage of any attacker against $G'$ is $0$, since it has exactly the same probability distribution as the random function. So we conclude that
$$
\mathbf{Adv}^{\mathrm{prf}}_{F_k'}(D) \le \mathbf{Adv}^{\mathrm{prf}}_{F_k}(D') + 0 \,.
$$


Why are there so many versions of the TEA block cipher?

The original algorithm is TEA, which is a very lightweight Feistel cipher. However, its extremely simple key schedule has two weaknesses. The first weakness allows what's called a related key attack, which is not an issue if the keys are chosen randomly. The second weakness causes equivalent keys. This means that, for TEA, any given key is equivalent to three other keys. This effectively weakens the keyspace from 2128 to 2126, which is bad, but not terrible. This is not normally a major problem unless the cipher is used in ways it shouldn't, such as for a hash.
XTEA was designed to fix the weaknesses in the original algorithm, in particular by adding a more complex key schedule. However, it was found that XTEA introduces some related key vulnerabilities of its own and did not meet the intended security target. This lead to another revision called XXTEA. However XXTEA is also vulnerable, in particular to a chosen-plaintext attack requiring only 259 queries (although the attack is impractical). The wide-block variation which avoids the usual downsides of a 64-bit block cipher is highly vulnerable as well, negating yet another benefit of XXTEA. In the end, it turns out that TEA itself is still quite secure as a cipher. It remains secure as long as it is used correctly, i.e. as a block cipher with uniform random and unrelated keys.


Breaking RSA using Chinese Remainder Theorem

I guess you are refering to the case where three people have the following public keys : $(n_1, 3)$, $(n_2, 3)$ and $(n_3, 3)$ (yes, $e = 3$, and this attack is one of the reasons we don't use $e = 3$ anymore).

In this case, if the same message $m$ is sent to those three persons, we have the following system :
$$
\left\{
    \begin{array}{ll}
        c_1 = & m^3\mod n_1 \\
        c_2 = & m^3\mod n_2 \\
        c_3 = & m^3\mod n_3 \\
    \end{array}
\right.
$$

Applying the CRT to
$$
\left\{
    \begin{array}{ll}
        c_1 = & x\mod n_1 \\
        c_2 = & x\mod n_2 \\
        c_3 = & x\mod n_3 \\
    \end{array}
\right.
$$
with $x = m^3$ will give you $x = m^3\mod n_1\times n_2\times n_3$

However, we know that $m \lt n_1,\ n_2,\ n_3$ so we have $ m^3 \lt n_1\times n_2\times n_3$ so a simple cubic root will give us the original message.

If the message is greater than any $n_i$, you wouldn't be able to recover it with a simple cubic root because you would have a modular result.

Today, we usually use $e=2^{16} + 1 = 65537$ which make this attack much more difficult to apply.


Where do Windows applications get entropy from?

Update: Since I wrote this post, CryptGenRandom has been deprecated. Apparently it is now recommended to use BCryptGenRandom from the "Cryptography Next Generation" API.

(Confusingly, it has nothing to do with bcrypt.)

Yes, Windows has something similar. It can be accessed through CryptGenRandom.

  With Microsoft CSPs, CryptGenRandom uses the same random number generator used by other security components. This allows numerous processes to contribute to a system-wide seed. CryptoAPI stores an intermediate random seed with every user. To form the seed for the random number generator, a calling application supplies bits it might have—for instance, mouse or keyboard timing input—that are then combined with both the stored seed and various system data and user data such as the process ID and thread ID, the system clock, the system time, the system counter, memory status, free disk clusters, the hashed user environment block. This result is used to seed the pseudorandom number generator (PRNG). In Windows Vista with Service Pack 1 (SP1) and later, an implementation of the AES counter-mode based PRNG specified in NIST Special Publication 800-90 is used.

Technically this is closer to /dev/urandom than /dev/random, but in practice the fact that you get cryptographically random numbers rather than "pure entropy" does not matter.


What's the purpose of the smoothing parameter in lattice-based cryptography?

As is mentioned in the comments above, there are many uses for the smoothing parameter. Here is one that provides some intuition of why it's useful.

For a basis $B$ of a full-rank $n$ dimensional lattice, let $P(B)$ be a parallelepiped of the lattice $\Lambda = L(B)$. Consider the operation of taking a point $x \in \mathbb{R}^n$ mod $P(B)$, which is to find the unique vector $y \in P(B)$ such that $x - y \in \Lambda$. In other words, $x \equiv y \mod P(B)$.

Now, consider a distribution that samples points in $P(B)$ in the following way. It first samples a point $e \in \mathbb{R}^n$ from the continuous Gaussian distribution with center at 0 and parameter s, then computes $t \equiv e \mod P(B)$. The output of the distribution is $t$. If the Gaussian parameter $s$ is greater than the lattice smoothing parameter $\eta$, then the distribution of $t$ is statistically indistinguishable from the uniform distribution over $P(B)$. Conversely, if $s$ is less than the smoothing parameter, than $t$ is likely to be close to some lattice point.

To provide a more geometric intuition of what's going on here, imagine placing balls around each vertex of the parallelepiped $P(B)$, and consider the region of each of these balls that intersects with $P(B)$. It is a nice exercise to show that these intersections in fact sum to one ball. Now, imagine going in the reverse, direction, taking a ball and dividing it up according to the angles of the vertices in the parallelepiped, then assigning each fragment of the ball to the corresponding vertex. This ball is the continuous Gaussian we started with in the distribution above. The smoothing parameter is the minimum "radius" of the ball such that, when the regions are assigned in this way, the overlapping distributions are indistinguishable from the uniform distribution over $P(B)$.

The smoothing parameter is intimately connected with many other lattice constants, especially parameters like covering radius and successive minima. This is just one of the many interesting properties that it has.


Reference for the Tortoise and Hare algorithm by Floyd?

Quoting Wikipedia:

  The algorithm is named after Robert W. Floyd, who was credited with
  its invention by Donald Knuth.3[4] However, the algorithm does not
  appear in Floyd's published work, and this may be a misattribution:
  Floyd describes algorithms for listing all simple cycles in a directed
  graph in a 1967 paper,[5] but this paper does not describe the
  cycle-finding problem in functional graphs that is the subject of this
  article. In fact, Knuth's statement (in 1969), attributing it to
  Floyd, without citation, is the first known appearance in print, and
  it thus may be a folk theorem, not attributable to a single
  individual.[6]

Now looking up reference [4], yields the Handbook of Applied Cryptography, which indeed contains a description as Note 3.8 (PDF version). However the Handbook also attributes the algorithm to Knuth as Wikipedia does, so

  Knuth, Donald E. (1969), The Art of Computer Programming, vol. II:
  Seminumerical Algorithms, Addison-Wesley, p. 7, exercise 6

is the reference you are looking for with the Handbook citing it as (PDF, reference 692)

  D.E.Knuth , The Art of Computer Programming – Seminumerical
  Algorithms, volume 2, Addison-Wesley, Reading, Massachusetts, 2nd
  edition, 1981


Why does the FBI ask Apple for help to decrypt an iPhone?

I'll try to take a stab at this. From Apple's iOS Security Guide, we learn that

  The metadata of all files in the file system is encrypted with a random key, which
  is created when iOS is first installed or when the device is wiped by a user. The file
  system key is stored in Effaceable Storage. Since it’s stored on the device, this key is
  not used to maintain the confidentiality of data;

and

  The content of a file is encrypted with a per-file key, which is wrapped with a class key
  and stored in a file’s metadata, which is in turn encrypted with the file system key. The
  class key is protected with the hardware UID and, for some classes, the user’s passcode.
  This hierarchy provides both flexibility and performance. For example, changing a file’s
  class only requires rewrapping its per-file key, and a change of passcode just rewraps
  the class key.

In other words: By physically being in possession of the device, you should easily able to get the file system key (take out the SSD and read the key off it). Let's call the file system key $K_{FS}$. Additionally, every file $f$ is encrypted using a per file key $K_f$. To get $K_f$, we need to have the file system key ($K_{FS}$) and the "class key", let's call the class key $K_C$.

So, there's a function $F_1$ which given the file, file-system key, the class key gives you the file key. $K_f$ =$F_1(f, K_{FS}, K_C)$. That means that for the FBI to decrypt a specific file, they'd need:

$f$ ✅
$K_{FS}$ ✅
$K_C$ ❌

So they don't have $K_C$ afaik. Right, how do you normally get that class key? The document says, it's protected by the "hardware UID" ($K_{UID}$) and (sometimes) the user's passcode $K_P$. Alas, there's another function $F_2(K_{UID}, K_P)$ which given the hardware UID and (sometimes) the passcode returns you the class key.
Assuming the FBI can easily brute force the passcode ($K_P$), all they need is the hardware UID ($K_{UID}$) but unfortunately for them that is apparently put in the silicon and therefore hard to access:

  The device’s unique ID (UID) and a device group ID (GID) are AES 256-bit keys fused
  (UID) or compiled (GID) into the application processor and Secure Enclave during
  manufacturing. No software or firmware can read them directly; they can see only the
  results of encryption or decryption operations performed by dedicated AES engines
  implemented in silicon using the UID or GID as a key. Additionally, the Secure Enclave’s
  UID and GID can only be used by the AES engine dedicated to the Secure Enclave. The
  UIDs are unique to each device and are not recorded by Apple or any of its suppliers.
  The GIDs are common to all processors in a class of devices (for example, all devices
  using the Apple A8 processor), and are used for non security-critical tasks such as when
  delivering system software during installation and restore. Integrating these keys into
  the silicon helps prevent them from being tampered with or bypassed, or accessed
  outside the AES engine. The UIDs and GIDs are also not available via JTAG or other
  debugging interfaces.

  The UID allows data to be cryptographically tied to a particular device. For example,
  the key hierarchy protecting the file system includes the UID, so if the memory chips
  are physically moved from one device to another, the files are inaccessible. The UID is
  not related to any other identifier on the device.

So, if I read that correctly, the function $F_2$ seems to be implemented in hardware and is accessible as $F_2'(K_P)$. Note that $F_2'$ only has one parameter which is the user's pass code. In other words $F_2'(K_P) = F_2(K_{UID}, K_P)$, so the hardware UID is provided automatically by the hardware. In non-Secure Enclave iPhones (like the 5C), you can probably brute force it with a custom iOS version that let's you use $F_2'$ as often as you want. In a normal iOS, only the lock screen can presumably run $F_2'$ and prevents you from doing that without ever increasing delays (and potential eventual device wipe). With a Secure Enclave iPhone (5S, 6 (+), 6S (+)) the secure enclave prevents you from running this function repeatedly. So not even the iOS kernel can run $F_2'$ without any delays.

Given that the iPhone in question seems to be a 5C, the FBI only seems to need a special version of iOS from Apple which allows them to use $F_2'$ repeatedly without delays with automatically provided pass codes. That should give the FBI 10000 (assuming a 4 digit pass code) or 1000000 (assuming a 6 digit pass code) "class keys". They can then just try each of the class keys and one of them will give them the data.

It is irrelevant for this particular question but I think it would still be interesting: Does the Secure Enclave change anything here? At the first sight: Obviously yes because a new iOS version wouldn't be good enough because the Secure Enclave would prevent you from running $F_2'$ in a loop by brute forcing the pass code. BUT: The secure enclave runs some kind of firmware too, so this limit could probably be lifted but updating the Secure Enclave. So far it's unclear to me whether Apple can do that without wiping all the content from the Secure Enclave. Different sources claim different things. This article covers that. Especially it cites a tweet from John Kelley who was apparently formerly within Embedded Security at Apple. He claims

  [...] I have no clue where they got the idea that changing SPE firmware will destroy keys. SPE FW is just a signed blob on iOS System Part

In other words: Even with a newer iPhone Apple could just deploy a special firmware to the Secure Enclave (SPE) which would allow to run $F_2'$ as often as the FBI pleases.

I hope this helps. All the information is taken from the iOS Security Guide and my interpretation of it.

edit: Because of the comment how my answer answer the question I should indeed state that more clearly. IMHO the FBI asks Apple because the need to run  $F_2'$ very often without delays so they can brute force the iPhone's code. For the iPhone 5C a new version of iOS should be enough as only the OS prevents you from doing that (you don't have programmatic access to $F_2'$ without special privileges). For newer iPhones, the Secure Enclave does prevent that apparently. The FBI can't compile their own, hacked version of iOS without this restriction because the iPhone only runs code signed by Apple and the FBI does (probably) not have Apple's signing keys.

Please do comment if you know or think that I misinterpreted anything or got anything wrong.


Is it possible to find a preimage for a reduced size hash?

We don't really know exactly how hard it is to find preimages of most cryptographic hash functions. Even for MD5 it is only "easy" to create collisions, while finding preimages is still considered "hard".

That said, we can apply statistical tools to estimate a "worst case", if we assume a random oracle for the hash function. In this case, we need in average $2^{255}$  tries to find a preimage to a 256 bit hash. Now, if we are looking only for a partial match (only 128 bits, it doesn't really matter which ones), we can estimate a match in average at $2^{127}$ tries.

Now, hash functions take an arbitrary input and map it to a fixed size output. There are no "preimages for M or K", there are just preimages (an input which maps to the same hash value). So once you found a preimage, you have this input. If the HMAC scheme requires a certain format of the input values for key, message and possibly other information, then you should only test inputs which fit this format.

To your second question: The attacker can not distinguish between the original message/key and any other preimage, if he has only the hash value (since they are the same). This might only be possible with additional information about the message: For example if the message is composed of English words in UTF8, preimages of random bits are not a "wrong preimage". However, in this case he would not even try this random input.

In general, the difference between HMAC and a cryptographic hash function is not that big. The difference becomes important, if the message is chosen from a small set of possible messages. In this case, the attacker can not just test all possibilities and find the real one, but he would have to test all messages with all keys (which should be larger than the hash value space). But in average, he will still find a preimage in 2^{k-1} tries for a k-bit hash value.

As final note: While $2^{127}$ possibilities is too much to brute-force, the security of this reduced hash value is less than the original one. Each ignored bit of the hash value cuts the complexity of finding a preimage by brute force into half. If you consider cutting down to something like every 4th bit of a 256 bit hash value (or any other fixed 64 bits of it), you get into the "possible to find with today's tools"-range. You have to ask yourself if this is worth saving a couple of bits for a potentially longer message, especially if you consider the other message overhead (e.g. IPv4 and TCP headers are each 160+ bits)


Surely bilinearity helps and and you have to be aware of the fact that $e(g^a,g^b)\cdot e(g^a,g^{-b})=e(g^a,g^b)\cdot e(g^a,g^b)^{-1}=1$.

You see that from your last equation
$$=e(g^{a\lambda_i}\cdot H(x)^{-v_ir_i},g^{u})\cdot e(g^{r_i}, g^{u't}\cdot H(x)^{v_i(u+\gamma)})\cdot e(g^{r_i}, g^{-tu'})\cdot e(g, H(x)^{v_i\gamma r_i})^{-1}$$

you get

$$=e(g^{a\lambda_i},g^u)\cdot e(H(x)^{-v_ir_i},g^{u})\cdot e(g^{r_i}, g^{u't})\cdot e(g^{r_i},H(x)^{v_iu})\cdot e(g^{r_i},H(x)^{v_i\gamma})\cdot e(g^{r_i}, g^{-tu'})\cdot e(g, H(x)^{v_i\gamma r_i})^{-1}$$

and by rearanging the terms a bit and using bilinearity, the fact that you have a symmetric pairing (switch arguments) and the fact mentioned above you will notice that only the first term remains and that is your desired result.


Name for crypto algorithm that preserves visual pattern

I'm not sure exactly what you're looking for, but one interpretation of your question is that you're looking for a way to 'hide' a message within a picture in a way that the picture isn't obviously changed.
The general technique to do this is known as "steganography"; that has the goal of hiding a message into something innocuous (such as a JPEG) in such a way that it's hard to discern (without the key) that there's a message there.  Steganography isn't an algorithm; instead, it is the general term for any algorithm that attempts to achieve this.
One common (and rather simple-minded) technique is to take the various bits of the message, and hide them within lsbits of various pixels the picture (tweaking the pixels only slightly); which pixels you use would depend on the key.
Standard joke: for more information, see the steganography stack exchange - just be warned, it is very well hidden...


No there isn't. First, OTP is private-key encryption scheme. Second, Asymmetric key is public-key encryption and No public-key encryption scheme can ever be perfectly secret. This is because the public-key (used for encryption) is available to everyone and is related to the secret-key in some way. Thus, a certain negligible amount of information is leaked. However, this leakage implies it isn't perfectly secure. So, No such thing as asymmetric OTP.


There are alternative representations of $GF(2^8)$ where the multiplicative inverse can be computed by computing the inverse in $GF(2^4)$, along with a handful of other operations (several $GF(2^4)$ multiplies, additions and a square).  Does your $\delta$ convert from the standard AES representation into such an alternative representation of $GF(2^8)$?

(Background: a representation is how we translate members of the abstract object known as $GF(2^8)$ into bitpatterns.  When we talk about, say, a prime field $GF(p)$, there's one obvious mapping between members of $GF(p)$ into the integers $[0, p)$, and it's hard to think of when another mapping would have any advantage.  However, when we talk about $GF(2^8)$, there are lots of plausible ways; different representations make specific operations cheaper.  The AES representation makes multiplying by the fixed element $2$ fairly cheap, at the expense of not giving an easy way of computing the multiplicative inverse).  Other representations make computing the multiplicative inverse cheaper.

Assuming that is what your $\delta$ is doing, the obvious way to compute the sbox is to do:

$$SBox(x) = AT(\delta^{-1}(Inv(\delta(x))))$$

That is, we translate the value into our alternative represention, compute the inverse in that representation, translate the value back into the standard representation, and then continue with the standard sbox computation.  You can compute the affine transform in the alternative represention; however it'll look like a random multiply by a fixed matrix, and be more expensive than the $AT$ in the standard representation).

If you feel like you have to compute the entire sbox in the alternative representation, then you can separate the affine transform into the linear multiplication $M$ and the constant vector $C$ (so $AT(x) = Mx + C$), and compute the values:

$$M' = \delta \times M \times \delta^{-1}$$

$$C' = \delta C$$

And so the operation $AT'(x) = M'x + C'$ is the affine operation entirely in the alternative representation.  However, as above, multiplying by $M'$ won't likely be as cheap as multiplying by $M$ (whose regular structure allows for a lot of simplification).


RFC4868 is not the HMAC RFC, which is actually RFC 2104. 4868 refers to the use of HMAC within IPSEC, which is why there is a key length restriction.

The maximum length key that can be used internally with HMAC-SHA256 is equal to the block size, 64 bytes or 512 bits. This can be useful in cases where the key is not full entropy such as the shared secret generated by a Diffie-Hellman key exchange; an ECDH secret of 512 bits has around 256-bits of security.

If the key length exceeds the block length, it must be first hashed to get it to fit within the block, this is the reason for the 70 byte test value, to make sure that implementations can properly handle it. The other lengths in the NIST vectors are one equal to the block length, and 2 arbitrarily shorter lengths. If an implementation can handle all 4 test values, it is generally safe to assume it can handle a 32-byte key as well.


Cyclic Groups Other than $\mathbb{Z}^*_n$ or Elliptic Curves

The multiplicative group $\mathbb{F}_{2^n}^{\ast}$ (which is cyclic) is used in defining LFSR sequences and nonlinearly filtered sequences typically as building blocks of stream ciphers.

This group is part of the picture for block ciphers; most prominently, the field $\mathbb{F}_{2^n}$ is used (for $n=8$) for defining the AES. Boolean functions and vector boolean functions defined over $\mathbb{F}_{2^n}$ also appear.


The key that was used in the AES/Rijndael for encryption is passed through a hash function

(strikethrough/strikeout mine)

That's OK if the hash function is secure and not vulnerable to timing attacks. Obviously MD5 is not a great option as it has been proven to be insecure. For this specific function however - similar to key derivation - it's OK. You should not be able to retrieve the key value as a hash is a one way function.

  I'll call this the key hash? This same value is used in both encrypting and decrypting. Then the encrypted data (from the AES CBC, and with the IV in front) is broken into chunks the same length of the key hash (blocks?). Each byte of the key hash is added to the encrypted byte, and then modulus-ed(?) (if > 255 then subtract 255).

This is basically a one-time pad where the key is repeated. Now normally it would be relatively easy to find the "hash" key with a known plaintext attack. With the ciphertext being properly randomized that is not possible. If however some part of the original AES/CBC ciphertext is ever leaked then the hashed key becomes known and the cipher can be reversed.

Basically this scheme doesn't add much security. It also shows a very limited understanding of cryptographic techniques and encoding methods. Because of this it should be seen as a risk, even if the scheme cannot be attacked directly. If MD5 is ever reversed you're in trouble. For now it is indeed a waste of bandwidth and processing time.

Furthermore, if you'd ever want to use hardware based encryption then the encryption key value will not be directly available (as the encryption operation is performed in the hardware itself). So it's probably not possible to perform MD5 over the key, making this scheme incompatible with hardware based security.

Finally, there seems a lot to be going on, but this scheme in all its needless complexity seems to miss an authentication tag. This means that an attacker may send you corrupted data that's still successfully decrypted. The attacker won't be able to simply inject any data, but it is possible to at least let the receiving party process garbage. In that sense the hash function could have been put to better use in a HMAC construction. In that case a SHA-2 hash such as SHA-256 should be preferred of course.


Safe and computationally efficient way to verify a curve25519 identity?

Yes, it is possible to authenticate using ephemeral-static Diffie-Hellman. You would however first trust the public key of the static key pair. One way to do this would be to put it into a DH-based certificate, signed with a CA. It's not so common because usually certificates are used to establish trust, and certificates commonly use a public key used for signature generation when it comes to authentication. Of course you cannot use ECDH to sign/verify certificates, so you'd be stuck with a different algorithm to verify a certificate, if you decide to go that way.

After you've trusted the received public key you can perform normal DH-key agreement, then use the resulting session keys derived from the established secret to perform HMAC authentication. Within this authentication you would need to make sure that the ID's are used, that the nonces are random, that the public keys are included etc. etc. So generally we make it ourselves easy and lift the handshake procedure from an existing, known secure protocol, as indicated in the comments.


How could an offline app verify a signature from one of many private keys?

You seem to be the person that is responsible for the private keys or at least the app. In that case you should look into PKI: public key infrastructure.

The most well known PKI infrastructure is that for TLS certificates. If you take a look at the certificate store of your favorite browser you'll see that there are no certificates there for your favorite services. Instead there is a set of trusted certificates of different certificate issuers. These are used to sign other certificates, in the end one of these certificates is the certificate of the end user, in this case a web server. This end-user is certificate is called a leaf certificate. The first certificate in the chain is called a root certificate. The certificates together look like a certificate tree.

The idea of a PKI is that the public key is part of the certificate. In the end this public key is trusted because there is a chain of certificates leading to a certificate that is trusted.

So you should become your own CA: you will create a self-signed root certificate, which is shipped with (and therefore trusted) by your app. You sign other certificates using the private key that is part of the key pair for the root certificate. Now the users can use their private key to create a signature, and have that signature be accompanied by the certificate that contains the public key of the user. Once that certificate is trusted by chain verification to the root certificate, the public key is trusted and can be used to finally verify the signature.

Generally PKIX is used, which uses a specific type of certificates called X.509 certificates. There is pre-made software that can be used to create certificates. An example is openssl ca.

The difficulty with your approach is not the security - public key or certificate pinning is a valid approach. The problem is the management: each time you add a key you need to update all your software. That is not the case if you can verify a certificate chain, only one certificate needs to be trusted. A certificate can also contain things such as identity, issuer, validity period, key usage and more.

Note that revoking a certificate or public key can be more tricky. You may need e.g. an Online Certificate Revocation Status protocol server so certificates and public keys can be trusted to be still valid.


If all encrypt algorithms in TLS1.3 ciphersuites are AEAD , why do they keep including a Hash algorithm?

From RFC 8446, the hash is used for:

The transcript hash, covering every message in the handshake to authenticate it during key agreement and certificate verification (§4.4.1).
Deriving various session keys from raw key agreement material and transcript hash with HKDF (§7.1).
Deriving key material for protocols based on the key negotiated in a TLS session (RFC 5705).


There are at least two different criteria for message encoding into fixed-size blocks:

no input has its encoding equal to the encoding of any other input;
no input has its encoding at the tail end of the encoding of any other input.

Criterion 1 is often used together with block ciphers for encryption or Message Authentication Codes. Usual padding techniques meeting it:

Bit padding, also known as ISO/IEC 9797-1 Padding Method 2. We append a single 1 bit to the message, then just as many 0 (possibly none) until filling a block.
Various forms of byte padding, applicable to messages already formatted as bytes (octets); most often, if the message is $n$-byte and a block is $b$-byte, it is added $p=n-(n\bmod b)$ byte(s) (thus $0<p\le b$), the last of which having value $p$; there are various conventions for the other added bytes: $0$ (ANSI X.923), $p$ (PKCS#7), random, or just unspecified.

Criterion 2 is stronger than criterion 1. It is sometime used for hashing, especially by iterating a one-way compression function, where this criteria strengthens the hash against some attacks (see this answer). A common implementation is:

Append a single 1 bit to the message (this step is customary, but has no justification AFAIK).
Append just as many 0 (possibly none) until there remains exactly $s$ unused bits in the message, for some fixed parameters $s$ (the message must have size less than $2^s$ bits); common choices are $s=64$ (MD5, SHA-1, SHA-256) and $s=128$ (SHA-512).
Append $s$ bits (thus filling the last block) coding the length of the message in bit (before padding), under some prescribed endianness convention; MD5 uses little-endian, SHA-1 and SHA-2 use big-endian.

I fail to track the original reference for criterion 2 (much less its common realization); it does not seem to be quite this way in: Ivan Bjerre Damgård, A Design Principle for Hash Functions, in proceedings of Crypto 1989; nor in its reference: Ralph C. Merkle, One Way Hash Functions and DES, in proceedings of Crypto 1989.


GCM mode and the order of AAD and plaintext

To extend Conrado's answer, there are three possible ways you might mean ordering:

The order of things location within memory
The order you present things to the GCM implementation
The order of coefficients within the GHASH polynomial

As Conrado mentioned, it doesn't matter where things appear in memory.

And, the order of coefficents are defined within GCM; change the order, and you're no longer doing GCM.  It might be secure (depending on the details of your new scheme), but it's not GCM

On the other hand, there are tricks that allow you to process things in a different order than how they appear in the polynomial.

For example, you can rearrange the GHASH polynomial to be:

$$(A_a H^a + A_{a-1} H^{a-1} + ... + A_0 H^0) H^{m+3} + \\ (M_m H^m + M_{m-1}H^{m-1} + ... + M_0H^0)H^2 +\\ TH$$

(where the AAD block is $(A_a, A_{a-1}, ..., A_0)$, the message is $(M_m, M_{m-1}, ..., M_0)$ is the message and $T$ is the block containing the AAD and message lengths)

With this formulation, you can process the AAD and the message independently, and combine them at the end.

Standard libraries don't implement this, but it certainly could be done.


Is an HMAC based on a second-preimage resistant hash function always unforgeable?

Even collision resistance is not sufficient to make HMAC unforgeable, so neither is second-preimage resistance.
Let $H : \{0,1\}^* \to \{0,1\}^n$ be a collision resistant hash function. We define the hash function $H' : \{0,1\}^* \to \{0,1\}^{n+1}$ as
$$H'(m\Vert b) = H(m)\Vert b,$$
where $|b|=1$.
Since for any $m_0\Vert b_0$ and $m_1\Vert b_1$, it holds that $H'(m_0\Vert b_0) = H'(m_1\Vert b_1)$ if and only if $b_0=b_1$ and $H(m_0)=H(m_1)$, it is easy to see that any collision in $H'$ implies a collision in $H$. Thus $H'$ must remain collision resistant.
However, HMAC instantiated with $H'$ is easily forgeable.
\begin{align}
\mathsf{HMAC}(K,m\Vert b) =& H'\Bigl((K\oplus \mathsf{opad})\Vert H'\bigl((K\oplus \mathsf{ipad})\Vert m\Vert b\bigr)\Bigr)\\
=&H'\Bigl((K\oplus \mathsf{opad})\Vert H\bigl((K\oplus \mathsf{ipad})\Vert m\bigr)\Vert b\Bigr)\\
=&H\Bigl((K\oplus \mathsf{opad})\Vert H\bigl((K\oplus \mathsf{ipad})\Vert m\bigr)\Bigr)\Vert b\\
\end{align}
I.e., an adversary can take the tag $t$ for some arbitrary message $m$, and present $(m\oplus 0\dots01,t\oplus 0\dots01)$ as a valid forgery with probability $1$.


How to show CPA attacker does not need access to encryption oracle after receiving cyphertext

"You can prove that for every polynomial time attacker that uses the encryption oracle after receiving the challenge cyphertext, you can construct another polynomial attacker that also breaks the encryption scheme only querying the oracle before receiving the challenge cyphertext."

Actually, that is not true in general; you need to make further assumptions on the encryption method.  Presumably, the lecture gave these further assumptions.

One counterexample to the general statement is a self-inverse cipher, that is, one for which $E_k(E_k(M)) = M$.  It is obvious, given $E_k(M)$ and an encryption oracle, how to recover $M$ with a single query.  However, if there are no further weaknesses, there is no useful way to generate queries before you see the challenge ciphertext $E_k(M)$.


Ensuring that an operation takes a relatively specific amount of time, but easily verify the result

Timelock puzzles solve this problem.

For instance, consider the function $f(x) = x^{2^t} \bmod n$, where $n$ is a RSA modulus and $t$ is large.  For people who don't know the factorization of $n$, computing $f$ takes $t$ squarings modulo $n$.  If you do know the factorization of $n$ (the private key), then computing $f$ can be done with $O(\lg n)$ squarings, regardless of how large $t$ is, by first reducing $t$ modulo $\varphi(n)$.  This lets you create a puzzle that will take a controllable amount of time for someone else to solve, and where you can very efficiently verify the answer: e.g., choose $n$ to be a 2048-bit prime and $t$ to be a million, or whatever you want $t$ to be to make computing $f$ take exactly as long as you want for the other person.

See, e.g., Time Capsule cryptography? and Parallel-resistant proof-of-work scheme? and What is the progress on the MIT LCS35 Time Capsule Crypto-Puzzle?

If you want a proof of work puzzle that requires the other person to do 30 seconds of work, I don't see any practical reason to worry much about quantum computers.  Right now there are no quantum computers that could pose a serious threat to this scheme.  If they ever become possible, you can always change the scheme out.  The scheme only needs to be secure for 30 seconds, not for 30 years....


Why derive keys from a master key instead of generating random keys?

Here are various advantages.  Maybe they don't all apply in this case—I don't know, but there are cases in the real world in which they do apply.

Test vectors.  You can write known-answer tests for your entire cryptosystem, end-to-end.  You can verify these test vectors in a power-on self-test to cheaply detect catastrophic failure.  You can easily use these test vectors to debug an interoperable alternative implementation during development.
Reproducible subcomputations.  If you need to add a branch to a tree of subcomputations with an independent key, you can simply use a distinct label for the HKDF info parameter, and all the other computations will remain unchanged.  That way, e.g., you don't have to update your test vectors, whereas you would have to if you drew keys out of a sequential PRNG.
Reduced storage.  You only need to store as many keys as there are independent privilege domains in your system.  You can simply rederive any subkeys for different purposes within a privilege domain instead of having to store them separately.
Reduced reliance on entropy sources.  You can flash a key onto an embedded microcontroller, and use it to derive subkeys for various purposes, and even rotate keys and erase old ones, without having to rely on an entropy source on the microcontroller itself.


How does this happen in RSA malleability?

As mikeazo notes in the comments, RSA operates on the ring $\mathbb Z / n\mathbb Z$ of integers modulo $n$, for a given modulus $n = pq$.  In this ring,

$$E(m) \cdot t^e \equiv m^e \cdot t^e \equiv (mt)^e \equiv E(mt)\ \pmod n.$$

In particular, for $n =  35$, $e = 23$,

$$17^{23} \cdot 2^{23} \equiv 33 \cdot 18 \equiv 594 \equiv 34 \equiv 34^{23}\ \pmod{35}.$$

The notation in your question,

  "$E(m) \cdot t^e \bmod n = (mt)^e \bmod n = E(mt)$",

apparently using $\bmod$ as a modulo operator, is somewhat confusing here, although it's technically correct if you interpret the left hand side as "$(E(m) \cdot t^e) \bmod n$".  I would much prefer the notation I've used above, which makes it clear that we're doing all arithmetic in the ring $\mathbb Z / n\mathbb Z$, and that we're thus free to reduce (or not to reduce) intermediate values modulo $n$ any time we want.


Find encryption algorithm knowing input, output and secret

Chances of finding the algorithm

It is relatively unlikely that you will find an answer. Ciphertext itself has been designed to be indistinguishable from random bytes (well, for modes based on block ciphers anyway).

The Kerckhoff's principle indicates that the encryption algorithm should not be depended on to keep the plaintext secret. But that doesn't mean that it is necessarily easy to find the algorithm; if the algorithm is used as as secret it may be impossible to find. Kerchhoff just states that it is unsuitable as a key because it will likely be leaked.

Although encoding modes, modes of operation, padding modes and ciphers have been standardized, there are a lot of them and the complexity of finding an exact match rises quickly, and you don't even know the key used.

Of course, if you don't have any experience doing this your chances decrease, as it is easy to make mistakes and e.g. overlook a possible solution or correct answer.

If a modern cipher was used

As a header is missing, it seems you're dealing with a file that is directly encrypted. AES is always a pretty good bet, and the mode is probably that of a stream cipher (CTR, CFB) as ECB and CBC would add padding. CBC ciphertext stealing is hardly used and requires at least one block, while files can be any size. Encryption / container protocols such as OpenPGP/ZIP/whatever can be safely skipped as they would expand the file size.

The really tricky part is how the password was transformed into a key. Normally you would use a PBKDF - a password based key derivation function - to derive a key from a password. However, a PBKDF requires a salt and iteration count. Generally those are stored with the ciphertext, but as your ciphertext size did not expand on the plaintext size, the salt is missing in action, making PBKDF less likely. You could try AES using the password directly as a key, extended with zero's on the right hand size.

Generally modes require an IV, so you may want to try an all zero IV instead of the normal one. Obviously the IV is not prefixed or, indeed, the ciphertext size would have expanded.

When trying to find the algorithm compare the beginning 8 bytes of the file, decrypting e.g. 32 bytes. Do not use padding when decrypting, as that will simply fail. If you have a match then use that information to continue.

Some other legacy options

As this is clearly not a standardized format the encryption can be literally anything, including classical ciphers. I'd certainly try e.g. the Vigenère cipher, using XOR with a repeated password in ASCII.

Another option is e.g. (PHP) mcrypt in ECB / CBC mode using two-key triple DES. Expand the key to 16 bytes by adding zero bytes at the end and then decrypt with an all zero IV. Blowfish, another 64 bit block cipher, may also be an option. Some bad libraries such as mcrypt do not pad if the plaintext is a multiple of the block size, and your (encrypted) image size is a multiple of 8 bytes (64 bit), but not 16 bytes (128 bit).

Trying RC4, another common cipher, could also be a good idea. It is a stream cipher that takes a key of configurable size. It doesn't take an IV; the key is supposed to be random each time (generally this can be established by simply concatenating the original key bytes and the IV bytes and use that as a key).


WPA/WPA2 Handshake -- Why are Nonces not encrypted?

Unfortunately, that wouldn't really achieve much. To see why, let's first recall the steps of the common dictionary attack on WPA/WPA2-PSK.

In WPA/WPA2-PSK, the key hierarchy goes like this:

password - this is the fundamental secret in the entire protocol, and all other keys are ultimately derived from this. Thus, the security of the protocol essentially boils down to the secrecy of this value.
PMK = PSK = PBKDF2(password, SSID, SSID-length, 4096, 256).
PTK = PRF(PMK, "pairwise key expansion", MAC1 || MAC2 || Nonce1 || Nonce2). The exact PRF that is used here is not important, but it is based on HMAC-SHA1.

Notice that as an attacker, if you know the password, then you have all the information you need to first derive the PMK (since everything else that goes into the PBKDF2 function is public), and then the PTK (since the MACs and the nonces are public). This, then, leads to the well-known dictionary attack: make a guess on the password, derive from this guess the PMK and PTK, then use the PTK on some of the captured data to verify your guess (e.g. by recomputing one of the message-authentication codes of the 4WHS). If the verification didn't check out, try another guess on the password.

Now, with your suggestion, the nonces wouldn't immediately be observable in the clear. However, this would only change the above attack slightly: again the attacker makes a guess on the password and derives the PMK as before. However, now it cannot immediately continue to derive the PTK, since it doesn't have the nonces. But this is not a problem, because the encryption of the nonces only depends on the PMK, which it now has a guess for. Thus, using this guessed PMK, it simply decrypts the encrypted nonces, and continues the attack as before, deriving the PTK and verifying the guess on the captured data. If the guess of the password was correct, then the attacker will obtain all the correct data and the final verification will check out. While if the guess was wrong, the final verification will most certainly fail.

Thus, the attack is more or less the same, just with one added step requiring the decryption of the nonces. Moreover, the only computationally intensive calculation being done here is the evaluation of the PBKDF2 function. The time needed for the extra decryption of the nonces dwarfs in comparison to this.


Differential privacy basics: Universe \mathcal{X} and database $x$

I am a little late. Your understanding seems correct. $\mathcal{X}=Names \times \{0,1\}$ Where $Names$ are all the possible names that could exist and $x \in \mathbb{N}^{2}$ (Because of $|\mathcal{X}|=2$).
Then you can choose one column and select the histogram of the type you want. Then you can express $x=(x_0,x_1)=(3,3)$ or $x=(x_{ross},...,x_{Rachel})=(1,..,1)$. A you see the first one is more convenient.


KCV and compatibility with block cipher modes of operation

I've thought quite a lot about this, and I think in general the answer is no, it would not be a good idea to use a KCV for those kind of situations. Using a hash or even better a MAC (using the key as MAC Key) would be a much better idea when a KCV is required. Instead of zero's, it would be much better to use a previously random (block of) bytes that is not likely to be of use to an attacker.

You could of course wonder if all zero input should be used for CMAC and counter mode. For CMAC is would be very easy to use another constant value. For CTR mode it is probably best to always increase the counter before it is used; one way would be to simply start with value 1. It would be easy to define a protocol that specifies the nonce / IV / counter that way.

Using a KCV for keys can be very useful for key management - it certainly saved the company I worked for a lot of time.

For CMAC mode it is easy to show that the KCV returns part or all of the keys...

Calculate a temporary value $k_0$ = $\operatorname{E}(k,0)$.
If $\operatorname{msb}(k_0) = 0$, then $k_1 = k_0 \ll 1$, else $k_1 = (k_0 \ll 1) \oplus C$.
If $\operatorname{msb}(k_1) = 0$, then $k_2 = k_1 \ll 1$, else $k_2 = (k1 \ll 1) \oplus C$.
Return keys $k_1$ and $k_2$ for the MAC generation process.

These keys in turn are used for the last block of the CBC mode encryption that underlies CBC-MAC, which is used to build up CMAC. Now it seems that this would reveal the last block to an attacker before it is encrypted.

Now comes the tricky part, I'm not sure if this negates the security added to CBC-MAC to create CMAC, but it doesn't look good.

As for CTR mode, it is clear that you can directly decrypt (part of) the first block of the ciphertext if you have a nonce (and counter) set to all zeros. You cannot get a more direct attack than that.


Why is asymmetric cryptography bad for huge data?

There are two main reasons why asymmetric cryptography is practically never used to directly encrypt significant amount of data:

1) Size of cryptogram: symmetric encryption does not increase the size of the cryptogram (asymptotically), but asymmetric encryption does. If we take the example of RSAES-OAEP in PKCS#1v2 with a 1024-bit key and 160-bit SHA-1 hash, a 1024-bit cryptogram can convey a maximum of 688 bit of useful information. Thus data enciphered in this way would cost 49% more space to store, or more time to move over a given link.

2) Performance: on a modern CPU with hardware AES support, encryption or decryption speed is over 2000 megabyte/second (per core); while decryption of a 1024-bit cryptogram in the above scheme can perhaps run at 4000 per second (per thread of a comparable CPU), thus a throughput of 0.4 megabyte/second, 5000 times slower; that's also moreless the ratio of power usage. That ratio tends to get even worse as security increases. While there are more efficient schemes, it is safe to say that a symmetric scheme is orders of magnitude faster and less power hungry than an asymmetric one, at least for decryption (some asymmetric schemes, including RSA with low public exponent, are considerably faster on the encryption side than they are on the decryption side, and can approach the throughput of some symmetric cryptography).

Addition: Asymmetric Cryptography does not "need data smaller than its key length". For example, the public key in an RSA scheme can be reduced to about half the cryptogram / modulus size by fixing high-order bits of the modulus $n$, and setting $e$ to a fixed value, thus can have a cryptogram nearly double the public key size. The private key can be compressed even further, ultimately to the seed of a PRNG.

BUT...  In practical terms, we needn't use these tricks to make the data look smaller than the key size.  This is because it is simple to use hybrid encryption; we pick a random Symmetric key, encrypt that key with the public key, and then use the Symmetric key to encrypt the data.  With this approach, we can handle an arbitrary sized data using any public key encryption method.

However, any public-key encryption schemes is bound to increase the size of the data that it enciphers: if it did not, there would be a single ciphertext for any given plaintext, and thus an adversary could test if the plaintext is a certain value, simply by enciphering that value (using the public key) and comparing to the ciphertext. Public-key encryption schemes typically increase the cryptogram size by $k$ bits to resist such attack with a strength of $2^k$ encryptions.


looking for BKZ earliest algorithm and its application in cryptography

BKZ was described in Lattice basis reduction: improved practical algorithms and solving subset sum problems by  C. P. Schnorr, M. Euchner in 1994. As the title suggests, it was first used for solving the subset sum problem.
https://academic.microsoft.com/paper/2126483728


MAC in SSH packet encryption, benefits to not including it?

The MAC is NOT redundant.

As alluded to by Paŭlo Ebermann's comment, the word authentication has a different meaning in the two scenarios you mentioned.

In the key exchange phase of SSH, the purpose of authentication is to ensure to both parties that they are indeed talking to the right peer (if using mutual authentication). Typically, the server authenticates itself using its public key and the client uses a username and password.

In the SSH record layer phase (i.e., the sending of the actual application data), the purpose of authentication is to protect each individual data packet from tampering. This is achieved using the MAC. To encrypt application data SSH typically uses either AES in counter mode or in CBC mode. Neither of these modes of operation provides protection against tampering of the ciphertext. Thus they need to be accompanied with a MAC in order to detect this.

Consider e.g., the silly example where Alice sends the following message encrypted using AES in counter mode, but without any MAC:
Transfer 100 USD from Alice to Bob. Then someone (Bob?) could flip a few strategically placed bits in the ciphertext, so that it would actually decrypt to Transfer 10 000 USD from Alice to Bob. instead. Note that without any MAC, it would be impossible for the recipient to notice that this ciphertext had been tampered with. Also, observe that this fact is completely independent of any key exchange that has been done prior to the tampering.

There is of course one obvious "advantage" to skipping the MAC: you save the 80-128 bits of overhead needed to transfer it for each data packet you send. But this is not safe and should not be done!


Does Shamir's Sharing Scheme make sense if k=2 and n=2?

Except for the extensibility (being able to latter add a third user), the trivial scheme with XOR works just as well as Shamir; the trivial scheme retains the following properties:

The length of each share is still as long as the original secret (in fact, you don't need to bother assigning share identifiers, which you have to with Shamir's scheme)
It is information theoretically secure.


Is it hard to find a big random easy to factor number?

Yes, this is feasible. Just generate sufficiently many nonce, rnd values, and you will eventually stumble upon a prime (or a number that can be factored into a large prime and a number of small prime factors). This is how most probabilistic prime generators operate.


At what modulus size does the logjam reduction stage become impractical?

It is hard to put concrete costs to these steps at this scale, and the parameters can be tweaked to make the precomputation more expensive to render the individual log cheaper, but we can try to do it asymptotically to get an idea. The complexity of the precomputation step is
$$
L_p[1/3, 1.923] = \exp\left((1.923 + o(1)) (\log p)^{1/3} (\log \log p)^{2/3}\right)\,,
$$
which in the case of a 1024-bit prime field—and assuming $o(1) = 0$—would amount to roughly $2^{86}$ operations$^1$.

The individual logarithm, on the other hand, has a smaller complexity of
$$
L_p[1/3, 1.232] = \exp\left((1.232 + o(1)) (\log p)^{1/3} (\log \log p)^{2/3}\right)\,.
$$
Once again, if assuming $o(1) = 0$ we would need a roughly $2900$-bit prime for the individual log step to match the cost of the 1024-bit precomputation. The precomputation step for $2900$ bits would be beyond $2^{128}$ operations.

$^1$ This complexity figure often ignores memory and storage costs, which as numbers grow becomes more and more important, but this is a rough approximation anyway.


What are the properties of a function based on multiple iterations of a pseudo-random permutation?

It is neither, because you're only talking about a fixed function—it's not even the right type of object to be a PRF or PRP.  Keccak-f[1600] is not a pseudorandom permutation family itself; it is a single fixed permutation.  A PRF or a PRP is a family of functions indexed by a key, such that a uniform distribution on keys induces an apparently uniform distribution on functions or permutations in some space.


Prove that a given encryption scheme is perfectly secret

For every key $k \in \mathcal K$ $$Dec(Enc(m)) \overset{\underset{\mathrm{def}}{}}{=} (Enc(m) - k) \bmod 4,$$ where $$Enc(m) \overset{\underset{\mathrm{def}}{}}{=} (m + k) \bmod 4,$$ so, combining it, we have $$Dec(Enc(m)) = (((m + k) \bmod 4) - k) \bmod 4,$$ which, by properties of modular arithmetic (or, more precisely, congruences), is equivalent to $$(m \bmod 4) + (k \bmod 4) - (k \bmod 4) = m + k - k = m$$
This is actually a great example, as it demonstrates the ultimate elegance of the mathematical definition of security. Encryption scheme $(E, D)$ over $(\mathcal K, \mathcal M, \mathcal C)$ is perfectly secret, if for all $m_i, m_j \in \mathcal M, c \in \mathcal C$ $$Pr[E(k, m_i) = c] = Pr[E(k, m_j) = c],$$  where $k$ is uniform in $\mathcal K$. Here is a table of encryptions of $m$ with key $k$ for all $m \in \{0, 1, 2, 3\}$ and $k \in \{0, 1, 2, 3\}$:
$$
\begin{array}{c|lc}
m/k & 0 & 1 & 2 & 3 \\
\hline
0 & 0 & 1 & 2 & 3 \\
1 & 1 & 2 & 3 & 0 \\
2 & 2 & 3 & 0 & 1 \\
3 & 3 & 0 & 1 & 2
\end{array}$$
As you can see, for every $m$, $Pr[Enc(m) = c] = 1/4$, thus given encryption scheme is perfectly secure.


Why are only lattice problems used in cryptography?

What makes a problem suitable for cryptography is slightly different than what makes a problem NP-hard.

What is required for cryptography is average-case hardness --- i.e., a randomly selected instance of a problem should be "hard" for an adversary to solve. However, random instances of some NP-hard problems (3SAT, e.g.) turn out to be easy with high probability.

Lattices are interesting as some of its average-case hard problems (ex. Shortest Integer Solution, SIS) allow a reduction to worst-case hard problems (ex. Shortest Independent Vector Problem, SIVP) --- i.e. solving a random instance of one problem is as hard as solving worst-case instance of another. No efficient quantum algorithms are known against these problems either.

Moreover, lattices have enough underlying algebraic structure which allows building cryptographic primitives (OWFs, Trapdoors, FHEs...) based on these hard problems --- see the survey by Peikert.


Is there any use for PBKDF with empty password?

While it might be possible to use an empty password, the reason for that is most likely that any exclusion would also be known to the attacker.

However, I wouldn't call it an important test case. A PBKDF does not protect from choosing bad passwords, it only makes the dictionary attack take a lot more computational effort. If one of the first guesses is correct already, no password-based KDF will protect against that. And if the empty password is allowed, it surely is quite high in that list.

Alternatively, they could have just overlooked that case. Or they decided against it. Only the authors might be able to answer your question with certainty.


Encrypting current time using 3DES as a signature

Probably Not

Simplifying the discussion, one-block CBC with a null initialization vector reduces the mode to ECB.

Seeing that most time stamps are less than or equal to 8 bytes, only one block should be used (maybe two if there is a padding scheme).

There currently aren't any known algorithms for ECB forgery (as far as I'm aware), so I'd say it's unlikely.

However, this scheme could theoretically be susceptible to a brute-force attack.

If the time window were one day, the search space would only be about 48 bits (2^16 seconds being roughly one day).

Practically, this is an unrealistic attack, (and requires the server to ingest approximately 2.25 Petabytes of data), but it's feasible within an order of magnitude, which is not usually desirable.


Could a very long password theoretically eliminate the need for a slow hash?

Despite the impracticalities of using a 43-char password, I would say yes, such a long password would be secure when hashed with just SHA256.  Assuming 127 possible ascii characters, a password of 8 characters would require an attacker to search about 2^56 possibilites (viable), whereas a password of 43 characters would require searching about 2^300 possibilities (infeasible, considering that 2^128 for encryption using a 128-bit key is infeasible). Having such a long password would make a slow-hash redundant.  With the case of a 43-character password, I doubt that rainbow tables would be issue either.


Cycles per byte means the number of CPU cycles that must elapse in order to process a single byte of input for a specific processor. A CPU's clock frequency determines how many cycles per second the processor is running at (for example, 2.6 billion per second for a 2.6 GHz processor). Note that this is a rather crude type of benchmark, because the bottleneck may not be waiting for each instruction to retire. Memory access latency, shared resources, etc. can slow things down.


Where does one store 3rd-party Public Keys

From a security point of view, you can store the public key wherever you want, as by definition it is public. This doesn't hold for the private key, which has to be store securely, as the security depends on it.
As pointed out by @fgrieu (in the comment below), the integrity of both public and private keys should be ensured. In other words, it should be ensured that no adversary can change the public keys. Therefore, you might consider also storing the public keys in a key store which should make it a lot harder for an adversary to tamper with it.

From an efficiency point of view, it really depends on what platform you are using. Of course you can store the public keys also in a key store (as a key store most likely offers some other useful functions). However, you can also just store the public keys in a database or the file system. Regarding the encoding (storing them as plaintext strings, hex strings or any other encoding) it again depends on your platform. You might have a look at this link.