Is the HNF basis the worst basis for a lattice?

Whether an algorithm succeeds or not for solving e.g. CVP depends on the quality of the basis, which for instance can be measured in terms of the sum of the norms of the basis vectors. Your question could therefore be interpreted as: does the HNF give you the basis of the lattice with the worst quality?

The answer has to be no to this. Suppose w.l.o.g. that the lattice lives in $\mathbb{Z}^n$, and the sum of the norms of the basis vectors of the HNF basis is $M$. Now clearly there can only be finitely many bases of the lattice for which this quality measure is less than $M$, as we can just enumerate all possible such bases. On the other hand, there are infinitely many bases for each lattice, and so there must be a basis with even worse quality. It all depends on how you define "quality", but for most sensible definitions there is no "worst quality" - you can always get a worse basis.

More concretely, given a basis matrix $B$, you can obtain another basis $B' = U \cdot B$ by multiplying $B$ with any unimodular matrix $U$. By taking a $U$ with huge entries, $B'$ will likely be a much worse basis than $B$.


You'll probably know this relation, which should be obvious if you think about it:

$$(a \bmod n) + (b \bmod n) \equiv a + b \mod n$$

This means that when using addition you do not have to reduce the operands, only the final result. However, if the final result is an operand again it needs not be reduce. This means that long chains of modular additions can be computed using normal additions with one reduction at the end.

You can see $a\times n$ as a series of additions:

$$a\times n = \overbrace{
    a + \cdots + a
   }^{n \text{ times}}$$

You can see $a^b$ as a series of multiplications:

$$a^b = \overbrace{
    a \times \cdots \times a
   }^{b \text{ times}}$$

So we can see $a^b$ as a very long series of additions of the base. Thus we do not need to reduce the base:

$$(a \bmod n)^b \equiv a^b \mod n$$


IV Re-use and Chosen Plaintext against 56bit Blowfish (CBC)

No.

You're already assuming that chosen plaintext attacks should be considered. A known IV together with your ability to arbitrary encrypt known plaintexts is enabling exactly that attack vector to the block cipher. These attacks are all attacks on the block cipher, and Blowfish is considered rather secure, if deprecated because - among others - the block size. A mode of operation cannot influence the security of the block cipher itself, and CBC is still considered a secure mode of operation when it comes to storing data confidentially.

What you can do is attack the cipher or protocol in different ways. You say that Blowfish is used to encrypt packets, so it could be that CBC/PKCS#7 based padding oracle attacks apply. If no message authentication has been performed a lot of other plaintext oracle attacks could also become available. If the authentication is optional you can always try padding oracle attacks while leaving the authentication out (this seemingly idiotic strategy used to work against Web-security frameworks). There are quite a surprising number of attacks to transport security, so if they still use Blowfish you can almost be sure that it is not completely secure.


What is the purpose of key strengthening?

The sources of that Wikipedia article show that the article describing key strengthening by Manber (adding a subsequently deleted salt) is from 1996, two years before the 1998 article that is given as the origin for key stretching describes (adding more iterations).

The idea there seems to have been to use the existing crypt() password hash exactly as-is, and make any modifications outside of it. From the Manber paper, p.5:

  The implementation of this scheme is very easy. In particular, all
  changes are made as an extra filter to the login procedure, without having to modify the encryption
  mechanism at all.

Remember that the original crypt() didn't have any means for setting the number of rounds, but was completely fixed. (It also didn't support password longer than 8 characters, so they couldn't just append the salt, but had to apply it by "scrambling" the password with the secret salt.)


Is SSL getting faster because it's getting less secure?

There are several effects coming into play. But the most important property is that with increasing keylengths, the attacker's work becomes exponentially expensive, whereas the defenders work only becomes slightly more expensive.

Looking at the different kinds of cryptography in use:

Symmetric cryptography

Originally we used DES and 3DES. DES had a dangerously small key and decent performance. 3DES had a secure keysize, but bad performance (3 times as slow as DES).

So AES was developed which has very good performance and secure key sizes. AES-128 is secure against brute-force for a long time and AES-256 is secure against brute-force using conventional and quantum computers forever.

So unless there are major advances in crypto-analysis, there is no reason to use symmetric cryptography slower than AES-256, no matter how fast the attacker's computers get. AES performance becomes significantly better on the current generation of processors, which offer specialized instructions.
RSA used in the key-exchange

The defender's cost grows with the key-size to the third power. The attacker's cost growth much faster, but doesn't double with each bit. So we need to increase key-sizes somewhat to compensate for the increased computational power of attackers. For example 1024 bit RSA keys are currently being replaced by 2048 bit keys, because cracking them will become possible soon.

Still the defender's advantage grows as computers get faster.
Better asymmetric algorithms

Elliptic curve cryptography is much faster than RSA. Currently it doesn't get used much for authentication in SSL, only for the ephemeral key-exchange using ECDHE suites. But in principle they allow a 128 bit security level with better performance than 1024 bit RSA keys.

In general modern cryptography is at a level where brute-force is no longer a threat for most schemes. The main trade-off is performance vs. how resilient to crypto-analysis the ciphers are. But even there we're only talking about a small constant factor that doesn't scale with computational power.

Unless there are major advances in crypto-analysis or computer science in general, I expect the processor cycle cost of cryptography to remain approximately constant. This means that effectively it'll get faster at the same rate as our processors.

In particular that means that the hand-shake costs effectively becomes much cheaper as computers get faster, whereas encrypting the connection itself will stay at a constant cost, assuming bandwidth (and thus the amount of data) and processor speed increase at the same rate. Luckily symmetric encryption is already very fast, especially on processors supporting specialized AES instructions (more than 1GB/s on a single core). Generating dynamic webpages is typically more expensive than encrypting them afterwards.


How exactly are public and private keys used to encrypt and the decrypt data?

Here is a numerical example with RSA.
(Edit and warning: as fgrieu notes in the comment, these values are strictly for illustrating the math involved; all of the parameters are unsuitable for actual use. See the answers here for discussion about how to properly choose the primes $p$ and $q$, and here about secure RSA key sizes.)
Quoting the relevant parts:

The first step of RSA encryption is to generate two primes, $p$ and $q$.
$$p = 257$$
$$q = 337$$
The product of $p$ and $q$ is $n$, in our case:
$$n = 257\cdot 337 = 86609$$
The euler totient, $\phi(n)$ is calculated below:
$$\phi(n) = (p-1)(q-1) = 256\cdot 336 = 86016$$
Now we have to chose an exponent, $e$ that is relatively prime to $\phi(n) = (p-1)(q-1)$. The pair $(e, n)$ is our public key that is used to encrypt messages.
$$e = 17$$
$17$ is relatively prime to $86016$ because they share no factors. We know this because $17$ itself is a prime number, so its only factors are $1$ and $17$. $9113$ is not divisible by $17$, so the numbers are relatively prime.
Our next step is to calculate a value for $d$. If you recall from the RSA algorithm, $d$ must be chosen so that it is the inverse of $e$, modulo $n$. So for our example, we must find a number such that:
$$e\cdot d \equiv 1 \mod \phi(n)$$
$$17 \cdot d \equiv 1 \mod 86016$$
To solve for d we use the Extended Euclidean Algorithm which can be used to find multiplicative inverses.
Using the Extended Euclidean Algorithm, we can calculate one possible value for $d$ is $65777$. We can check the algorithm by computing  $e*d \mod \phi(n)$ and ensuring it equals $1$.
$$e\cdot d \mod \phi(n) = 17\cdot 65777 \mod 86016 = 1118209 \mod 86016 = 1$$
$d$ is our private key and is used to decrypt our messages. Now that we have both a public key and a private key, we can encrypt and decrypt messages.
$$\hbox{Pub } = (e,n) = (17, 86609)$$
$$\hbox{Priv } = (d,n) = (65777, 86609)$$
To encrypt a message m, we first convert it into a large integer. Then we calculate m^e \mod n. The result is the encrypted message, or ciphertext, $c$. Let’s send the text “Hi”. In order to do this, we must convert the message into an integer. We’ll use the integer $18537$ to represent our text.
$$c = m^e \mod n$$
$$c = 18537^{17} \mod 86609 $$
$$c = 12448$$
Now, can we decrypt $12448$ back into the original message, $18537$? To decrypt a message we use the private key, $(65777, 88609)$
$$m = c^d \mod n$$
$$m = 12448^{65777} \mod 86609$$
Here we use the Chinese Remainder theorem, an easy way to solve $a^b \mod n$
$$m = 18537 \mod 86609$$
Indeed, when we perform decryption on our ciphertext, we are left with the original message.

One more thing:

It's my understanding that public keys are generated from the private key using a one-way, or trapdoor function

Not always. In Diffie-Hellman key exchange, you start with a private value $x$ and generate $g^x \mod p$ as a public key, given suitable $g$ and $p$ (and are known to the public). However, for RSA, you pick secret primes $p$ and $q$ and from that generate the public key $(N=pq, e)$, such that $\gcd(e, (p-1)(q-1)) = 1$. And from that you can derive the decryption exponent (private key) $d$, such that $ed \equiv 1 \bmod (p-1)(q-1)$.


Is this a good way of splitting a private key into a 2 of 3 scheme?

The proposed sharing scheme does allow reconstruction of key $K$ from any two of the three shares $K_A$, $K_B$, $K_C=(X_A,X_B)$, because:

$K=K_A+K_B$ from $K_A$ and $K_B$
$K=K_A\oplus X_A$ from $K_A$ and $K_C$
$K=K_B\oplus X_B$ from $K_B$ and $K_C$

Problem is, the scheme leaks information about key $K$: always less than 1 bit worth to participants $A$ and $B$; but over 1 bit to participant $C$, growing up to the whole of $K$ if there is enough redundancy in $K$ (see below). While the proposed sharing scheme might leak acceptably little information about the private exponent of an RSA or ECDSA key, which are close enough to uniformly random, it is not recommendable in general.

As an extreme example, if it is shared a key $K$ of a single bit, that is $K\in\{0,1\}$, then:

if $K=0$ then $K_A=0$, $K_B=0$, $K_C=(X_A,X_B)=(0,0)$
if $K=1$ then either

$K_A=0$, $K_B=1$, $K_C=(X_A,X_B)=(1,0)$
$K_A=1$, $K_B=0$, $K_C=(X_A,X_B)=(0,1)$

It follows that $C$ always learns $K=X_A\oplus X_B$, and $A$ or $B$ seeing its $K_i=1$ learns $K$; also, if $K$ is uniform, $A$ and/or $B$ seeing its $K_i=0$ can bet that $K=0$ with better than even odds.

For large $K$, $A$ and $B$ learn some information about the order of magnitude of $K$ (less than 1 bit worth on average, regardless of the distribution of $K$).

But $C$ gains more information about $K$. The low-order bit of $X_A\oplus X_B$ is always the low-order bit of $K$, and the high order bit of $X_A\oplus X_B$ tends to match the corresponding bit in $K$ for uniform distribution of $K$.

Worse, redundancy known to exist in $K$ allows $C$ to gain even more information about $K$. For example, if it is known that the representation of $K$ consists entirely of the digits 0 and 1 in some base $2^j$ with $j\ge3$ including hexadecimal or octal, then $C$ can fully reconstruct $M$ by computing $(X_A+X_B)\oplus(2(X_A+X_B))$ and masking to keep the bits that could be set in $K$.

A simple scheme that works and leaks no information is to share each bit $k$ of $K$ by assigning a uniformly random integer $x$ in $\{0,1,2\}$ to $A$ ; $x+k\bmod3$ to $B$ ; $x+2k\bmod3$ to $C$. If two parties have the same value assigned, then $k=0$, otherwise $k=1$.

Further, by writing $K$ in base three, thus with $k\in\{0,1,2\}$ , and with the parties knowing who received $x$, $x+k\bmod3$, or $x+2k\bmod3$, the capacity of the scheme is increased and each of the three shares has the same size as $K$.

Of course, the generic method is Shamir's secret sharing, which allows a flexible number of shares and threshold for reconstructing $K$.


Is it OK to reseed a Deterministic Random Bit Generator from itself?

No, in your situation (where you don't care about security), there isn't any harm in seeding the generator from its own output (or, for that matter, reseeding it by just incrementing the original seed, and resubmitting it).

The chief issue would be if you would fall into a loop (that is, you start repeating outputs); if the seed you generate is 128 bits or more, that is highly improbable for any reasonable number of reseeding.

Now, as you are well aware, a CSRNG is overkill for your purpose; however the question is whether it is cheap overkill.  If the total amount of time your simulation takes is short, or if the bulk of your computation is in things other than generating the random string (and so taking a bit longer in the generation part doesn't significantly slow you down), then it is cheap overkill.


Is pseudorandom function also a one-way function?

(Note the OP's clarification that even for 1, the adversary does not have the key k.)

Yes. $\:$ The way to show anything like those, is to use the fact that oracle access to prfk

is sufficient to efficiently determine the extent to which an adversary is violating those.

def straight-line_reduction_1_():
 m = random_element_of_(domain(F))
 query F on m
 let c be the output of F on m
 send c to inner_adversary_1
 forward any queries and responses between inner_adversary_1 and the F oracle
 let guess be the output of inner_adversary_1 on c
 if guess == m:
  return True
 else:
  return False

straight-line_reduction_1_ uses only a small amount of space and makes only one more oracle query than inner_adversary_1, and straight-line_reduction_1_'s runtime is dominated by forwarding queries/responses from/to inner_adversary_1.  (So, straight-line_reduction_1_

is efficient.)  For all F, the probability of straight-line_reduction_1_ outputting True is equal

to the probability of inner_adversary_1 correctly guessing m given c.  However, if F is a

truly random function and inner_adversary_1 makes at most q queries, then the probability

of inner_adversary_1 correctly guessing m given c is at most (q+1)/(cardinality(domain(F))).

(That should be proven, but I'll only bother doing so if you ask.)

Given that result (which I didn't provide a proof of), it then follows that the probability of inner_adversary_1 correctly guessing m given c by making at most q queries is at most (q+1)/(cardinality(domain(F))) plus the extent to which the combination of inner_adversary_1

with straight-line_reduction_1_ distinguishes the function family from random.

In particular, if the function family is pseudorandom then 1 holds.

One can proceed analogously to show that

if the function family is pseudorandom then 2 also holds.


Can I encrypt a message by swapping bits in the text?

First problem is you're not specifying at all how many swaps you need to do for a given message length, other than saying it's "several." For an $n$-bit messsage there are $n!$ ways of rearranging its bits, gives a lower bound of $\mathrm{log}_2(n!) = \sum_{i=1}^{n}\mathrm{log}_2(i)$ bits for on how much pseudorandomness you'll need. Rather than analyze a precise number of rounds your random swaps method needs to achieve a good result, however, it's just simpler to substitute in a Fisher-Yates shuffle that'll fairly permute an $n$-item sequence in $n$ steps.

But whatever you do, even if we assume true random bit permutations, the technical answer is that this is straightforwardly insecure because an adversary can easily and reliably distinguish encryptions from random strings by looking whether the number of ones vs. zeroes is the same as their chosen plaintexts. A special case of this is that any message that's only zeroes or only ones encrypts to itself.

Even if we assume the attacker doesn't get to choose plaintexts, they can use this property to test whether a given ciphertext could be the encryption of some plaintext they guess at.  Take for example the binary ASCII codes for these strings:

HAHA ===> 01001000 01000001 01001000 01000001 ===>  8 ones
YEAH ===> 01011001 01000101 01000001 01001000 ===> 11 ones
NOPE ===> 01001110 01001111 01010000 01000101 ===> 14 ones

If I see a ciphertext with 11 ones I can tell that it's definitely neither HAHA nor NOPE, but could still be YEAH.


Does adding OWF of the private key to encryption scheme hurts security?

It's possible to have a secure encryption scheme that ignores the first half of its key, and a secure OWF that leaks the entire second half of its input. Composing them as in your question results in something profoundly insecure.


How does MD5 divide the padded message in 16 words?

1819043144 in decimal is 6c6c6548 in hexadecimal.  In US-ASCII, the letters have the following encodings:

H = 0x48
e = 0x65
l = 0x6c
l = 0x6c
etc.

‘Word’ here means a group of bits of a natural size for a machine, typically larger than a byte; in this case, it's a group of 32 bits.  It does not mean an English word like ‘Hello’.  MD5 breaks the padded message into blocks of 16 words (512 bits) apiece to work on one at a time before moving onto the next block in sequence.


Which platforms are most vulnerable to Simple Power Analyse Attack

Power Analysis attacks rely on the attacker being able to analyse the power used by the computing device, so such attacks work best on platforms where the attacker can analyse the power drawn by the device with cycle accuracy. This points at smart cards, which:

use an external source of power;
have very little room for some isolation circuitry which would hide the per-cycle power consumption;
work in a security model where the attacker controls the external environment (contrary to, say, encryption on a server in a remote room);
run at low clock rates, facilitating analysis;
run on an external clock, under full control of the attacker, thus again facilitating analysis (the chip will refuse to run if the clock rate is too low or too high, but simply knowing the clock signal makes correlation much easier);
are economically forced to be cheap, preventing the application of the most effective but expensive tamper resistance countermeasures.

Smart card vendors still do a lot of work on the subject, and modern, FIPS 140-2 level 3 compliant smart cards, are fairly good at defeating simple power analysis. Countermeasures are both algorithmic (e.g. blinding), software (e.g. always computing the multiplication, regardless of whether the key bit is a zero or a one, but only keeping the multiplied or unmultiplied value at the end), and hardware (isolation with some capacitors, internal clock, extra noise-inducing circuits...).


Security considerations for partially shared password databases

What you are looking for is an authentication and access service on top of a password management system. There are a couple of solutions in this space, but they are corporate and expensive:

http://www.liebsoft.com/privileged_identity_management/
http://www.cyber-ark.com/digital-vault-products/pim-suite/index.asp
http://www.netwrix.com/privileged_password_management.html
There are about 10 other companies and products in this space.

There are also some web based versions of keepass which may fit your needs, but then you'll need to secure the HTTPS, etc.

http://sourceforge.net/projects/webkeepass/


Can I use different IVs when encrypting identical plaintexts with identical keys with AES-CTR?

I'm wondering whether I should try to use the same IV each time,

No. Using the same IV twice for the same message means that you leak that you sent the same message. If your set of messages is somewhat small this allows an adversary to more easily correlate reactions to messages with possible message contents.

whether it's safe to use a random IV for different instances of the same plaintext.

Yes, it is. The security definition which CTR satisfies (CPA security) very much considers the fact that the same message is sent twice. This will not leak anything (within reasonable bounds). To see this note that $F$ is usually modelled as a PRF, that is if your adversary doesn't know the key it might as well be a truly random function $f$ which takes its input, draws a response uniformly at random and stores the mapping for this input. This means that $F(K,I_1)$ can be translated to $f(I_1)$ which can be translated to the random string $R_1$ and the same can be done to construct $R_2$. Then if you look at $C_1=P\oplus R_1$ and $C_2=P\oplus R_2$ you will notice that both are "essentially encrypted with the one-time-pad", i.e. independent and uniformly random keys of size equal to the message length which will obviously not leak any information.


Showing formally that DDH hardness implies CDH hardness

Let me state the precise definition of DDH, to make it more clear: assuming a group an a generator $g$ are fixed, the challenger flips a coin. If he gets 0, he picks $(x,y,z)$ uniformly at random; if he gets 1, he picks $(x,y)$ uniformly at random and sets $z = xy$. It returns $(g^x,g^y, g^z)$. You win the DDH game if you can find out the coin that was flipped with non-negligible advantage over the random guess. Now, you have this adversary $A$ that breaks CDH with probability $\varepsilon$, and you would like to use it to break DDH. So, a challenger flips a coin and sends you a DDH challenge.

I've written:  $Pr[A_{DDH}(g^x,g^y,g^z) = 1]=Pr[A_{CDH}(g^x,g^y)
> = g^z]$ But how can I analyze it? If $g^{xy} \neq g^z$ I don't know the probability that $A_{CDH}(g^x,g^y) = g^z$, I only know that
it gives (some) wrong answer with probability $1-\epsilon$

There are two situations: either the challenger picked $1$, and so it holds that $g^{xy} = g^{z}$. As on input $(g^x,g^y)$, the adversary returns $g^{xy}$ with probability $\varepsilon$, in this case it returns the same $g^z$ that you got from the challenger with probability $\varepsilon$. But if the challenger picked $0$, then by the definition of the DDH game, $z$ was picked uniformly at random, and in particular, totally independently of $x$ and $y$.
So the question becomes: given $g^x$ and $g^y$, no matter how it works and how powerful it is, what are the chances that the adversary outputs $g^z$, which is a uniformly random group element that is not known by the adversary? You should easily convince yourself that the answer is one over the order of the group - a negligible quantity.
Hence, when the coin is $0$, the adversary outputs $g^z$ with negligible probability; when it's $1$, he outputs $g^z$ with probability $\varepsilon$. As the coin is flipped at random, both situations happen with probability exactly $1/2$ - from that, you should be able to measure the probability that you win the DDH game by answering $0$ when $A$ fails to output $g^z$, and $1$ when he succeeds.


How to adapt the equation of Gaussian mechanism noise based on number of executions

The formula you mention to get $\sigma$ given $\delta$ and $\varepsilon$ is only correct for $\varepsilon<1$. It's also not tight.
If you use Gaussian noise on multiple statistics, each of sensitivity 1, and want to get the tightest possible privacy guarantees, then you should use the Analytic Gaussian Mechanism instead (Theorem 8), replacing $\Delta$ with the square root of the number of your statistics. It's tight and works for any value of $\varepsilon$ and $\delta$.
The only problem with that approach is that there's no formula giving $\sigma$ as a simple function of $\varepsilon$, $\delta$ and $\Delta$; so you have to do some binary search to find the best possible value (and be careful about how you do the floating-point calculations). Here is an example from our open-source differential privacy library.
Finally, if what you want to do is train a model in a DP way, I would suggest using existing tooling, like TensorFlow Privacy, rather than rolling your own.


Is the private key required once the certificate is hashed and signed?

That of the CA that issued the certificate? No. That of the end entity you are trying to communicate with? Yes. The whole point of a certificate is to create a binding between an entity (eg a website) and a public key, so that by proving ownership of the associated private key somebody (the entity) can confirm to be the entity named in the certificate.

  Is the private key used for any other purpose within the handshake or
  certificate validation?

Again, the CA's private key: No. The end entity's private key is used to sign a specific part of the handshake (usually the ephemeral ECDH public key) so that the party knows that said part really originated from the entity named in the certificate and that they are connecting to that entity which then also knows the negotiated symmetric keys.


AES-GCM encryption and decryption doubts

1) I'm using a GUID as authentication tag which is binding to a user to whom the sensitive information belongs. The encrypted text and tag is stored in separate databases at separate locations. Is this ok?

You're not using the GUID as authentication tag, you're using it as additional authenticated data, which is OK, especially since you've already shared a key. The authentication tag is - when using the somewhat hacked Java API - output at the end of the ciphertext.

  2) From what I've read AES-GCM takes in (plain text, IV, key, associated data) and outputs (cipher text, authentication tag). Are associated data and authentication tag the same thing, because my implementation of encrypt and decrypt work when I pass same value in cipher.updateAAD(...)? How to obtain the authentication tag after encrypting?

No, see above. If you want to get the authentication tag you may want to strip it off the end of the ciphertext.

  3) Should I use BouncyCastle instead of using default Java implementation.

Not unless you want to forgo AES-NI and GCM optimizations. I'd stay away from Bouncy Castle for implementations already present in the API provided by OpenJDK / Oracle runtimes.'

  4) If the data to encrypt is 16 bytes, when should I generate a new DEK for enc/dec.

See the NIST GCM specifications; in general it depends on the authentication tag size, so there multiple answers possible.

The constant value of GCM_TAG_LENGTH is not displayed in the code of the question though, so it is unclear what the authentication tag size is in your particular case.

In the comments an authentication tag size of 128 bits was mentioned. The NIST GCM specifications are not entirely clear on that, so I asked for the sizes in this question which was answered a whole lot later.

  5) One master KEK for all DEK's? For encrypting DEK's should I use same AES implementation? If not, then what to use?

That depends on the protocol and, in the end, the use cases and threat model. But in general I'd use a KDF such as HKDF to derive keys rather than to wrap (encrypt) them. Now for that you might want to use Bouncy Castle, because there aren't any good KDF's implemented in Java itself.


AES-CBC-128 Known plain, IV, Cipher attack

No, there's no possible solution to get the key used, assuming what we are told in the question, and

the key has been chosen randomly;
we find no way to get a clue about it (which could be the case for example if we monitored a device holding the key, or used the obligatory XKCD technique);
we define "possible" as: having odds better than one in a thousand millions (about one in $2^{30}$) for $2^{96}$ keys tested (which I guesstimate represents quite a few years of the effort currently wasted spent on bitcoin mining, based on that source telling these things recently got over $4\cdot10^{18}$ SHA256d hashes per second);
no serious attack on AES-128 (the block cipher) is discovered;
we discount the hypothesis of quantum computers usable for cryptanalysis, which currently are still very hypothetical.

That's because enumerating keys by brute force is quite nearly the best known attack against AES-128 (the block cipher) that recovers the key without attacking the implementation; thus odds of finding the right key after testing $n$ keys are at best $n\,2^{-128}$, regardless of the operating mode used.


Is there a simple hash function that one can compute without a computer?

Well, depending on what's reasonable and what you can compute reliably by hand, you MIGHT be able to compute modular exponents in a moderate-size group (like $Z_n$ for moderate $n$).  Exponentiation via repeated squaring is doable I think.

Probably more practical would be a MD5-like ad hoc confusion-diffusion primitive.  You'd need to make the input large enough to make exhaustive search impractical by hand (32 bits should do it I would think?) and then make a round-function that was simple enough to compute by hand but had empirically-good collision-resistance.  Finally apply Merkle-Damgaard for a "few" rounds.

I would expect this to work reasonable well with a random crypto classmate.  If you're playing against Adi Shamir, you're probably screwed.

Edit: For in-person commitment schemes, you can get rid of hash functions altogether.  Just write a string of random bits on a folded paper and hand it to your partner to commit those bits.  But the more interesting scenario is doing this through a prison wall, over a phone, or over the internet... then you really need something mathematical.

Let's take the prison-wall example: you want to commit to another inmate some integer $x$ and you have no computational resources but can communicate with tapping (no paper).  Here's what I would do: pick a 64-bit number $x$ that you want to commit.  Make sure you can't factor it (it might be prime, but verifying primality is going to be tedious by hand).  Then choose another, larger, 64-bit number $y$ that is also hard to factor by hand.

Now compute $p=xy$ (easy) and send $p$ to your buddy.  If $x$ and $y$ were both hard to factor, $p$ is as well, so he can't extract $x$ or $y$ from $p$.  Now for the reveal, you send $x$ and $y$; he verifies that $p = xy$ and that $x$ is the smaller integer.

It's important that both are 64-bits (or both the same size) to prevent you from changing to $x'$ after the commit where $p = x' (k y)$.  This doesn't happen if $x$ and $y$ are prime, of course, but large primes aren't easy to generate by hand.


Are covert and rational adversaries same?

As the previous answer says, they are certainly NOT the same. However, there is certainly a connection between them. Specifically, the covert model just says that there is a deterrent parameter $\epsilon$ and the guarantee is that if the adversary tries to cheat then it will be caught with probability at least $\epsilon$. The question that arises is how should $\epsilon$ be set in real life.

Here, rationality can be utilized. Specifically, if you are given the adversary's utility when it succeeds in cheating undetected, its (presumably lower) utility when it doesn't cheat, and its (presumably even lower) utility when it is detected cheating, then you can compute the value of $\epsilon$ that will guarantee that the rational choice is to behave honestly. I'll leave the details of how to compute this to you (it's not difficult).


The equation for secp256k1 is $y^2 = x^3 + 7$, so that $a = 0$ and $b = 7$.

The equation for secp256r1, also known as NIST P-256, is $y^2 = x^3 - 3x + b$, where $b$ is 41058363725152142129326129780047268409114441015993725554835256314039467401291; here $a \equiv -3 \equiv p - 3 \pmod p$ where $p = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1$ is the characteristic of the field underlying secp256r1.

If you change the curve parameters, you get a different curve.


Would it be safe to use the message hash as the IV in ChaCha?

First, this is not safe with ChaCha because the ChaCha nonce is only 64 bits long, since ChaCha nonces are normally chosen sequentially, so there would be a nonnegligible danger of collision with a reasonable number of messages.  Let's say XChaCha instead, with a 192-bit nonce, which is large enough to choose at random without danger of collision.

The recipient must know the nonce in order to decrypt the message, so we presumably have to transmit it alongside the ciphertext.  Call the hash $h$; the ciphertext is $E_k(h, m) \mathbin\Vert h$, where $E_k(h, m)$ is the XChaCha encryption under key $k$ and nonce $h$ of the message $m$.

If you use a fixed public hash $h = H(m)$, such as SHA-256, then the ciphertext $E_k(h, m) \mathbin\Vert H(m)$ reveals information about the plaintext that the adversary can exploit: they can confirm a guess about what a plaintext was, e.g. Attack at dawn! vs. Attack at dusk!, by evaluating $H(m)$ themselves on their guesses and checking.
If you use a secret hash $h = H_\kappa(m)$, such as keyed BLAKE2s-192, you have a kind of MAC-and-encrypt composition.  The adversary doesn't know the secret $\kappa$, and so can't confirm guesses.  It doesn't quite achieve the security goal of authenticated encryption because if you repeat a message, the ciphertext will be repeated too.  But that's the only leak that a cost-limited adversary will get, as you observed.
If you add a nonce parameter back into your system and use a secret hash $h = H_\kappa(n, m)$, then you get a nonce-misuse-resistant authenticated cipher.  If you never repeat a nonce, it's authenticated encryption; if you do repeat a nonce, whether accidentally or cetaceaously, repeated ciphertexts are the only leak that a cost-limited adversary will get as above.

This is an SIV or synthetic initialization vector scheme, similar to others on the market like AES-SIV, AES-GCM-SIV, and various CAESAR gladiators with names that are too cool for a bird like me to remember.  Using BLAKE2 won't beat any speed records—with BLAKE2, you pay for collision resistance, not just pseudorandomness—but it'll do the job if those are the parts you have on hand.  A much faster approach might be to use a universal hash family to compress the message into 256 bits, say hash256, and feed that through a 256-to-192-bit PRF; one could probably do better by exploiting the structure of XChaCha as a composition of ChaCha and HChaCha.


Using KDF output for password validation

It's best practice to use the KBKDF to generate separate key material for validation as well as for generating the key used for encryption using a different input or counter of each key.

If you do apply a KBKDF for each key / IV (using different ID's/counters for each) then you should not have any concern leaking any information. These KBKDF's are plenty fast (especially in comparison with PBKDF2 of course) so speed should not be a concern.

I would suggest to use a counter mode KDF in NIST SP800-108 if you want to stay within NIST boundaries. You can still use your favourite HMAC as PRF.

Note that there is some discussions regarding the security of KDF's. NIST approved KDF's may not always be the most safe. For instance, consider scrypt over PBKDF2 and HKDF-Expand (your currently selected KBKDF) over NIST SP800-108 if you don't require NIST approved algorithms.

Note that all the KBKDF's of NIST as well as HKDF have been added to Bouncy Castle 1.50 lightweight API for Java (I did the implementation / testing against NIST CAVP vectors), in case you require an implementation.


AES Password Based Key Derivation Iterations

Thank you all for all of the excellent help. I am happy to say that with your help I have found the answer to my initial question and more.
The code below accepts a [string] password, [hex string] salt, [int] key size, and [int] iteration count, and returns a tuple containing the correct key and IV for PBKDF2. OpenSSL PBKDF2 uses 10,000 iterations by default. Leave the salt in the command as double quotes if there is no salt.
Proof:
printf "Today is a good day!" | openssl enc -aes-192-cbc -md sha512 -pbkdf2 -S 436172616d656c73 -k "Sparky" -p
results in:
salt=436172616D656C73
key=37A12300EF8D3442B266B41172154DFE0836803C4257AFB6
iv=E2FC1F1DF27AB4A6F303EDD6537EEE53
The same salt, key, and IV can be obtained by using the code and class below:
from pbkdf2 import kdf
key, iv = kdf.pbkdf2(“Sparky”,”436172616D656C73”,192,10000)
results in:
key=37A12300EF8D3442B266B41172154DFE0836803C4257AFB6
iv=E2FC1F1DF27AB4A6F303EDD6537EEE53
“Sparky” is the password
“436172616D656C73” is the salt
192 is the AES-CBC key size
10,000 is the number of hmac iterations (pbkdf2)
And here is the Python3 code (pbkdf2.py).
Import hashlib
import hmac
class kdf:
def pbkdf2(passwd, salt, size, iterations):

    dictionary = {128:((0,32),(32,64)), 192:((0,48),(48,80)), 256:((0,64),(64,96))}

    k = b = hmac.new(passwd.encode("utf-8"), bytes.fromhex(salt) + b'\x00\x00\x00\x01' if len(salt) > 0 else b'\x00\x00\x00\x01', hashlib.sha512).digest()

    for i in range(2, iterations + 1):
        b = hmac.new(passwd.encode("utf-8"), b, hashlib.sha512).digest()
        k = bytes(i ^ j for i, j in zip(k, b))

    key = k.hex()[dictionary.get(size)[0][0]:dictionary.get(size)[0][1]]
    _iv = k.hex()[dictionary.get(size)[1][0]:dictionary.get(size)[1][1]]

    return key,_iv


Are there encryption schemes with which it takes (significantly) longer to encrypt than to decrypt?

Perhaps not of relevance if the question is meant in a purely thoretical (i.e. asymptotical) sense, but the CBC encryption mode is inherently sequential, while decryption can easily be performed in parallel.


Can I use my random IV (for AES) as a salt for PBKDF2?

I suppose that what you are trying to do is password-based encryption of some data; you use PBKDF2 to derive the password into an encryption key, and then use the key with AES to encrypt the data. The AES encryption needs an IV, and the PBKDF2 function needs a salt. Both IV and salt should be generated anew for each encryption (even if reusing the same password).

Generically, the salt and the IV can be just encoded in a header for the encrypted file. They are not secret values.

Your question is then: can you use the same value for both the salt and the IV (presumably to save space) ? I do not recommend it. I would be surprised if it really induced a security issue, but who can be sure ? It looks a bit funky, and that's bad enough to avoid it. What you can do, instead, is to store the salt in the file header, and use PBKDF2 to generate both the key and the IV. Thus, the IV needs not be stored anywhere. PBKDF2 is a key derivation function which can produce an output of arbitrary length.

Generating the key and the IV from the same source is what is done in OpenSSL (in its private symmetric encryption format), and also in SSL/TLS (up to TLS 1.0).

I hope that your AES-based encryption mechanism uses a mode with integrated integrity checks, like EAX. Integrity is not an option; it is often overlooked, but it is necessary for security.


Is it possible to attack a one-time pad encrypting only slightly more than its length?

This does not look like OTP, but like PSK with conflicting extra steps.

Alice has her own entropy source.

And by definition, Bob does not have this same entropy source, so what Alice have is a random number generator. And since she cannot tell Bob if the bit is 0 or 1, Bob have no way to decrypt anything. And if she can tell, Eve can know too. And if Eve cannot know the content of the message, why don't use this secure channel to send the message instead of entropy?

A meddling Eve, if she knows how this protocol works

Eve always knows the protocol, the algorithm, all obfuscations, she only needs the key. That's the Kerckhoffs's principle.

The data transferred this way (which could be even more entropy - Eve doesn't know which part of the data is which!) would be protected by the initial challenge, and by the entropy of the initial OTP.

Likewise Bob cannot decrypt anything because he does not have access to Alice's entropy source.

Would it be instead preferable to perform an RSA/Diffie-Hellman key exchange over the initial OTP?

Absolutely! Diffie-Hellman is used by every single bank out there for a reason. OTP can be unbreakable if done right, but is so cumbersome that isn't practical and that's why is rarely used in the real world. IfDiffie-Hellman is good enough to banks protect themselves, is good enough for you, Bob, Alice, and for me.


The title of this article is complete hype. Tip: when a journalist says “X could solve Y”, read “X probably won't solve Y”. Much of the content of the article is hype too.

Cryptography has a random number problem, but the problem is not producing random numbers, and the proposal in this article wouldn't be useful to produce random numbers anyway.

Cryptography does need random numbers for many things. The problem of obtaining random numbers can be divided into three parts: generating sufficient entropy for security, generating a sufficient quantity and quality random numbers for the applications, and actually bringing the random data where it's needed. The first problem is solvable, the second is solved, the third one is where the difficulty is.

To generate random numbers, it's necessary to have a source of non-determinism. A deterministic computer, by definition, is incapable of producing anything random. But there is no need for any expensive machine using quantum mechanics. Classical mechanics or cheap applications of quantum mechanics are good enough in practice. Your PC has a random number generator, if it isn't an antique. Your phone probably has one too, if it's a not-too-old smartphone. If your credit card has a chip, it has a hardware random generator. You can find microcontrollers that cost a few cents (I'm talking bulk prices here) that have a built-in RNG. Many devices lack one (your home router might not have one), but at current prices it's a supply chain and requirements problem, not a cost problem. If you can control how a device is designed, there's no excuse not to include a hardware random generator.

A hardware random generator gives you entropy, but it isn't directly usable for cryptography. It usually has limited bandwidth and biases (no measurement apparatus is perfect). Fortunately, turning an entropy source into a cryptography-grade random generator is a solved problem. All you need to do is to use the entropy source to seed a pseudorandom generator. Any cryptography library has one or more PRNG available.

The real problem with random numbers in practice is getting all the software out there to use them correctly. This is a difficult problem to solve because every piece of software needs to get things right: properly relay the data, don't leave a copy lying around. The operating system driver needs to get it right, the system installer needs to get it right, all the layers of software libraries need to get it right, and the application needs to use the libraries properly. Proper use of randomness is near-impossible to test, so bugs are difficult to detect. Common problems include developers using non-cryptographic random generators when they need cryptographic ones (don't use rand anywhere near cryptographic code!), using a cryptographic PRNG that is not seeded properly (always use your OS's randomness source such as /dev/urandom or CryptGenRandom), using non-random inputs to functions where random input was needed, and systems where the entropy source is not configured properly.

So when the article says

  Eventually, it would be great if they shrank the setup to fit on a chip, says Bierhorst: a random number generator in every laptop, so that nobody ever uses those algorithm-based numbers for encryption again.

that's attacking the part of the problem that doesn't need new technology. The reason people use “algorithm-based numbers for encryption” is that either their device lacks a generator which can be built cheaply using current technology, or that there's a problem in the software. This new machine would not help with either part of the problem.

As for the proposed application of a “randomness beacon”, it's a plausible one, but it's of limited use and difficult to put to practice. A randomness beacon, as the article explains, is useless for most cryptographic applications since it wouldn't be secret. It's useful as an impartial arbiter, for example to assign auditors to auditees, but that can be done with any source of randomness. The fact that the machine itself is more difficult to “hack” than a PC with RDRAND is not all that useful, because the hacking could be done in the reporting and logging system.


This is extremely insecure. The discrete log is a red herring -- nowhere in the problem is the difficulty of discrete log relevant, because neither party ever uses their knowledge of their private exponent (computing $g^{-k}$ given $g^{k}$ does not require knowledge of $k$, so if inverses are fast to find, knowing one gives you the other quickly). That means we can ignore the exponentiation; all you have is Alice picking $a\in G$ and Bob picking $b\in G$, so $s=ma$, then $t=mab=sb$, then $u=ta^{-1}=mb$. Eve intercepts $s,t,u$, and computes $s^{-1}$, then $s^{-1}t=b$, then $b^{-1}$, then $ub^{-1}=m$. The issue isn't really that they're all divisible by $m$, it's that you rely on keeping $a$ and $b$ private but then send $s$ and $sb$ over a public channel (which means an attacker can easily recover $b$ and thus $m$).

In actual ElGamal, you actually use your private exponent. Instead of having to keep $g^{k_A}$ and $g^{k_B}$ secret, you rely on the fact that Alice (who knows $g^{k_B}$ and $k_A$) can compute $g^{k_Ak_B}$ while an attacker cannot. To use the security of discrete log, you have to do something that's easy for someone knowing the exponent but difficult for someone else; finding the inverse is not that something.


Where does the $\varphi(n)$ part of RSA come from?

$\phi(n)$ is the order of the multiplicative group of the numbers in $\mathbb{Z}_n$. $\phi$ is known as Euler's totient function. A consequence Lagrange's theorem is that any element of a group, raised to the order of the group is equal to the identity element.

So, using $\phi(n)$ ensures that decryption works. Since $ed\equiv 1\bmod{\phi(n)}$, we can say that $ed-1\equiv\phi(n)$ or $ed\equiv\phi(n)+1$.

So if we look at $m^{ed}\bmod{n}$ well that is just the same as $m^{\phi(n)+1}\bmod{n}$ which is the same as $m^{\phi(n)}m^1\bmod{n}$. But since $\phi(n)$ is the order of the group, we know that $m^{\phi(n)}\equiv 1$ so we have $m^{\phi(n)}m^1\equiv 1m^1\equiv m\bmod{n}$. This proves that decryption works and we were only able to prove it since we chose $d$ accordingly.

If we didn't use $\phi(n)$ the mathematics wouldn't necessarily* work out and decryption would not be guaranteed to work. So, the designers of RSA used $\phi(n)$ out of necessity.

*See the comment by fgrieu. Any multiple of $LCM(p-1,q-1)$ would work.


Safe way to derive IV from the DH shared keys for AES-GCM?

If there is no regulatory requirement, for AES-128, a good option would be splitting the SHA-256 hash into a key (128-bit), IV (96-bit), and any unused portion. That allows us to make the IV implicit (and secret, which is unnecessary, but does not harm) thus saves even so little bandwidth. For AES-192 or AES-256,  we can do this with SHA-512 instead of using SHA-256.

On a related note, make sure that the same derived key is never used by a given party both to encrypt and decrypt/authenticate because that opens to mirror attacks. If the communication is bidirectional, derivation could use
$$\operatorname{HMAC-SHA-xyz}(\mathsf{key}=\text{DH-shared-secret}, \mathsf{message}=\text{sender-ID})$$
as the origin of the session key and IV used by the sender to prepare its message. HMAC internally hashes the shared secret if it more than a certain size (64 bytes for SHA-256), that's fine.

For even stronger assurance:
$$\begin{align}
\text{Key}&=\operatorname{HMAC-SHA-xyz}(\mathsf{key}=\text{DH-shared-secret}, \mathsf{message}=\text{'K'}\mathbin\|\text{sender-ID})\\
\text{IV}&=\operatorname{HMAC-SHA-xyz}(\mathsf{key}=\text{DH-shared-secret}, \mathsf{message}=\text{'I'}\mathbin\|\text{sender-ID})
\end{align}$$

which gives an argument that the leak of IV (which should be assumed even if the IV is not sent in clear) can't harm the secrecy of Key even if the hash has some level of defect. Also, HMAC has a parameter (now shown) to specify the output size, making the definition cleaner.


AES and DES - reusing the same round keys

Before discussion about the Slide attack, first, observe that the DES uses 48-bit key per round produced by it's key-schedule. If the DES uses the same key for every round than the key-space will be $2^{48}$ not $2^{56}$. Therefore it can be trivially broken by simple brute-force of two p3.16xlarge instances on AWS.

The Slide attack

Wagner and Biryokov called your type of key-schedule homogenous. This occurs when the key-schedule produce periodic subkeys and in the simplest case, the period is 1, as in your question.

While the brute-force requires $\mathcal{O}(2^{n})$, the slide attack on block cipher (if works) requires $\mathcal{O}(2^{n/2})$ and for Feistel ciphers requires $\mathcal{O}(2^{n/4})$ since the $F$ function modifies only half of the block.

The attack is independent of round numbers, all it needs the $F$, the round function, is a weak permutation; i.e. given two equations $F(x_1,k) = y_1$ and $F(x_2,k) = y_2$ it is easy to extract the key $k$, as 3 rounds of DES which is a weak permutation.

idea

Let a block cipher with $r$ rounds, then;

$X_j = F_1(X_{j-1})$ where $ 1 \leq j \leq r$ and $x_j$ represent the internal outputs, $X_0$ is plaintext and $X_r$ is the ciphertext.

In the period 1 case, $F_j = F_{j+1}$ for all $j \geq 1$.

slid pair

A pair of $(P,C)$ and $(P',C')$ is called a slid pair if $F(P)=P'$ and $F(C) = C'$.

attack

Obtain $2^{n/2}$ known-plaintext $(P_i,C_i)$ and look for slid pairs. By birthday paradox, it is expected to find to find one pair with this property.

When the round function is weak, testing a slid pair condition will be easy, and some key bit of the cipher will be recovered.

Note: This slide attack requires $2^{64}$ known plaintexts and has a time complexity of $2^{128}$ encryptions for AES and this is greater than exhaustive key search!

Efficient Slide Attacks

Bar-On et. al improved the original sliding attack with their work 1K-AES has that use the same key for every round with data and time complexity $2^{64}$. The result shows that 1K-AES is insecure.

Countermeasures

Don't use periodic key scheduling algorithms
Utilize round constant, as in AES, PRINCE, LED, Simon and Speck,...


c# Correct Triple Des Block Encryption Usage

3DES is a block cipher which processes "blocks" of 64 bits. A block cipher is not sufficient to encrypt a message, defined as a sequence of potentially many bytes. Hence the use of a mode of operation which organizes things; this may imply some padding, and an Initialization Vector.

TripleDESCryptoServiceProvider can do all that: you specify the key, the chaining mode, the padding and the IV, and then you call CreateEncryptor() (or CreateDecryptor()) which returns an ICryptoTransform instance, on which you call TransformBlock() and TransformFinalBlock() to process all your data. You can process the data by chunks (you call TransformBlock() several times, and finally TransformFinalBlock() once).

The code you show is trying to do the opposite of what you seek: it uses TripleDESCryptoServiceProvider to process a single block, without any chaining or padding (hence the use of ECB and no padding).

Note that:

ECB is known to be a weak chaining mode (it leaks quite a lot of information on typical input data).
Secure modes of operation (e.g. CBC) need an appropriate IV: in the case of CBC, it must be chosen randomly and uniformly with a cryptographically strong random generator, and it must never be reused (the point of the IV is that you can reuse the same key for several messages, as long as each message has its own IV). The IV is normally transmitted along with the encrypted message (in the clear), since the decryptor will need it.
Ciphers process bytes. A "string" is a sequence of characters, thus a conversion step is needed. I assume that your StringToByte() method (which you do not show) does that. Beware of charsets: you want the conversion to always operate the same way, regardless of how the local machine was configured.


Well, the obvious answer to 'how to find a Safe prime that is also a Nothing-Up-My-Sleeve' number would be to take one of the primes listed in RFC 3526.  These primes (which come in several sizes) are all of the form $p = 2^n - 2^{n-64} - 1 + 2^{64} \cdot ( \lfloor 2^{n-130} \pi \rfloor + i )$, where $i$ is the smallest nonnegative integer such that both $p$ and $(p-1)/2$ are prime.  Having most of the bits within the modulus be from the binary expansion of $\pi$ would appear to satisfy the Nothing-Up-My-Sleeve property.

Also, I don't know if it is wise to pick a generator; after all, from the hash $a^m \bmod p$, the attacker can deduce the value $m \bmod 2$ if $a$ is a generator.  It would seem more prudent to have $a$ be a quadratic residue (and with the RFC 3526, along with any safe prime that is $p \bmod 8 = 7$), $a=2$ is such a quadratic residue, as well as making the exponentiation operation slightly cheaper.


What is the rationale design of TinyJambu-LWC?

There is indeed an advantage but it only makes sense if you understand how the initialization stage works.

TinyJambu is generally designed for a hardware implementation with a fixed key, and the key also burned into the hardware. Think an IOT device that reports data, but where there is a chance of theft and you dont want the key extracted, as the attacker has copies of all the ciphertext. Even worse, the attacker may want to forge messages.

TinyJambu uses a single keyed permutation $P$ based on a NLFSR, this is iterated a number of times depending on how it is used and how large the key is. $P_n$ refers to the permutation iterated $n$ rounds. Note the diagram P1 and P2 are NOT $P_1$ and $P_2$, but rather a permutation step where $n$ is based on key size.

In the initialization stage, the key is not added to the state by XOR like in a typical sponge based cipher, rather it is permuted using $P_{1024}$, this effectively mixes the key into the state, but allows the key to stored only as part of the permutation.

After the state is keyed, the nonce is added 32-bits at a time. First a domain separator bit is added to the state, then it is permuted with $P_{384}$, then a nonce word is XOR'd. Once again the permutation is keyed here, so there is additional key mixing into the initial state.

In P1 and P2, P1 is equal to $P_{384}$, and P2 is $P_{1024}$ or larger, based on key size, in 128 round increments. The nonce is basically added using P1, just like the AD. Additionally, since the AD comes after the nonce, it changes the state in the same way, so nonce reuse with different AD does not compromise security.

So back to the question, what is the advantage of keyed permutation in duplex construction? Primarily to keep the state small, but also to make the cipher lightweight, as all key addition and permutation are part of a single operation. The designers also say:

  When a key is already stored in the device, the state of the cipher could be very small since we can use the keyed permutation to prevent an attacker from computing the states offline and launching the state collision attacks using the computed states

With a state size of only 128-bits, it is possible (not probable) to compute the keyed initial state in advance and crack the whole cipher, but making the permutation keyed makes that even more infeasible.


This is not true. In particular, consider $4\in (\mathbb{Z}/5\mathbb{Z})^\times$. We have that $4^2 = 16\equiv 1\bmod 5$, so $\langle 4\rangle = \{1, 4\}$ is not the full group.

The theorem you mention is known as Fermat's little theorem, and it states:

  $\forall x\in (\mathbb{Z}/p\mathbb{Z})^\times$, $x^{p-1}\equiv 1\bmod p$

As you mention, all elements satisfy this. Generators are distinguished in that they satisfy this, but for all $k < p-1$ they satisfy $g^k\not\equiv 1\bmod p$ (so $p-1$ is the "smallest exponent" such that $g^{p-1}\equiv 1\bmod p$). As a hint, you don't need to check all $k < p-1$ (and you can in fact check a single $k < p-1$ which will work in all cases).


What makes an open source encryption algorithm safe?

The XOR state is irreversible without the proper key which is what I understand, so whats the point of all of the other operations that happen on the key?

Suppose all we had was secret keys and the XOR operation.  Well, actually, it is possible to build a secure cipher out of that, called the one time pad.  One time pads offer perfect secrecy, but suffer from fatal practical flaws:

The keys must be as long as the messages.
You must never use the same key to encrypt two different messages, or it becomes very easy to break.

So we can look at your question from this angle: the extra complexity in modern ciphers is the price that we pay to remove those practical disadvantages.  It's what allows us to use a single 128-bit key to safely encrypt gigabytes of data, time and time again.

The other thing that I'd highlight is this: you're assuming that just because you know what operations an algorithm does, it's automatically easy to undo those operations.  But one of the core assumptions of modern cryptography is that this is false: there are operations that are easy to do but costly to undo.  The prime example is that multiplication is easy (runs in polynomial time), but factorization is costly (doesn't run in polynomial time).  It's possible to prove that, if such one-way functions exist, then cryptographic algorithms can be built and fully disclosed, whose security depends exclusively on the secrecy of the key.

So if the designers of AES chose their operations right, then AES encryption and decryption are:

Easy for parties who know the secret key;
Costly for parties who don't.

Whether this is true for actual algorithms like AES and why, well, that is the hard part, and can't be answered in a brief question/answer format like this.


as SEJPM said you're looking for digital signature algorithms.
If you want names and standards, there's ECDSA based on elliptic curves and DSA based on the RSA philosophy.

https://en.wikipedia.org/wiki/Digital_signature

Good luck!


Is XCBC where k2 and k3 might be the identical, secure?

If key 2 and key 3 has a nonnegligible chance to be the same, then the attacker has a nonnegligible chance of being able to generate a valid (Message, MAC) pair.

Here's how it works, if the message is not a multiple of 16, then XCBC pads the message out to the next multiple of 16; if it already is, the message remains the same.

Then, XCBC logically does a CBC mode encryption (using key 1); except that when it gets to the last block, it xor's in either K2 (if no padding was added) or K3 (if padding was added) before the final encryption.

Note that this padding operation is public; anyone can compute it.

What the attacker would do is request the MAC of a message M (which is not a multiple of 16); he gets a valid T.

Then, the pair (Pad(M), T) has a nonnegligible chance of being also valid; if K2==K3, then the message will be a multiple of 16, and so no padding is added; XCBC will xor in K2, but since K2==K3, that'll give the same result as the corresponding step during the query, and the final encryption will also be the same.


First of all, I'm no expert in this area. Generally $n$ bit ECC seems to have a security level of about $n/2$, but I found some claims that it's lower for certain types of curves.

RFC4492 - Elliptic Curve Cryptography (ECC) Cipher Suites contains the following table:

               for Transport Layer Security (TLS)

                Symmetric  |   ECC   |  DH/DSA/RSA
               ------------+---------+-------------
                    80     |   163   |     1024
                   112     |   233   |     2048
                   128     |   283   |     3072
                   192     |   409   |     7680
                   256     |   571   |    15360

It doesn't seem to distinguish between different curve types.

I found an RFC draft (not a real standard RFC) that claims the following security levels:

Symmetric  |  ECC2N  |  ECP  |  DH/DSA/RSA
       80  |   163   |  192  |     1024
      128  |   283   |  256  |     3072
      192  |   409   |  384  |     7680
      256  |   571   |  521  |    15360

This is consistent with other other sources that put the security level of ECC at $n/2$. Binary curves seem to be a bit worse than prime curves.

The blog entry Not every elliptic curve is the same: trough on ECC security elaborates:

  Additionally, something that most people does not know, but that it’s extremely relevant to our analysis, is that there are different kind of ECC curve cryptography and their “size” it’s different depending on the kind of curve:

  ECC Curves over Prime Field (often referred as Elliptic Curve and represented by P-keysize)
  ECC Curves over Binary Field (often referred as Koblitz Curve and represented by K-keysize)

  Given a security strength equivalence the Elliptic Curve and the Kobliz Curve have different key size, for example when we read ECC 571 we are referring to Koblitz Curve with an equivalent strength to ECC 521 Prime curve.

For some curves (like supersingular ones) there are specific attacks, which make them significantly weaker.


How to store and use a Cryptographic Seed in a database

The best way to encrypt a seed in a db would be to use multiparty computation and heterogeneous computing (multiple core systems). The only other way would be to store them in plaintext, e.g. in a shadow password (non-public file).


Why can the last block contain a full block of padding in CBC Encryption?

Yes, we always have to pad the message. The reason is simple: How do we know if the message has a padding or not if we don't always pad?

Let's say we pad with adding only $0$ bits. We got the (after padding) message $0101\,1100\,0000\,0000$ and a block size of 2 bytes (16 bits). Well, what was the original message? Was it $0101\,11$? Or was it $0101\,1100$? We don't know.

We can of course pad with one $1$ bit and then as much $0$ bits as needed. This works every time if the message size is not a multiple of the block size, but not anymore of it is exactly a multiple of the block size. We would not know if the last $1$ and $0$s are padding or part of the mssage. Because of this we need to pad even if the message is already in "perfect size".


Since your question has RSA tag, I'm going to speak mostly about RSA, but first...

symmetric cryptosystems

With symmetric key, your key could be anything binary with given length. But, since passwords are weak and aren't binary, you should pass it trough key derivation function (KDF).

RSA and other asymmetric cryptosystems

With asymmetric key, there is some structure to it (at least in some cryptosystems, like RSA. There are asymmetric systems where there isn't any special structure to private key - Thanks Ilmari Karonen). For example in RSA you need two primes p and q of close length, and public key is n=p*q (there are some more things commonly saved, but this smallest amount of information to get key). So you can't simply convert your password to key with KDF.

But there are some techniques that can be used to derive private key solely from password (And for given security and some more things that can be constant). For example, you can use your key as input to CSPRNG (A random function), and then generate 2 random numbers with given length, and then search for closest next prime for those numbers. This (albeit somewhat slowly - same as generating a key) will give you a private key, that will be same for same password. Same can't be done with public-key as far as I know - everything you can do there is use optimal encoding of it and give it to user. But after all it's public key so it's meant to be shared anyway.

This way, every asymmetric cryptosystem can be made where key gives you same key, just by feeding password to KDF and then using it as seed in CSPRNG. This isn't usually done, because this will lead to appearance of same keys (because two people or more used same password). And this is somewhat slow (same as just generating new key). And there are no standardized ways to do that (Thanks user4982).


Is it possible to increase the encryption security of a short key?

The hash idea isn't great. See Kerckhoffs's principle. The underlying secret is still the four digit PIN, which is only $4 \times -\log_2(10) = 13$ bits of security. And don't we all pick '1234' anyway?
You can use a key derivation function like Argon2 (there are others). That slows down hackers attempts at guessing your PIN. You could aim for something like one second on typical hardware. Still it could be brute forced after a mean time of an hour and a quarter on that same kit though.
Security could be further enhanced with an $n$ tries and you're locked out policy if there is a server involved with conditional logic. This would be implemented by also using the derived encryption key to encrypt a series of four check digits, say all zero. If they do not decrypt to all zero, it's the wrong PIN, so try again until lock out. This is how your ATM card behaves.
And a further further method would be to have an increasing/exponential delay between attempts. This would depend on your customers' acceptance though.

A longer pin is an option if the business allows it. Windows login PINs are six digits.


What are advantages of using a HMAC over RSA with SHA-1 hashes?

HMAC is much faster to compute. Also, HMAC might still be secure, even if the underlying hash function is broken. This is not true for RSA + a broken hash function.


Tips on conceiving safe software messaging platform

First, as a bit of general advice: Designing a secure cryptographic system is hard. Experts with decades of experience still make mistakes. Depending on your intended audience, you may be better served by looking for an established system that meets your needs rather than trying to design an implement something from scratch.

To answer your specific question above, I would suggest that the keys of store 2 are one weak point. With a list of these keys, and one or more user IDs known, it's straightforward to implement a dictionary attack to try and discover the associated passwords. (X does nothing to help protect the passwords, because it is not random.)

Passwords are notoriously a weak point of most systems in use today, thus you might contend that this is unavoidable, but you should still strive to avoid making it easy to do an offline dictionary attack.


On Linux, does /dev/random unblocking imply that /dev/urandom is seeded?

I finally untangled what this code is doing.

YES.

The quick version of why this is true is that the first 128 bits of entropy which the system collects get mixed directly into the nonblocking pool, bypassing the input pool. The logic which implements this is part of each of the add_foo_randomness() functions:

 r = nonblocking_pool.initialized ? &input_pool : &nonblocking_pool;

http://lxr.free-electrons.com/source/drivers/char/random.c?v=4.5#L804
http://lxr.free-electrons.com/source/drivers/char/random.c?v=4.5#L924

And per http://lxr.free-electrons.com/source/drivers/char/random.c?v=4.5#L677, nonblocking_pool.initialized is set when its entropy_total exceeds 128 bits. So by the time anything is available from /dev/random, /dev/urandom has been seeded.

For completeness, here's the rest of the story on how the entropy pools are managed:

All pools, even the nonblocking pool, have entropy estimates that are credited when new entropy is mixed in and debited when entropy is extracted.
As detailed above, the first 128 bits of entropy collected get written and credited to the nonblocking pool; everything thereafter gets written and credited to the input pool.
If the input pool is overflowing (i.e. its entropy estimate is approaching its total size), then this triggers a transfer from the input pool to either the blocking or the nonblocking pool, on an alternating basis. Pools skip their turn if they're already at least 75% full. (http://lxr.free-electrons.com/source/drivers/char/random.c?v=4.5#L692)
Reading from /dev/random always triggers a transfer from the input pool to the blocking pool (http://lxr.free-electrons.com/source/drivers/char/random.c?v=4.5#L1177). Reading from /dev/urandom triggers a transfer from the input pool to the nonblocking pool only if there has been no such transfer in the past 60 seconds (http://lxr.free-electrons.com/source/drivers/char/random.c?v=4.5#L983).
The amount transferred is (http://lxr.free-electrons.com/source/drivers/char/random.c?v=4.5#L995):

Typically equal to the amount being read from /dev/{u}random
But at least 64 bits
But not more than the current entropy estimate for the input pool
And not more than that estimate minus 128 bits if the transfer is to the nonblocking pool. (EDIT: I think this is a bug. See http://marc.info/?l=linux-kernel&m=145945873501946&w=2)


Unpredictability of X.509 serial numbers

A non-random serial number does not imply, by itself, a security issue with the signature scheme, but, as @Jack points out, it can be used to leverage an attack. On a general basis, signature algorithms begin by hashing the input message with a given hash function; if the message or hashing process is fully controlled by the attacker, then collision resistance of the hash function becomes an important issue. On the other hand, with some randomness inserted by the signer (e.g. a random serial number, added by the issuing CA of a certificate), the signature ought to be resistant to mere collision attacks, and, ultimately, work on preimage resistance (and MD5, with all its shortcomings, still appears to be optimally resistant to preimages).

Such randomness should be inserted in an "appropriate" way, which depends on the internal structure of the hash function. Halevi and Krawczyk have specified a generic way which should be good for all hash functions, and called it RMX. It has resulted in an Internet Draft and NIST Special Publication SP-800-106. Noteworthy points are:

RMX is meant to be applied on any binary message, but it requires generation of some random value, to be transmitted along with the message.
Since the hashing process is modified, the signer and verifier must be aware of RMX, right at the beginning of message processing.
RMX includes a description of how to extract the random value from the first half of a DSA/ECDSA signature (the "$r$" value, which does not depend on the signed message). This is meant to save bandwidth and be compatible with existing data formats (which do not have room for an extra "random value"), but it makes signature more complex, since the "$r$" value must then be generated before hashing the input message -- which can be cumbersome in systems where the hashing is externalized, in another module than the one holding the signature private key.
This is a recommendation which has not yet found its way in any notable standard.

Using a random serial number is the "poor man's randomized hashing" which has the fine property of being fully compatible with existing X.509 certificate verifiers (the hashing process and the certificate formats are not altered in any way) and many CA already implemented it, albeit not for protection against collision attacks. In a certificate, the serial number occurs "early enough" in the structure, with some big fixed elements between it and the public key (namely, subject and issuer names, validity dates...), so that it suffices, with existing MD-based hash functions (MD5, SHA-1...), to prevent leverage of collision attacks. Also, a long enough random serial number ensures uniqueness with overwhelming probability without having to look up anything in a database. For proper interoperability, use a positive serial number less than $2^{159}$ (this ensures that the value encoding, as specified in ASN.1 DER, will fit in 20 bytes).

Completely unrelated to collisions and signatures, but relevant for security, predictable serial numbers leak business information. As Peter Gutmann states it in his X.509 Style Guide (an old but fun and not completely obsolete text):

  by using sequential numbers a CA ends up revealing just how few certs it's actually signing (at the cost of a cert per week, the competition can find out exactly how many certs are being issued each week)


That's a reasonable solution if you can't use a random salt. If you personalize your hash function for your application, then the salt is globally unique for each user. (e.g. use sitename||username as salt) The only salt reuse happening is that older passwords of the same user have the same salt. But that's a very minor issue.

I disagree with Polynomial who wants unpredictable salts. Unpredictability is not necessary for most protocols involving password hashing. Global uniqueness or at least rareness is the decisive property.

To combine sitename and username I'd simply go with concatenating them. Your HMAC suggestion is certainly fine too. Your xor variant gives me a bit of a bad feeling, but is probably fine too.


Is one-time-pad still secure if the number of 1's in the key is revealed to the attacker?

The security notion one usually considers for OTP is perfect secrecy, which informally means that the ciphertext does not reveal any information about the original message, regardless of the computational power of the adversary. It is already known that this requires that the key size must be equal to the plaintext size and that all keys are equiprobable. That way, for each ciphertext you could find a key that decrypts the ciphertext to any possible message.

However, your proposal violates these principles. Assuming the key size (and plaintext size) is $S$, then the number of possible keys is not $2^S$ (i.e., all the possible keys of length $S$, as in the regular OTP), but $\binom{S}{n}$, which is much less than $2^S$. This has the consequence that for a given message $m$, not all possible ciphertexts are equiprobable, or conversely, for a given ciphertext not all possible messages are equiprobable (in fact, some of them have no probability).

Let's see it with your example. With regular OTP, for a length of 5 bits there are $2^5 = 32$ possible keys (as well as messages and ciphertexts). If an adversary gets $c$, there are 32 possible messages that correspond to that ciphertext. That is, the ciphertext is completely useless to the adversary. Now, in your proposal, for $n = 3$ there are $\binom{5}{3} = 10$ possible messages for a given ciphertext, since there are only 10 possible keys. The ciphertext $c$ and knowledge of $n$ makes possible to the adversary to deduce which 10 messages (out of the 32 possible) are related to the ciphertext. Therefore, he is gaining some knowledge about the original message.


Yes, SSL2 did not MAC the handshake. See (recentish and more available) rfc6176

  SSL 2.0 Deficiencies

  SSL version 2.0 [SSL2] deficiencies include the following:

  ...

  o  Handshake messages are not protected.  This permits a man-in-the-
    middle to trick the client into picking a weaker cipher suite than
    it would normally choose.


Hill Cipher if the length of the string is not divisible by the Key Dimensions

This is a standard problem in modern cryptography (eg for CBC-mode).

The standard solution is to use Padding or some other agreed-upon mechanism to encode variable-length messages as a multiple of the blocksize.

The most common padding is PKCS#7 padding: If one byte is left, append 0x01, if two are left append 0x02 0x02 and so on. Note that this requires you to also pad on messages which are a multiple of the blocksize (in case your message ends on eg 0x01).

As you are more concerned with letters than bytes, you can probably adapt the above scheme to use A instead of 0x01 and B instead of 0x02 and so on for the full alphabet. So in your particular case you would pad the message with a single A.


An alternative hashing method, how does it compare?

Isn't the second method reducing the hash's target space because it is only 2 x 'chunk size' (which is less than the original size if number of chunks > 2)? If the target hash space is smaller then collisions are likely to be higher and the resulting hash use is therefore weaker on that basis (although this isn't the most important factor with reasonable size target spaces).

Obviously this is a simplistic analysis comment and not a full crypto analysis - for that you need to have a solid grounding in cryptography mathematics.


Yes. There is a difference between key strength, key size and the size of the encoding of a key.

The modulus of the RSA private key determines the key size, for instance, but an RSA key commonly also contains the public, private exponent and CRT parameters, an encoding structure etc. etc.

In GPG indeed the "key" consists of many additional parts as well (as you can see from the size). You can packet-inspect the keys in GPG by simply performing gpg <exported-key>.

See here for more information (and note that the question really belongs on Superuser, but whatever).


Most hashes are built from permutations (either keyed permutations/block-ciphers, as in MD5, SHA-1 and SHA-2, or unkeyed permutations as in Keccak/SHA-3 and CubeHash). A permutation is a shuffling of the inputs. Once you have a good random permutation, you can easily build a hash from it. See Construction of One-way compression functions from block ciphers on wikipedia for details.

As an analogy you can think of shuffling cards by hand (except crypto uses between $2^{128}$ and $2^{512}$ cards).

A common strategy for shuffling is going through the deck several times, performing a bunch simple operation each time. Each time of going through the deck is called a "round".

Why do SHA-2 and SHA-3 have a smaller number of rounds?

For a round you can either choose to do more complex, and thus expensive operations which achieves more or simpler cheaper rounds which do less. SHA-1 has simpler rounds than SHA-2 and thus needs more of them to properly mix the values.

The art of designing a symmetric primitive that achieves as much mixing as possible with as cheap as possible operations. The SHA-2 and SHA-3 are better than SHA-1 in that regard.

Why have many rounds?

More rounds make cryptoanalytic attacks harder but do not help (much) against brute-force. In particular it increases resistance to a technique called differential cryptoanalysis, which is a popular technique for attacking hashes and block-ciphers.

Going back to the card shuffling analogy:

You can define features of a deck, such as two specific cards being placed directly after each other. After going through the deck once, that feature might be preserved with a relatively high probability like 10%. After going through the deck multiple times the probability of a feature surviving all of them drops exponentially. So the probability of a feature being present in the final state will approach the ideal probability quickly.

In cryptoanalysis you can define similar features called "differential characteristic". One round preserves this characteristic with a certain probability. For example if a characteristic survives one round with probability $10^{-3}$, it might survive 80 rounds with probability $10^{-3 \cdot 80}= 10^{-240}$.

If you have characteristics surviving all rounds with high enough probability, that can often be exploited for finding a collision or pre-image faster. A designer aims for enough rounds that exploiting these shuffling flaws is more expensive than doing a brute-force attack while choosing few enough rounds for good performance.

(There are a few inaccuracies in the above description, but I believe the general idea is correct.)

Why does SHA-1 have 80 rounds?

More rounds increase security against cryptoanalysis. But it also decreases performance. So it's necessary to find a compromise between security and performance. The SHA-1 designers chose 80 rounds.

In hindsight, they chose a too low value, since we have since found attacks against SHA-1 that find collisions faster than brute-force.


Communication cost of Oblivious Transfer and OT Extension?

With the most standard approaches, the cost of performing $m$ $1$-out-of-$n$ oblivious transfers of strings of length $\ell$ with security parameter $\lambda$ is $O(m(\lambda + n\ell))$ (see e.g. this paper, Section 5.3). Use $m=1$ above to have the asymptotic cost for a singe OT. Note that this can be improved in various settings - e.g., it can be typically much less if all you need is are random OTs (where the selection bits and the transmitted strings are random). We can also get some savings when $\ell$ is very small (constant) and $n$ is not too big as well - for example, $1$-out-of-$2$ OT of length-$1$ secrets can be done with communication $O(\lambda/\log \lambda)$ with the same paper.

One can further improve this cost, at least in theory. Typically, it is theoretically feasible to perform $m$ $1$-out-of-$n$ oblivious transfers of strings of length $\ell$ with security parameter $\lambda$ using communication $O(m n\ell)$, under standard assumptions (e.g. under the DDH assumption, with a constant $4+o(1)$ in the $O()$ when $m$ is sufficiently large, using this paper - note although that this is not concretely practical)


In cryptography it is common to reason about the probability of an event in the probability space of all the random choices made (i.e. the random bits generated) during an algorithm's execution. So, in this description, "over the random coins of HGD" means the probability is computed over the probability space defined by the random bits used during HGD sampling.
You are, I think, confused here by the difference between the uniform and hypergeometric distributions. If the sampling is uniform, the probability of the sample $x$ being equal to any other particular $x^*$ is exactly $\frac{1}{|D|}$. However, the sampling here is actually done according to the hypergeometric distribution, so the probability of the sample $x$ being equal to some $x^* \in D$ is exactly $P_{HGD}(x−d;|R|,|D|,y−r)$.

The wording here is on the formal side, but the intuitive takeaway is that the distribution of the output of the HGD subroutine is hypergeometric. Think of it as a black box that takes in some arguments (and random bits) and spits out a sample from the right distribution.


You can prove this by contradiction.
Suppose $\mathcal{E'}$ is not CPA-Secure, meaning there exists an attacker $\mathcal{A}$ who can break this scheme with non negligible probability. Using this attacker, we try to break CPA-Security of $\mathcal{E}$ with non negligible probability as follows:

The adversary $\mathcal{B}$ (for breaking $\mathcal{E}$) outputs two plaintexts $m_0$ and $m_1$.
A bit $b$ is then chosen uniformly at random $b \leftarrow \{0,1\}$ and $\mathcal{B}$ receives the encryption of $m_b$ i.e., $c=E(k,m_b)$.
Based on the definition of CPA indistinguishability experiment (see section 3.5 in Katz-Lindell book), the adversary has still access to the encryption oracle and can query this oracle at the point $c$ receiving $c'=Enc(k,c)$. (Here, we assume that the plaintext and ciphertext space is the same.)
$\mathcal{B}$ emulates the CPA indistinguishability experiment for $\mathcal{A}$ by sending this challenge ciphertext $c'$ to $\mathcal{A}$.
$\mathcal{A}$ outputs a bit $b'$.
Eventually, $\mathcal{B}$ returns the same outbuts bit $b'$ as $\mathcal{A}$.

Now, it is obvious that assuming non-negligible success probability for $\mathcal{A}$, the success probability of $\mathcal{B}$ in breaking $\mathcal{E}$ is non-negligible too.


Is tweakable block-cipher based on the Merkle-Damgård construction secure if $F$ is a PRP

Minematsu studied this construction, and some generalizations thereof, in Section 5 of Beyond-Birthday-Bound Security Based on Tweakable Block Cipher. Minematsu, however, uses a PRF to derive keys instead of the block cipher.

The idea is simple: the tweakable SPRP security of this construction, for $q$ queries distributed arbitrarily over $t \le q$ different tweaks, is the security of $t$ instances of $F$, plus the distance from the key derivation to uniformly distributed keys.

The security of $t$ instances of $F$ is otherwise known as multi-key or multi-user security, and we can bound it as $t \cdot \mathbf{Adv}_{F}^{\text{sprp}}(\mathcal{D})$, i.e., at most $t$ times the security of any single instance.

So we have
$$
\mathbf{Adv}^{\widetilde{\text{sprp}}}_{F}(\mathcal{D}) \le \mathbf{Adv}^{\text{prf}}_F(\mathcal{D'}) + t \cdot \mathbf{Adv}^{\text{sprp}}_{F}(\mathcal{D''}) \,,
$$
for a distinguisher $\mathcal{D'}$ making $t$ queries and a distinguisher $\mathcal{D''}$ making at most $q$ queries. The first distance can be refined by the PRP-PRF switch, so we end up with
$$
\mathbf{Adv}^{\widetilde{\text{sprp}}}_{F}(\mathcal{D}) \le \frac{\binom{q}{2}}{2^n} + (t + 1) \cdot \mathbf{Adv}^{\text{sprp}}_{F}(\mathcal{D''}) \,.
$$

So this construction is secure until approximately $2^{n/2}$ blocks are queried and, assuming a perfect block cipher with $\mathbf{Adv}(\mathcal{D}) \le t/2^k$, around $2^k/t$ evaluations.

Imagine for example a concrete instance of AES-128 where an attacker queries $2^{64}$ different tweaks $x_i = \text{AES}_{\text{AES}_k(t_i)}(0)$ then tries $2^{64}$ keys $k_i$ until $\text{AES}_{k_j}(0) = x_i$. Each attempt has success probability $2^{64-128}$, since there are $2^{64}$ distinct keys. Then, $\text{AES}_{\text{AES}_k(t_i)}(1)$ must also be equal to $\text{AES}_{k_j}(1)$.


How are boolean functions used in cryptography?

Many properties of boolean functions are used in stream and block cipher design, e.g., when they are used as filtering and combining functions. Some important examples are:

Nonlinearity (minimal Hamming distance of the truth table of the boolean function from affine functions), must be high for resisting linear/affine approximation attacks.
Correlation Immunity (CI) and resilience (CI is the maximal nonzero weight for which all Walsh-Hadamard transform coefficients are nonzero, and quantifies resistance to divide and conquer style correlation attacks; resilience is CI plus balancedness). There is a tradeoff between CI and algebraic degree of the boolean function $f$, namely $deg(f)+CI\leq n-1$, for an $n$ variable boolean function, discovered by Xiao and Massey.
There are links between the weight of the complex DFT and linear complexity of sequences (and all sequences can be expressed as Boolean functions after a choice of basis of $GF(2^n)$ over $GF(2)$ and appending zero) called Blahut's theorem.
There is a fantastic recent book on applications of boolean functions in cryptography, "Cryptographic Boolean Functions and Applications" by Stanica and Cusick. Older relevant books include "Analysis and Design of Stream Ciphers" by Rueppel and "Stability Theory of Stream Ciphers" by Ding, Shan, and Xiao. Any issue of Designs, Codes and Cryptography, and quite a few Crypto conferences will regularly have papers on these topics. See the IACR eprint server as well.

Finally, Sboxes are just vectorial (vector output) boolean functions, see the chapter entitled Propagation and Correlation in the AES Proposal, a version of which also appears in the book "The Design of Rijndael" by Rijndael designers Daemen and Rijmen.


How to calculate period of stream cipher with multiple LFSR and NLFSR

While I do believe I understand what you are asking for, I will rephrase my own interpretation of the question, and apologize if I have misunderstood the question.

Question: How do you calculate the period of a stream cipher whose output is determined by multiple feedback shift registers (linear or nonlinear)?

"Determined by multiple feedback shift registers" is somewhat vague, so I will give some concrete examples.

Nonlinear combiners

First off, let's talk about nonlinear combiners. That is, the output of the feedback shift registers (linear or nonlinear) are combined in some way. The scheme would look something like this, where $R_1$, ... , $R_n$ are the shift registers and F is some boolean function.

Let $a_{1}$, ... , $a_{n}$ be the periodic sequences produced by $R_1$, .. , $R_n$ respectively and $b$ be the output sequence from F. Now let $P(a_i)$ denote the period of sequence $a_i$ $\forall i \in \{1, .. , n\}$ and $P(b)$ be the period of sequence $b$. Then the following holds:

$$
P(b) | lcm[P(a_1), ... P(a_n)]
$$
Where lcm denotes the least common multiple. Now, if the FSRs $R_1$, ... , $R_n$ were chosen such that $P(a_i)$ are pairwise coprime, we get a stronger bound:

$$
P(b) = \prod_{i = 1}^{n} P(a_i)
$$

In fact this condition ONLY holds if $P(a_i)$ are pairwise coprime. This result is due to Lidl and Niederreiter.

Decimation

Another way to construct a stream cipher from multiple LFSRs is by letting one LFSR clock another LFSR. In this section, I will not discuss NLFSRs.

We will consider two well-known examples, however in order to keep the answer somewhat brief I will not give full descriptions of them. Links will be given to resources below. Only two LFSRs are used in these examples, $R_1$ and $R_2$.

The Binary Rate Multiplier

A theorem due to Chambers and Jennings (1) show that under the following assumptions:

R1 has a primitive feedback polynomial of degree m, and hence a period of $P(a_1) = 2^m - 1$
R2 has a primitive feedback polynomial of degree n, and hence a period of $P(a_2) = 2^n - 1$
All prime factors of $P(a_1)$ divide $P(a_2)$
$gcd[\sum_{i=0}^{2^m-2}x_i, 2^n - 1] = 1$
Then we have that $P(b) = (2^m - 1)(2^n - 1)$

The Shrinking Generator

Shrinking generators are another way of combining LFSRs by decimation. In the original paper by Coppersmith, Krawczyk and Mansour (2), the following bound is given on the period:

$R_1$, $R_2$ have primitive feedback polynomials of order $r_1$, $r_2$ respectively.
$P(a_1)$, $P(a_2)$ are coprime.
Then $P(b) = (2^{r_1} - 1)2^{r_2 - 1}$.

Note that this is only to give you an idea, and only holds for the cases described above. Below I link to a couple resources for further reading on binary-rate multipliers (BRMs) and shrinking generators, if they are of interest.

(1): W. G. Chambers and S. M. Jennings, "Linear equivalence of certain BRM shift-register sequences," in Electronics Letters, vol. 20, no. 24, pp. 1018-1019, 22 November 1984.

(2): Coppersmith D., Krawczyk H., Mansour Y. (1994) The Shrinking Generator. In: Stinson D.R. (eds) Advances in Cryptology — CRYPTO’ 93. CRYPTO 1993. Lecture Notes in Computer Science, vol 773. Springer, Berlin, Heidelberg


In SRP, v = g^x means $v = g^x \mod p$, i.e. exponentiation modulo a large prime $p$.


How exactly is the input message of SHA-256 (pre-)processed?

So is this an array with 64 elements, each allowed to be 32 bits long?

Yes, although you could also use 128 elements of 16 bits or 256 elements of 8 bits if the (embedded) processor doesn't support 32 bit operations. SHA-256 however operates on 32 bits internally, so that's the most efficient word size.

If the implementation uses anything other than 32 bit operations then the 32 bit operations need to be replicated with one of the other word sizes.

  But then I ask myself, if we have a message that is, for example 4096 bits long and we only fill the first 16 elements of the array with the original message, what happens to the other (4096-16*32 = 3584) 3584 bits of the message?

They'll be processed after that chunk. SHA-256 operates on batches of 512 bits at a time, this is the 16 words as 16 * 32 = 512 bits chunk (Wikipedia pseudo code says: for each chunk).

Each chunk is processed and this updates the h0..h7 state, which provides the start of the next processing of the chunk. The final state is used to produce the output.

  What are the rightrotate and rightshift operators doing to the elements in the array?

Well, they move the bits of the selected word to the right. The rightrotate operation will put the bits that "fall off" the word back on the left. In cryptography we call this transpositioning.

It is possible to emulate any of these operations using bitwise masking operations if they are not directly available in the runtime (Java for instance does not support rotate, only shift).

Processors generally directly support shift and rotation.

Notes

Note that it is important to note that SHA-2 is defined to be big endian and SHA-3 (unfortunately) little endian. This is important when implementing the algorithm on a runtime with a different endianess.

Obviously the wikipedia pseudo code should not be implemented directly. For each chunk it reads:

  create a 64-entry message schedule array w[0..63] of 32-bit words

normally you make sure that SHA-256 implementation only allocates the message schedule array once, after which it can be reused for each chunk. The pseudo code was written to understand the algorithm rather than to provide a hint on how to implement it efficiently.


Why is counter mode encryption with a 16-byte cipher block not broken?

You are right that it is generally foolish to try to use AES-GCM for zetabytes of data under a single key.  The standard ought to have clearer data volume limits.

For a long time, the folklore understanding was that a non-collision in a CTR stream doesn't really leak all that much…until sweet32 demonstrated that it actually can be a real problem.  Still, what is feasible for a 64-bit cipher with online cost ${\sim}2^{32}$ may be considerably harder for a 128-bit cipher with online cost ${\sim}2^{64}$.

An alternative is to use crypto_secretbox_xsalsa20poly1305, which is a pseudorandom function family rather than a pseudorandom permutation family like AES, so the generic birthday distinguisher for permutation-based CTR doesn't apply.  One could also imagine using a wider-block cipher like Threefish-256, in which case the birthday bound is unimaginably larger; it is a pity that AES was standardized with a meager 128-bit block.


How can we know who sent a MAC-then-encrypt message?

Opening suspicious files kind of assumes that you immediately do something with the data after decryption. This is a bad idea for both encrypt-then-MAC as well as MAC-then-encrypt and even authenticated encryption.

Many authenticated modes of encryption such as GCM and EAX are online which means that you will immediately receive the ciphertext after encryption or plaintext after decryption. It depends on the interface of the cryptographic library (API) if the online property is available; some higher level API's require you to supply all of the ciphertext plus authentication tag before anything is decrypted.

If you however decrypt first and then keep the result buffered until authentication has taken place then this is not a big problem. As long as you do not process the data before authentication the security of your system should not be at risk (you may of course want to make sure that the ciphertext and tag size is within certain limits).

What is a problem with MAC-then-encrypt is that any vulnerability in decrypting altered ciphertext may result in leaking data. This means for instance that padding oracle attacks for ECB and CBC mode are possible. A lot of the differences between encrypt-then-MAC and MAC-then-decrypt are already explained here.


Some signature algorithms are deterministic (you always get the same signature for the same private key and input), others are not. In the case of RSA, as specified by PKCS#1, the "old-style" (aka "v1.5") signatures are deterministic, while the "new-style" ("PSS") signatures are not (padding includes some random bytes).

In Java, the "NONEwithRSA" mechanism ought to select the old-style signatures, and the input data should be already hashed (a normal signature begins by hashing the input data); in your code, you use unhashed data as input, which is a bad idea for security. The "NONEwithRSA" mechanism was added to support contexts where data is hashed externally, and also SSL/TLS which insists (in its pre-1.2 versions) on using the concatenation of MD5 and SHA-1 as its "hash function". This does not explain why you get different outputs, but you are still doing it wrong.

To investigate further, convert the signature to a BigInteger and apply the public key on it, to see what the padded data looks like:

BigInteger n = ... (the public key modulus)
BigInteger e = ... (the public key exponent)
BigInteger x = new BigInteger(1, realSig);
System.out.printf("%X\n", x.modPow(e, n));

With PKCS#1 v1.5, this should look like:

1FFFFFFFFF....FFFFF0048454C4C4F

(The 48454C4C4F is the encoding of "HELLO" -- because your code puts the raw data here instead of the hash value suitably encoded in an ASN.1 structure which designates the hash function.)

Since you are using a PKCS#11, you will sign data depending on what the underlying device can do. It is possible that your device does not allow such "NONEwithRSA" mechanism, or allows it only if it already looks like a properly encoded hash value. This may be your issue after all. The debug code above should show what happens.

(Also, don't use String.getBytes() without any argument. This converts the input string with the default encoding of the current machine, which depends on how the machine was configured; for some people it will be UTF-8, others will have UTF-16 or latin-1 or something else. It is much better to specify an explicit encoding, as: s.getBytes("UTF-8"))