Integrity check of a binary firmware file with hash function

This appears to be an example of an xy problem.

The goal is to ensure that the firmware is not modified. The standard solution to this problem is to use a digital signature. To quote content from the previous link:

  A (digital) signature is created with a private key, and verified with the corresponding public key of an asymmetric key-pair. Only the holder of the private key can create this signature, and normally anyone knowing the public key can verify it.

With a digital signature, your company (and only your company) can create a signature for the firmware that anyone can verify. If the firmware is modified, then the signature you created will not pass the verification routine.

  There should be an easy way to verify the firmware, like by comparing the hash code, printed in the manual and compare it against the calculated one, loaded from the individual device…

This is not really an "easy" way to verify - most users will not be able/willing to read the binary via JTAG.

Even if they are willing to do so, there is still a possible attack vector: Users might only check if $n$ characters of the two hashes are a match, and then naturally assume that all of the rest will be too. An adversary would in this case only have to produce a partial collision, which could be a much easier task.

It is best to refrain from relying on manual verification.

You can store in the device your public verification key and store the signature next to the firmware. When your device is started, it should be designed to automatically verify the signature before continuing to use the firmware. If the signature does not verify, then operation should be aborted.

RSA is popular* for signatures because verification can be very fast (relatively speaking). Creating a signature is not terribly fast, but since it only needs to be done rarely, it does not really matter how long it takes.

You can use a program such as SSL to create a digital signature, which can be done on any computer.

The verification routine will have to run on your device, so your developer(s) will have to incorporate that functionality in somehow. It may be possible to re-use part of an existing library rather than writing the verification routine from scratch. I would recommend using/porting the code from bearssl if at all possible.

Ideally, your company would contract this portion of development out to an experienced cryptography engineer. If it's possible, it's worth it to have to make sure that it is done correctly.

*In approximately a decade you may have/want to update the signature scheme you use due to quantum computing and NIST's post-quantum cryptography competition.


consequences of using fixed values with OAEP

If you encrypt something with low entropy but use a fixed seed for OAEP, it is trivial to brute force it, and verify your guesses with public key, while randomized all or nothing padding will make verifying a guess impossible.

In the context of signatures rather than encryption, it doesn't seem as severe, but you are supplying the attacker with a bunch of related plain text cipher text pairs which can't be a good idea.


I know no published attack against the XTEA algorithm, much less one working with a few plaintext/ciphertext pairs and a random key.

There are published attacks against reduced variants of XTEA, AFAIK either with much less than half of the 64 rounds, or up to 36 rounds but assuming related or/and weak keys in addition of known plaintext. Often, especially as the number of rounds grows, much more than one plaintext/ciphertext pair is required.

By the metric of how much extra rounds this Feistel cipher has above the threshold where it it gets broken, XTEA seems on the safe side.

The single known practical weakness of the XTEA algorithm is its 64-bit block size, which opens the door to attacks on modes of operation and protocols using XTEA, especially when the amount of data involved reaches a few megabytes gigabytes processed with the same key. We also must fear attacks against implementations of XTEA, in particular by side-channel cryptanalysis.


Is there a standard way to extend the output of a hash?

If you assume the hash function as block box with no known preimage attack, then you can do the following to get a "more secure" hash:

You have a message $m$ and a hash function $h(\cdot)$, and you want to extend the hash length by factor $k$.
Assuming the hash function as block box, you don't change anything if you add a fixed prefix or suffix to the input string.
However, if the prefix or suffix is different, you will get a random different output.
Therefore if you have e.g. $h_0=h(m|0)$ and $h_1=(m|1)$, it should be even harder to find a common preimage $m$ than for a single hash function. But I have no idea how much harder it actually gets. But if you assume a random oracle for the hash function, and find a preimage for $h(m)$  after testing $x$ values in average, the common preimage should be found after testing $x^2$ values.

This leaves us with this formula (the suffix number inside the hash functions should be fixed size bitstrings):
$h'(m):=h(m|1)\,|\,h(m|2)\,|\,...\,|\,h(m|k)$

Finding a preimage or a collision then is not reduced to finding a match for a single input to the hash function but to several.


Does Cramer-Shoup allow re-randomization?

@hakoja correctly points out that what you are asking for is not compatible with CCA security (the security property that Cramer-Shoup satisfies). More specifically, you seem to be looking for a rerandomizable, RCCA-secure encryption scheme. These two properties mean:

Rerandomizable: Given an encryption of an unknown $m$, there is a way to generate fresh samples from $\textsf{Enc}(k,m)$.
Replayable CCA (RCCA): The scheme is non-malleable except for the possibility of modifying a ciphertext $c$ into another ciphertext $c'$ where $\textsf{Dec}(k,c) = \textsf{Dec}(k,c')$. Basically, the scheme is malleable only in ways that preserve the plaintext; otherwise it is non-malleable.

Rerandomizable RCCA means that the randomization feature is the "only malleability" of the scheme. These are not too hard to achieve together, but they become non-trivial when you include another requirement:

Unlinkability: Given $c = \textsf{Enc}(k,m)$ for an unknown $m$, it is hard to tell whether some other $c'$ is an independent encryption of $m$ or a rerandomization of $c$. In order to make sense, this property should hold even in the presence of chosen-ciphertext attacks (i.e., against attackers that have access to the decryption function), which makes it difficult. It often means that the rerandomization procedure must refresh all the randomness in a ciphertext.

In the paper below, we were the first to construct a rerandomizable RCCA scheme:

  Prabhakaran & Rosulek: Rerandomizable RCCA Encryption, CRYPTO 2007

The scheme is about 5-6x more expensive than Cramer-Shoup, and it relies on DDH holding in some groups with related order. There is a later followup work that gives different constructions of rerandomizable RCCA from pairing-based groups:

  Chase, Kohlweis, Lysyanskaya, Meikeljohn: Malleable Proof Systems and Applications. Eurocrypt 2012.


Preimage attack given half of the preimage

Knowing the first 256 bits of X is of little use. Intuitively you can understand this becsuse most values for the first 256 will have a matching second 256 which will lead to Y.
Assuming pseudo random distribution throwing n balls in to n bins will leave only n/e of them empty.
By knowing there is an answer with said prefix the brute force is slightly faster, not by doing anything clever in the brute force but by virtue of eliminating the possibility of no value. If we have a random oracle hash the worst case brute force with the prefix is 2^256 and without it is 2^512 but the difference in expected attack time is rather small. And in any cass it is entirely not fessable. Threre are no known relevant attacks on sha255 to make this even remotely feasible to launch.


How use multiple keys to sign the same document?

Teach the verifier what set of keys must sign a document for it to be valid.  When the verifier receives a document, it must have a valid signature by every one of those keys affixed to it.

Then before a verifier will accept a signed document, the possessor of every one of the signing keys must sign it.

That's it.  That's enough for the security properties you've described.

It's not the most efficient scheme.  There are more efficient schemes, e.g. in an earlier answer I wrote to a related question, but this will satisfy the security properties you asked for and can be built out of any ordinary public-key signature scheme.


1) The adversary queries the oracle (with some randomly chosen message $m$) and gets as a result a message $m=m_1|m_2|...$ and its tag $t=(t_0,F_{k_2}(t_r))$. She then draws $\rho$ uniformly at random in $\{0,1\}^n$ and outputs the message $m=\rho\oplus m_1|m_2|...$ and its (valid) tag $t=(\rho\oplus t_0,F_{k_2}(t_r))$.

2) The adversary queries the oracle (with some randomly chosen message $M$) and gets as a result the padded message $M|1|0^l$ and its tag $t=t_r$. She then queries the oracle with the message $t_r$ and gets the corresponding tag $T$.  She eventually outputs the (unpadded) message $M|1|0^l|0^n$ and its valid tag $T$.

3) The message space consists of the set of $\{\mbox{bit_length}(S)|S\}$ where S runs through all possible bit strings of length less than $2^n$.


Are there any digital signature algorithms in common use that result in 32-byte signatures?

Yes! (restrictions apply). ISO/IEC 9796-2 (scheme 1, SHA-1 hash, option 1 also known as implicit hash identifier, alternative signature production function) is a fully standard signature scheme, based on RSA, widely used in the Smart Card industry for public key certificates and message authentication, that adds only 22 bytes of signature overhead (if the message to sign is at least 234 bytes, for 2048-bit RSA modulus), and is quite simple to implement.

The main caveat is that some of the message to sign is not directly intelligible in the signed message; rather, that 238-byte section at the beginning of the message is recovered as a byproduct of the signature verification process. This restriction is often tolerable: who cares for the public modulus section of an RSA public-key certificate before the signature of the certificate has been verified? Especially since that signature verification is faster and simpler than in most competing schemes with relatively short signatures, e.g. ECDSA.

Other caveat: ISO/IEC 9796-2 scheme 1 is not safe when the adversary can obtain the signature of many chosen messages (there is the risk that the adversary can compute the signature of some more messages). Scheme 3 is a functional replacement free of this defect, with a security argument, but is seldom used AFAIK.

For details on signature with message recovery, including references to the standard, practical description, and known attack against scheme 1, see this answer.

Update: If we stick to ISO/IEC 9796-2 scheme 1 with SHA-1, option 1, alternative signature production function, because that's an industry standard, we should know when it is vulnerable: that's

Due to the padding scheme, when the adversary can repeatedly chose part of a message, exactly predict the rest with sizable odds $\epsilon$, and obtain the signatures, and gain advantage of the slightly constrained message(s) for which a forged signature can be obtained. In current attacks the number of signatures to obtain grows as $K/\epsilon$, with $K$ in the hundred thousands.
Due to SHA-1's relatively poor collision resistance (in the order of $2^{61}$ hashes in the best of the non-retracted attacks currently listed on wikipedia), if the adversary can chose or predict enough of the beginning of a message to create a collision, and can obtain the signature of one message (and gain advantage of the other).

A good mitigation to both issues, if we can afford a 32-byte signature overhead, is that the signer provides 10 bytes worth of entropy unpredictable to an attacker somewhere within the first 64 bytes of the message to sign (e.g. add 10 random bytes at the beginning), before applying the signature. That location best strengthens SHA-1 by making the output of the first compression function unpredictable, and falls within the beginning of the recoverable part of the message where that's best for strengthening the padding scheme.

So at the end of the day, in order to sign a message $M=M_1\|M_2$, with $M_1$ of 224 bytes and $M_2$ an arbitrary non-empty bytestring, using an RSA private key $(N,d)$ with $N$ 2048-bit, the signer

draws a random $M_0$ of 10 bytes, then apply ISO/IEC 9796-2 scheme 1 with SHA-1, option 1, alternative signature production function on message $M'=M_0\|M_1\|M_2$ (these are the next steps);
computes $H=\operatorname{SHA-1}(M_0\|M_1\|M_2)$, which is a 20-byte string;
forms $X=\text{'6A'}\|M_0\|M_1\|H\|\text{'BC'}$, which is a 256-byte string representing (in big-endian convention) a 2047-bit integer also noted $X$;
computes the signature $S=X^d\bmod N$, which is an at-most-2048-bit integer which we represent as a 256-byte string (in big-endian convention);
preferably, apply the verification procedure below on $S\|M_2$, and perform the next step 6. only in case the verification outputs $M$ (or $M'$ depending on variant); this guards against some fault attacks;
transmit the signed message $S\|M_2$ (which is longer than $M$ by 32 bytes).

The verifier using a trusted RSA public key $(N,e)$ with $N$ 2048-bit

checks that the alleged signed message is at least 257 bytes, else rejects the signed message;
splits the signed message into $S\|M_2$ where $S$ is 256-byte;
checks that $S$ (considered an at most 2048-bit integer in big-endian convention) is less than $N$, else rejects the signed message;
computes $X=S^e\bmod N$ (which is an at-most 2048-bit integer) and expresses it as a 256-byte string also noted $X$;
checks that the first and last byte of that string are $\text{'6A'}$ and $\text{'BC'}$, else rejects the signed message;
reformats $X$ as $\text{'6A'}\|M_0\|M_1\|H\|\text{'BC'}$ where $M_0$ is 10-byte, $M_1$ is 224-byte, $H$ is 20-byte;
checks that $\operatorname{SHA-1}(M_0\|M_1\|M_2)$ equals $H$, else rejects the signed message;
output $M_1\|M_2$ as the authentic $M$ (variant: output $M_0\|M_1\|M_2$ as the authentic $M'$).

Note: I have restricted to $M_2$ non-empty in order to avoid a slight complication, where according to the standard the prefix byte should be $\text{'4A'}$ instead of $\text{'6A'}$, and verified as such, when $M_2$ is empty.

For something still with 32-byte overhead, academically sound, fully aligned to standards (if not practice), and dumping the deprecated SHA-1, we can use ISO/IEC 9796-2 scheme 2, with SHA-224, option 1, 2 bytes of salt, and alternative signature production function.


Relation between Key-exchange and Public-Key encryption schemes

First, some definitions.

A public key encryption scheme (PKE) is a scheme with public and private keys, where we can encrypt a message using the public key and decrypt using the private key.
A key encapsulation method (KEM) is a scheme with public and private keys, where we can use the public key to create a ciphertext (encapsulation) containing a randomly chosen symmetric key. We can decrypt the ciphertext using the private key.
A key exchange protocol (KEX) is a protocol that allows Alice and Bob to agree on a shared symmetric key. A two-move KEX is a protocol where Alice sends a single message to Bob, Bob replies with a single message to Alice, and afterwards they both have the same symmetric key.

Next, some context.

Any PKE with sufficiently large plaintext space can be trivially turned into a KEM.
Any KEM can be turned into a PKE by adding some symmetric encryption. (This is often called hybrid encryption.)
Any CPA-secure KEM can be turned into a passively secure KEX. (Alice runs KEX key generation and sends the public key to Bob. Bob creates a ciphertext containing a randomly chosen symmetric key and sends it back to Alice. Alice decrypts the ciphertext and gets the symmetric key.)
Some passively secure two-move KEX can be turned into a CPA-secure KEM. (The process that leads to Alice's message is key generation. The public key is Alice's message. Alice's state after sending the message is the private key. The process that leads to Bob's message and the shared symmetric key (in response to Alice's message, that is, the public key) is key encapsulation, and Bob's message is the public key.)
A passively secure two-move KEX can be turned into an actively secure three-move KEX using digital signatures. (Bob signs both messages and sends the signature as part of his message. Alice signs everything and sends the signature as the third message.)

In other words, these notions are tightly related. (There are lots of details and simplifications in the above, but morally, it should be roughly correct.)

Now to your actual questions (which are a bit unclear, but let's make an attempt at answers).

Compared to traditional PKEs like RSA-OAEP, designing a KEM and proving it secure is often easier. Likewise, compared to traditional key exchange schemes, designing a KEM and proving it secure is often easier. Then we can turn the KEM into a PKE using hybrid encryption, and we can turn it into a KEX with a standard conversion theorem. This is why KEMs are attractive objects to design and study.
Your sketch seems fundamentally similar to the above two-move KEX => KEM argument. However, that doesn't mean that a KEX is easier to design and analyse (from scratch). Experience suggests otherwise.
The traditional definitions of PKE, KEM and KEX doesn't allow the process to fail in the usual case. For traditional schemes, this has always been easy to guarantee. For newer schemes, this does not seem to be the case. Typically, there's some probability that things will go wrong (decryption failures). This makes analysis much more difficult, but not impossible (as NTRU shows us). Still, I don't think the presence of decryption failures changes the fact that KEM design and analysis seems to be easier than KEX design and analysis.


The reason we add salts to the key derivation process it to make the key hash image unique for a given password. Actually a salt is added to remove weakness when an attacker has a list of "most common password". Adding a salt make the attacker job harder, he has to rebuild the attack per every salt he finds, i.e.: per every ciphertext he gets. It is considered safe to store the salt with the cipher text.

Similarly the iteration number is there to slow down a brute force attack, so it is still safe to store it with the cipher text.


Reusing AES-CTR Keys and IVs for File Encryption

Yes, there are secure alternatives to support random-access based encryption.

I did not come up with a way to break the proposed combination.
Still, instead of inventing a new mode, I would recommend to take consider existing modes for this kind of operation, such as XTS mode. The existing modes are more studied, and (in some ways) more efficient. XTS mode (as well as some other modes) only invokes cipher once per block of input. Rogaway has created a paper describing the most common modes of operation, which contains good study of XTS mode, including some critique.

Alternative: IEEE P1619

IEEE P1619 has developed standards for disc encryption. These standards contain cryptographic mechanisms for keeping disc storage encrypted. As disc storage (often) requires frequent rewrites of disc sectors, these standards capability of rewriting sectors.

IEEE P1619 specifies both length expansionless encryption mechanisms and mechanisms with length extension (P1619.1). XTS mode is one of the most commonly used cipher modes of operation, if you want to avoid length extension. It likely proves the security features you expect from CTR with ECB combination, i.e.
it works on narrow blocks (16 bytes) and allows you to pass in index of the sector. Some narrow block a problem. In that case, you mate take a look at wide block encryption such as EME2, XCB from P1619.2.

Alternative: Per Block IV (Traditional)

Just for reference I also mention traditional (well studied way to do this). This approach may prove useful in case you lack cryptographic library or hardware with appropriate modes from P1619.

A well known way to do random-access based encryption is to consider data as blocks and generate random IV per each block each time a block is updated. This of course mess that the encrypted data will expand, but the percentage is not very large: consider e.g. one kilobyte blocks and 16 byte IVs: $\frac{16}{1024}\approx1.6\%$. This is only a small cost. Note: When expanding length, it is commonly good idea to add authentication tag as well.


(Note: I'm using hexadecimal numbers to denote AES field elements and decimal numbers to denote integers.)

First of all, you have to fix a generator of the AES field's multiplicative group. There's quite a lot of them:

0x03 0x05 0x06 0x09 0x0b 0x0e 0x11 0x12 0x13 0x14 0x17 0x18 0x19 0x1a 0x1c 0x1e
0x1f 0x21 0x22 0x23 0x27 0x28 0x2a 0x2c 0x30 0x31 0x3c 0x3e 0x3f 0x41 0x45 0x46
0x47 0x48 0x49 0x4b 0x4c 0x4e 0x4f 0x52 0x54 0x56 0x57 0x58 0x59 0x5a 0x5b 0x5f
0x64 0x65 0x68 0x69 0x6d 0x6e 0x70 0x71 0x76 0x77 0x79 0x7a 0x7b 0x7e 0x81 0x84
0x86 0x87 0x88 0x8a 0x8e 0x8f 0x90 0x93 0x95 0x96 0x98 0x99 0x9b 0x9d 0xa0 0xa4
0xa5 0xa6 0xa7 0xa9 0xaa 0xac 0xad 0xb2 0xb4 0xb7 0xb8 0xb9 0xba 0xbe 0xbf 0xc0
0xc1 0xc4 0xc8 0xc9 0xce 0xcf 0xd0 0xd6 0xd7 0xda 0xdc 0xdd 0xde 0xe2 0xe3 0xe5
0xe6 0xe7 0xe9 0xea 0xeb 0xee 0xf0 0xf1 0xf4 0xf5 0xf6 0xf8 0xfb 0xfd 0xfe 0xff

To build exponentiation and logarithm tables, you have to choose and fix one of the generators. Let's call this element $g$. I will use $g=\mathtt{0x03}$ in this answer, but it doesn't really matter.

Now let's build an exponentiation table, that is, an array that maps an index $i\in\{0,\dots,254\}$ to the element $g^i$.

Initialize an arrayExp[255] of AES field elements indexed by integers.
Set t := 0x01.
For all i ranging from 0 to 254, do

Set Exp[i] := t.
Set t := mul(g, t), where mul denotes multiplication in the AES field.
Set i += 1.

After this procedure, you can easily find $g^i$ using Exp without using a single multiplication: It is just Exp[i % 255]! (The group is cyclic of order $255$, so the modulo operation takes care of is larger than $254$. This is also the reason for the "missing" 256th spot in the table: It is 0x01 again.)

For example, the table for $g=\mathtt{0x03}$ looks like this:

0x01 0x03 0x05 0x0f 0x11 0x33 0x55 0xff 0x1a 0x2e 0x72 0x96 0xa1 0xf8 0x13 0x35
0x5f 0xe1 0x38 0x48 0xd8 0x73 0x95 0xa4 0xf7 0x02 0x06 0x0a 0x1e 0x22 0x66 0xaa
0xe5 0x34 0x5c 0xe4 0x37 0x59 0xeb 0x26 0x6a 0xbe 0xd9 0x70 0x90 0xab 0xe6 0x31
0x53 0xf5 0x04 0x0c 0x14 0x3c 0x44 0xcc 0x4f 0xd1 0x68 0xb8 0xd3 0x6e 0xb2 0xcd
0x4c 0xd4 0x67 0xa9 0xe0 0x3b 0x4d 0xd7 0x62 0xa6 0xf1 0x08 0x18 0x28 0x78 0x88
0x83 0x9e 0xb9 0xd0 0x6b 0xbd 0xdc 0x7f 0x81 0x98 0xb3 0xce 0x49 0xdb 0x76 0x9a
0xb5 0xc4 0x57 0xf9 0x10 0x30 0x50 0xf0 0x0b 0x1d 0x27 0x69 0xbb 0xd6 0x61 0xa3
0xfe 0x19 0x2b 0x7d 0x87 0x92 0xad 0xec 0x2f 0x71 0x93 0xae 0xe9 0x20 0x60 0xa0
0xfb 0x16 0x3a 0x4e 0xd2 0x6d 0xb7 0xc2 0x5d 0xe7 0x32 0x56 0xfa 0x15 0x3f 0x41
0xc3 0x5e 0xe2 0x3d 0x47 0xc9 0x40 0xc0 0x5b 0xed 0x2c 0x74 0x9c 0xbf 0xda 0x75
0x9f 0xba 0xd5 0x64 0xac 0xef 0x2a 0x7e 0x82 0x9d 0xbc 0xdf 0x7a 0x8e 0x89 0x80
0x9b 0xb6 0xc1 0x58 0xe8 0x23 0x65 0xaf 0xea 0x25 0x6f 0xb1 0xc8 0x43 0xc5 0x54
0xfc 0x1f 0x21 0x63 0xa5 0xf4 0x07 0x09 0x1b 0x2d 0x77 0x99 0xb0 0xcb 0x46 0xca
0x45 0xcf 0x4a 0xde 0x79 0x8b 0x86 0x91 0xa8 0xe3 0x3e 0x42 0xc6 0x51 0xf3 0x0e
0x12 0x36 0x5a 0xee 0x29 0x7b 0x8d 0x8c 0x8f 0x8a 0x85 0x94 0xa7 0xf2 0x0d 0x17
0x39 0x4b 0xdd 0x7c 0x84 0x97 0xa2 0xfd 0x1c 0x24 0x6c 0xb4 0xc7 0x52 0xf6

A logarithm table can be easily derived from this:

Initialize an array Log[0x100] of integers indexed by AES field elements.
For all i ranging from 0 to 254, do

Set Log[Exp[i]] := i.

Note that there is no index i such that Exp[i] = 0x00, so the spot for 0x00 in the table is left empty. There is no logarithm of zero (just like over the reals!).

The result looks like this:

---   0  25   1  50   2  26 198  75 199  27 104  51 238 223   3
100   4 224  14  52 141 129 239  76 113   8 200 248 105  28 193
125 194  29 181 249 185  39 106  77 228 166 114 154 201   9 120
101  47 138   5  33  15 225  36  18 240 130  69  53 147 218 142
150 143 219 189  54 208 206 148  19  92 210 241  64  70 131  56
102 221 253  48 191   6 139  98 179  37 226 152  34 136 145  16
126 110  72 195 163 182  30  66  58 107  40  84 250 133  61 186
 43 121  10  21 155 159  94 202  78 212 172 229 243 115 167  87
175  88 168  80 244 234 214 116  79 174 233 213 231 230 173 232
 44 215 117 122 235  22  11 245  89 203  95 176 156 169  81 160
127  12 246 111  23 196  73 236 216  67  31  45 164 118 123 183
204 187  62  90 251  96 177 134  59  82 161 108 170  85  41 157
151 178 135 144  97 190 220 252 188 149 207 205  55  63  91 209
 83  57 132  60  65 162 109  71  20  42 158  93  86 242 211 171
 68  17 146 217  35  32  46 137 180 124 184  38 119 153 227 165
103  74 237 222 197  49 254  24  13  99 140 128 192 247 112   7

Now, the interesting part is how to use these tables to multiply. Take two AES field elements x and y. If either x or y is 0x00, the result is 0x00 (we have to avoid this special case since Log[0x00] is undefined). Otherwise, we can reduce multiplication in the AES field to modular addition over the integers: One can easily show that
$$\mathtt{mul(x, y) == Exp[(Log[x] + Log[y]) \;\%\; 255]}\text!$$

(This is completely analogous to the well-known rule $b^eb^{e'}=b^{e+e'}$ over the reals.)

Similarly, one can obtain inverses:
$$\mathtt{inv(x) == Exp[255 - Log[x]]}\text,$$
since according to the rule for multiplication and since Log is Exp's inverse by definition,

mul(Exp[255 - Log[x]], x) == Exp[(Log[Exp[255 - Log[x]]] + Log[x]) % 255]
                          == Exp[(255 - Log[x] + Log[x]) % 255]
                          == Exp[255 % 255]
                          == Exp[0]
                          == 0x01.

(Again, this is analogous to $\frac1{b^e}=b^{-e}$ over the reals, additionally adding the group's order to obtain a positive exponent.)

So, what have we gained? We replaced multiplication in the AES field, which is quite expensive (involving a loop and conditional branches), by table lookups using only very simple and fast arithmetic.


Use gpg --s2k-mode 3 --s2k-count N, where N is the number of iterations you want to use.  The manual page says the default is 65536, and you can use any number between 1024 and 65011712.

If you like to tweak the defaults, I suggest making this number as large as you can bear it, without introducing noticeable slowdown (e.g., ideal would be to make the passphrase mangling process take about a second or so).

See also this answer to a different question, and the following questions/answers on IT Security.StackExchange:

What is purpose of --s2k-* GnuPG options?
gpg --perfect-code
an answer to "gpg encryption security"
an answer to "Good file encryption tools"
Do OpenPGP/GnuPG apply slow hash to password when encrypting/decrypting key?


Execution speed of AES_128 GMAC operation

GCM is sometimes called a 1.5 pass AEAD cipher, where the CTR encryption counts for 1 and the GMAC counts for 0.5. So you would indeed expect it to be faster than encryption + CMAC and HMAC with regards to the amount of CPU instructions.

That is: as long as the encryption is using AES for both solutions. GCM requires a 128 bit block cipher while CMAC and HMAC could also work with a fast stream cipher.

If the hardware however doesn't support 32 bit multiplications the speed may drop significantly, so it's not that great on embedded processors with a 8 or 16 bit ALU. ARM however is 32 (for ARM9) or 64 bit so it should be relatively fast on one.

Note that there may be rather big differences with regards to implementation. It's definitely recommended not to take anything for granted and test which authenticated cipher is fastest in practice.


Deniable Encryption from simple primitives

Deniable encryption is a topic that has been worked on for a while, but recently (in the last year or two), I have seen many more papers.

I haven't kept up with the area but can make a few comments:

The schemes are typically built with public key primitives instead of symmetric key ones (the distinguishing feature not being the symmetry of the keys, rather the use of a clean mathematical structure instead of non-linear block cipher design)
Most schemes encrypt the message bit-by-bit. This means you only have to embed two possible plaintexts (0 and 1) and it is easy to open a message to any possible message.

Scheme based on Elgamal

There is only one scheme that I know that comes close to fitting your scenario. It is from this paper (sorry, couldn't find a non-gated version) and is based on Elgamal.

Properties

The scheme only allows opening to two possible messages however this should be sufficient for your motivating example.
Instead of recovering the different messages using, simply, different keys, it uses two different decryption algorithms. Using the standard Elgamal decryption will give you one message (the fake one) and using a special decryption algorithm will give you the real message. Schemes like these are sometimes called multi-distributional instead of fully-deniable. (Aside: To me, this is reminiscent of steganography: hiding a secret message in innocuous looking data).
This is a plan ahead scheme meaning you have to know what fake message you want to open the ciphertext up to ahead of time
The scheme is receiver-deniable, meaning the receiver of the message (the person performing decrypt) can deny the true plaintext value. For reasons we will see, the sender cannot.
Despite being based on Elgamal, the scheme is actually symmetric key; the consequences we will see.

Construction

Recall normal Elgamal, where Alice sends a message to Bob. Bob has a secret key $x$ and a public key $y=g^x$ (for some generator $g$). To encrypt message $m$, Alice chooses a random value $r$ and computes $\langle c_1, c_2 \rangle = \langle g^r, my^r \rangle$. To decrypt, Bob uses secret key $x$ to compute $c_{1}^{-x}c_2$.

Let's generalize slightly: replace in the ciphertext $g^r$ with some arbitrary value $a$ and $y^r$ with some value b. Then the ciphertext is $\langle a, mb\rangle$. There are lots of a values of $a$ and $b$ that will decrypt to $m$, not just $g^r$ and $y^r$. In fact, any $a$ and $b$ such that $b=a^x$ will work. In this scheme, Bob gives Alice his secret key $x$ (see fine-print below).

Once Alice has $x$, it is simple. She can, for example (my example, not from the paper), set $a=\mathrm{AES}_k(m)$, using an additional shared secret key $k$ (only used for decrypting the true value), and then compute $b=a^x$. For fake message $\hat{m}$, Alice sends $\langle a, \hat{m}b\rangle$. If Bob wants the real message, he decrypts $c_1$ with AES. If he wants to deny, he claims it is an Elgamal ciphertext and decrypts as normal, with $x$, and gets $\hat{m}$.

In the paper, they set $a=g^km$ and $b=y^km^x$. Here, instead of $k$ being a shared secret, there is a shared secret $s$ and $k=\mathcal{H}(s||\hat{m})$. I don't fully appreciate why the construction needs to be this complicated (comments welcome). To decrypt, Bob, uses $x$ and standard Elgamal decryption to recover $\hat{m}$. With $\hat{m}$ and $s$, he computes $k$ and then computes $g^{-k}c_1$ to recover $m$.

Fine-print

Because Alice is given Bob's secret key, this means it is no longer a public key encryption scheme. This has consequences: If Charlie also wants to send messages (standard or deniable) to Bob, Bob either has to use a different key pair (which is odd for what is ostensibly a true public key) or Alice can read all the messages.
If Bob is coerced, he can deny that anything more than standard Elgamal is going on. However, if Alice is coerced, they will ask her what message $m$ and randomness $r$ she used to create the ciphertext. Because she didn't create a standard Elgamal ciphertext, she cannot answer for $r$ or compute a suitable one without solving a discrete log.
Finally, it may be odd for something like disk encryption or file encryption to use Elgamal on the data itself. Usually you'd use it to encrypt an AES key, and then use AES to encrypt the actual data.


The main difficulty in designing what I asked, is coming up with a permutation over a relatively small set, that is easy to compute in the forward direction, but convincingly much more difficult to invert. The least unsatisfactory I have so far is based on the discrete logarithm problem in $\mathbb Z_p$. If $p$ and $(p-1)/2$ are primes, and $g\in\{2\dots p-2\}$ with $g^{(p-1)/2}\not\equiv1\pmod p$, then
$$P:\begin{cases}
 x\mapsto g^x\bmod p& \text{if } x\in\{1\dots p-1\}\\
  0\mapsto0
\end{cases}$$
is a permutation of $\{0\dots p-1\}$ which is easy to compute, but markedly harder to invert. At least, the problem is well-studied, with the best known algorithms the index calculus algorithm and some specialized GNFS variants. Bad news is that the problem is workable for 530-bit $p$, and here I'll be stuck with $p$ like 80-bit (for $b=64$ and other realistic parameters).

It seems possible to build a slow one-way pseudorandom permutation over $\{0,1\}^b$ from such $P$, while keeping about the same security gap (ratio of work in backward to forward direction) as in $P$. I sketch such a construction below. Again this is not fully satisfactory, for the above (family of) $P$ does not have a high-enough security gap, given the order of magnitude I can use for $p$. I badly need a better $P$ !!

Update: The best attacks on $P$ require a heavy pre-computation, then can go from $P(x)$ to $x$ at comparably low cost. I have tuned the following to account for that fact.

The construction requires an expected $c_0\cdot c_1$ evaluations of the above $P$ with $p\approx c_0\cdot2^b$, and forces an adversary trying to brute-force the forward direction to mobilize about $m\cdot2^m$ bits of memory for each few instances run in parallel. Realistic parameters could be $b=64$, $c_0=2^{12}$, $c_1=2^{12}$, $m=20$.

Derive from $K$ a pseudo-random $g$ in $\{2\dots c_0\cdot2^{b-1}\}$ ;
Derive from $K$ an arbitrary permutation $M$ of $\{0,1\}^m$, stored as $2^m$ words of $m$ bits of memory;
Repeat for $c_1$ rounds (identifier by round counter $r$) the following keyed permutation of the current $b$-bit state $s$:

derive from $K$ and $r$ a pseudo-random prime $p$ in range $\big[{3\over4}\cdot c_0\cdot2^b\dots{5\over4}\cdot c_0\cdot2^b\big]$, such that $(p-1)/2$ is prime and $(g^{(p-1)/2}\bmod p)=p-1$ (note: it is advantageous to perform the later test right after insuring that $p$ and $(p-1)/2$ have no small divisors);
Repeat

If $s<\big\lfloor p/2^m\big\rfloor\cdot2^m$ (which is, most of the time)

Replace the low $m$ bits of $s$ with their image through $M$;

If $s\ne0$ (which is, most of the time)

Replace $s$ with $g^s\bmod p$;

Until $s<2^b$.

Note: $s$ temporarily grows to at most $b+\big\lceil\log_2({5\over4}\cdot c_0)\big\rceil$ bits.

For each round, the repeat..until iteration is expected to be executed about $c_0$ times, with an exponential distribution. Increasing the number of rounds $c_1$ makes the runtime more predictable, and less likely that pre-computations for inverting $P$ can help an attack. Each iteration requires one memory lookup, and $\epsilon\cdot\log_2 p$ multiplications $\bmod p$ (we can have $\epsilon\ll1$ with some pre-computation).

(Optionally, the construction could end (or/and start) with some conventional $b$-bit block cipher using key $K_d$ derived from key $K$, perhaps TDES for $b=64$ (with additionally one bit of $K_d$ devoted to making the resulting permutation odd or even, by conditionally swapping output values $0$ and $1$). This, combined with use in other steps of permutations not chosen from $K_d$, convincingly insures that the overall construction is indistinguishable from a random permutation for one not knowing $K$).


From a cryptographic standpoint it is OK to expose a public key in the sense of revealing its value. The most basic assumption in cryptography involving public/private key pairs is that the value of a public key is public; hence its name.

It is extremely important that an adversary can not alter a public key. Any exposition that would allow alteration must be avoided !

Also, a public key is highly characteristic; so one might not want to reveal one's public key, in order to remain untraceable (and anonymous). However, that might not be enough: unless the signature scheme is designed to prevent this, revealing one's signatures might allow traceability (for some systems it is even possible to reconstruct the public key from signatures).

It is correct that not revealing a public key deprives adversaries from information that a sufficiently powerful adversary can use to find (an equivalent of) the private key and break the system. But we need a public key to be public so that signatures made with the owner's private key can be publicly checked. Concluding that one should not reveal a public key is like saying one should keep the location of a bank's safe room secret: that's an assumption ruled out by design, because it would make the design unfit for the intended purpose.

Yes, hypothetical quantum computers usable for cryptanalysis would allow an adversary to attack a known public key of the kind we use now (and in the blockchain). On the other hand

Currently, available quantum computers are less useful for cryptanalysis than available lightsabers are to break into a bank's safe room.
There is plausible reason to fear that in the signature systems that we use, a few signatures are as good as the public key to an attacker with such hypothetical quantum computer usable for cryptanalysis.

Update: regarding

  How does bitcoin for example validate the transaction signature with a public key hash and not public key itself?

It obtains the public key, validate (or reject) it by hashing it and comparing to the trusted public key hash, then validates the transaction signature against the validated public key. For more, see indiscreteLogarithm's answer.


Calculating minimum number of messages hashed a 50% probability of a collision (Birthday Paradox)

You are approximately correct; they are wrong. Their answer calculates the chance of matching a particular value i.e. hash inversion. To see this $k$ tries have a $(2047/2048)^k$ of failing to find a match so you want $k>\log(0.5)/\log(2047/2048)$.
For small numbers we can calculate the exact value of the birthday bound by finding the smallest $k$ such that
$$\prod_{0\le i\le k}\frac{n-i}n=\frac {n!}{(n-k)!n^k}<0.5$$
which in this case is $k=54$.


Encrypting small packets with low data rate

in general, a widely used algorithm to exchange/set up session keys is Diffie Hellman. While exchanging public keys, during the process a shared key is generated, that could also be used to encrypt the communication, without additonal AES.

I do not know how deep your knowledge of asymmetric encryption is- generally, there are two(three) problems that are used. None of them are trivial- factorisation, discrete logarithms and elliptic curves, the latter often combined with the first two.

However, I'm missing out some details that would help- would you rather have a fast encryption (because in that case I would recommend an elliptic-curve based Diffie Hellman, as ECDH) or an easy implementation (standard DH). Is it important that the algorithm is CCA secure(DH is not). How high shall the security be- how much computation power do you have? Can the key of the IPhone change, or should it always be the same? It would also be helpful to know what kind of bluetooth device it is.

Another approach would be using one-time keys. The communication could be initiated by the bluetooth device, which has a storage of several keys that may only be used once- in this case to encrypt the session key.

Last but not least, CTR mode is considered less secure than other cipher modes of AES. Personally, I would recommend GCM for you- because I like it, and because it also provides authenticated encryption, and can be pipelined easily. It has a 128 bit block size. If you expect many errors, OFB could be useful for you... but that goes too far. If you clarify your question a bit more as I‘ve indicated, I can help you out further.


Given just the hash of a file, can I verify that the file contains a specific data block?

Assuming that you know that $h_0$ is the root hash of a Merkle tree for the file, you can be sure that $h_1$ is a hash of a section of the file if you know that it's one of the hashes of the sections one level below the root and you know its sibling hashes, i.e. you have values $(h_1^1, \dots, h_1^{m_1})$ such that $\mathscr{H}(h_1^1, \dots, h_1^{m_1}) = h_0$ where $\mathscr{H}$ is the hash function used to build the Merkle tree. Because of collision resistance, if you have a preimage for $h_0$, it must be the right one, so the $h_1^k$ values are the hashes of the section at a level below.

More generally, you can verify that $h$ is a hash of a section of the file knowing the hashes of the siblings of that section, and the hashes of the siblings of its parents, and so on recursively up to the root. This requires the knowledge of $b \cdot n$ hashes where $n$ is the depth of the section and $b$ is the tree's branching factor. Note that you only need to be given the hash values, you don't need to trust them; they'll all be verified in the process.


Crack linear congruential generator knowing every other word in sequence

Sometimes, rather than do cool math, the easiest approach is brute force!

#include <stdio.h>
#include <assert.h>

int main()
{
    enum { X0 = 3158, X1 = 1888, X2 = 1285, X3 = 1744, X4 = 253, X5 = 722,
           M_START = 3159 };
    for (int m = M_START; m < 10*M_START; ++m) {
        for (int a = 2; a < m; ++a)  {
            int c = X2 - ((X1 * a) % m);
            if (c < 0)
                c += m;
            int my_x2 = (X1 * a + c) % m;
            assert(my_x2 == X2);
            int my_x3 = (X2 * a + c) % m;
            int my_x4 = (X3 * a + c) % m;
            int my_x5 = (X4 * a + c) % m;
            if (my_x3 == X3 && my_x4 == X4 && my_x5 == X5) {
                printf ("m=%d, a=%d, c=%d\n", m, a, c);
            }
        }
    }

    return 0;
}

This code does an exhaustive search.  In less than a second, it spits out:

m=3187, a=2663, c=2627
m=6374, a=2663, c=2627

Now, this is for an LCG that just outputs the values you gave without any gaps.  But we can easily do a little math to work out that if $a^2 \mod m = 2663$, then $a = 1200$, the modular square root of 2663 (in Mathematica, PowerMod[2663, 1/2, 3187]).

Likewise, we can easily find $c$.  Thus, we find $m = 3187, a = 1200, c = 854$.

And thus the actual sequence (with odd-numbered items in bold) is 2679, 3158, 1111, 1888, 497, 1285, 346, 1744, 2982, 253, 1689, 722, 390, 365, 2235, 2587, 1116, 1514, 1064, 2854, …

But maybe you worry that I've used a $\mathrm{O}(n^2)$ algorithm?  What if $m$ were larger?  Well, I was just feeling lazy, that's all.  We can easily drop the complexity to something far less.  It just makes for slightly longer code:

#include <stdio.h>
#include <assert.h>

int modular_inverse(int a, int m)
{
    // Based on code from http://rosettacode.org/wiki/Modular_inverse#C
    int t, nt, r, nr, q, tmp;
    t = 0;  nt = 1;  r = m;  nr = a % m;
    while (nr != 0) {
        q = r/nr;
        tmp = nt;  nt = t - q*nt;  t = tmp;
        tmp = nr;  nr = r - q*nr;  r = tmp;
    }
    if (r > 1) return -1;
    if (t < 0) t += m;
    return t;
}

int main()
{
    enum { X0 = 3158, X1 = 1888, X2 = 1285, X3 = 1744, X4 = 253, X5 = 722,
           M_START = 3159 };

    for (int m = M_START; m < 10*M_START; ++m) {
        int diff0 = (X1 - X0);  if (diff0 < 0) diff0 += m;
        int diff1 = (X2 - X1);  if (diff1 < 0) diff1 += m;
        int diff2 = (X3 - X2);  if (diff2 < 0) diff2 += m;
        int diff3 = (X4 - X3);  if (diff3 < 0) diff3 += m;
        int diff4 = (X5 - X4);  if (diff4 < 0) diff4 += m;

        // diff1 = a * diff0   =>   1/diff0 * diff1 = a
        int inv_diff0 = modular_inverse(diff0, m);
        if (inv_diff0 < 0) continue;
        int a = (diff1 * inv_diff0) % m;

        int my_diff1 = (a * diff0) % m;
        int my_diff2 = (a * diff1) % m;
        int my_diff3 = (a * diff2) % m;
        int my_diff4 = (a * diff3) % m;
        assert(my_diff1 == diff1);

        if (my_diff2 == diff2 && my_diff3 == diff3 && my_diff4 == diff4) {
            printf ("m=%d, a=%d\n", m, a);
        }
    }

    return 0;
}

This version spits out its answer essentially instantly, taking 0.001 seconds to run the program.

m=3187, a=2663

From here, we can then figure out $c$ and then proceed as above.

BTW, if you enjoy more of a challenge, feel free to check out this question I asked a while back.


Worth taking performance hit of HMAC to gain additional security?

If we assume that 1 and 2 are true then HMAC-SHA-512 is a better choice.

For the time comparison, as stated Paul Uzsak, if there is no specific time relevant problem around ~50% faster shouldn't be considered. If more secure, then use it.

For your comment;

The shatter attack on SHA-1 requires a degree of freeness in the hashed data as in PDF's. This attack may or may not apply to other formats, but still, SHA-1 is considered broken and it is already non-standard, kick out.

With the identical-prefix collision attack probably you cannot forge the MAC with this method. We haven't seen any complicated attack that uses the shatter attack to break some other constructions, yet.

The output of SHA-1 is 160-bit and it is in the generic birthday-attack range for our computing powers, especially for a collective like bit-coin miners who reached $2^{91.6}$ SHA-256 hashes per year on 25 September 2018.

512-bit is not prone to generic collision attacks. This will require $2^{256}$ hashes to find a collision with probability 50%. For SHA-256, it is still impractical for today's standards $2^{128}$ and this is equal to brute-forcing AES-128 up to some constant.

When a new attack occurs for a hash function we have to look at it so that what the attack can be used when the hash function used in HMAC construction. However, as noted by the Forest

  In particular, an HMAC demands much weaker security guarantees from the hash function than many other applications it may have. It only requires weak collision resistance from the underlying hash.

For the security case You should be prepared to move into new standards. Even if there is not an attack to carry a collision attack into a HMAC construction, you should immediately move away from that hash function into more secure one.

note: Weak collision resistance is the second pre-image resistance:

it is computationally infeasible to find any second input which has the same output as any specified input, i.e., given $x$, to find a 2nd-preimage $x' \neq x$ such that $h(x) = h(x')$.


Enigma ring settings - is the relative location of the turnover all that matters?

Mechanically the only effect of the Ringstellung is to determine the rollover points as you surmise. This is easily inferred from descriptions of Enigma models in Alan Turing "Prof's Book where "comic strip" and paper Engimas only use the Ringstellung information to determine rollovers.
Cryptanalytically the effect is that if the message indicator or "window position" of the machine is known but the Ringstellug is not, then nothing is revealed about the "wheel position" or "rod position" as it was referred to at Bletchley Park. There were instances when such information was known, but it was not always easy to bring to bear on the cryptanalysis. A notable exception was the Herivelismus exploitation of human error that noted that common message indicators were often correlated with Ringstellung settings. This was a very useful step in separating out one part of Enigma settings and solving for it separately early on in the war.


What happen if a asymmetric crypto-system deals with only one key

Well, each party would know that the other party uses the same key, because they would probably have the same public key.

Now, if some person I have never met before would use the same key as me, I would go into paranoid panic mode. That person could decrypt all messages that were only meant to be decrypted by me (and of course vice versa).

However, if I only use my public-private key pair for communication with this one person, and nobody else, it would be not that bad, because the messages are no secret for either of us anyway. BUT: you never know if some stranger takes care of his passwords the same way as you do. An attacker could capture the pub keys, see that you both use the same key, and in case the other person is a little sloppy, and the attacker would get hands of the other persons keys, he could not only decrypt messages meant for your partner, but also messages meant only for your eyes.

When it comes to security, it is always good to be as paranoid as possible, if it does not take that much extra effort, and avoiding to use the same key as someone else (as unlikely as this is) is definitely something that is easily avoidable, with quite a big impact. (And while there might be even fancier attacks for scenarios like that, these are the most obvious points, which are enough to say 'don't do that')


Basic Idea: For simplicity, assume the server $S$ is trusted.

Then all the server has to do is to prove that it has the private key $(n,d)$ corresponding to its public key $(n,e)$ which is trusted, say, via a PKI.

The client uniformly generates a random value $X \in Z_n,$ keeps it private, and then encrypts it into $$Y=X^e ~(mod~n)$$ and sends $Y$ to the server. The server
obtains $$Z=Y^d~(mod~n)=X^{ed}~(mod~n)$$ and sends $Y$ back to the client.

By the uniqueness of inverses modulo $\varphi(n)$ we know that $$ed\equiv 1~(mod~\varphi(n))$$ if and only if the private key is correct. Thus all the client needs to do is to check that $Z$ equals the original $X$ it had generated.

I have used plain RSA with no randomisation or encapsulation. There are many wrinkles if we want to protect against replay attacks, etc., but your question sounds like a basic question.

Edit: (Thanks to @fgrieu) copied for completeness of answer, hope he/she doesn't mind.

  In challenge/response, the answer's server is more generally known as
  prover; and the answer's client as verifier. The question also hints
  at using RSA signature for that: verifier generates and sends random
  $X;$ prover signs it as $Y=X^d~(mod~n)$ and sends signature $Y$;
  verifier computes $Z=Y^e~(mod~n)$ and verifies that $Z=X.$ The
  answer's method given above uses encryption, with the advantage that $X$
  is not known to attackers and can be used to derive a shared secret
  key. But the signature method allows $Z$ to carry information that the
  prover has signed.


Process of dividing 168bit key into 56bit keys in TripleDES

Yes. The keys are indeed used in a linear manner.

In particular, they are used in $E$-$D$-$E$ mode: encrypt using first 56 bits as key, decrypt using next 56 bits as key and then again encrypt using final 56 bits.

This way its possible to use triple DES (which is officially called TDEA) for the DES, 2-DES and 3-DES variations. The first would use $K_1$-$K_1$-$K_1$ as keys, the second would use $K_1$-$K_2$-$K_1$ as keys and the full 3-DES would use $K_3$-$K_2$-$K_1$ as keys. Sometimes the 2-DES and 3-DES keys are also called ABA and ABC keys respectively.

DES uses one bit of each byte as parity, but this bit is not always validated by implementations. So triple DES keys with parity use 64, 128 or 192 bits. This explains why some implementations allow the output of an MD5 hash - which is 128 bits - to be input as 2-DES key without any error.

References :

FIPS 46-3
Wikipedia on triple DES


Combining multiple cryptographic keys to generate an encryption key

As long as the total entropy (unpredictability measured in units of bits) of the inputs is at least as large as the derived key size then it is okay in practice.

Reasons why it might not be good in theory (but really is harmless):

In theory you lose a tiny bit of entropy due to collisions. (Small enough not to ever ever ever matter for short inputs, acceptable mainstream hash functions, and greater than 128 bits of output.)
If someone hashes a known value together with a uncertain low entropy input, then reveals that value, an attacker can then enumerate likely values for brute forcing the low-entropy input value. Since the inputs are secret keys (with high entropy) and since the output is kept secret, it is no concern.
Some hash functions could be designed to be resistant to collision, first preimage, and second preimage attacks. But that doesn't guarantee the output is pseudorandom. It's okay because SHA-2 has enough scrutiny to believe it's practically a random oracle. And even if collisions or minor biases are found some day, the fact that inputs contain long random uniform bit strings means it won't effect key derivation.

I assumed your SecretKeys are symmetric shared secret (uniform full entropy) keys. (I don't know why you would want to combine shared secret keys to make a shared secret key and why the process that made the input keys can't be used.)

You can also hash public keys (but they add zero entropy because of their publicness) and Diffie-Helman style shared secrets. Key exchanges in protocols like TLS can use key derivations that are a function of inputs including a DH shared secret, public authentication keys, and protocol handshake details fed to a hash function to generate symmetric keys used for encryption and authentication.


Technical details of attack on Android bitcoin usage of SecureRandom

It looks like there are really two potential problems. From the mailing list

  all private keys
  generated on Android phones/tablets are weak and some signatures have
  been observed to have colliding R values, allowing the private key to
  be solved and money to be stolen.

Recall that with bitcoin

  Transactions are cryptographically signed records that reassign ownership of Bitcoins to new addresses. Transactions have inputs - records which reference the funds from other previous transactions - and outputs - records which determine the new owner of the transferred Bitcoins, and which will be referenced as inputs in future transactions as those funds are respent.

  Each input must have a cryptographic digital signature that unlocks the funds from the prior transaction. Only the person possessing the appropriate private key is able to create a satisfactory signature; this in effect ensures that funds can only be spent by their owners.

So, first, if all private keys generated on an Android device are weak, anyone could (potentially) figure out your private key and basically transfer the money in your wallet to themselves. Weak private keys would be the result of the RNG not being very random in practice so there is only a small pool of random numbers being used to generate the private key (e.g., in the debian openssl key generation bug, there were some 65k private RSA keys being used due to a poor RNG, that is small enough to be enumerable).

Now, specifically on to what you asked about colliding R values. Bitcoin uses ECDSA for signing. For my description below, I'll use non-EC DSA to describe the problem for simplicity.

In DSA, the private key is a randomly generated value $x$ and the public key consists of $(p,q,g,y)$. For details on $p$, $q$ and $g$ see Parameter Generation. $y$ is computed as $y=g^x\bmod{p}$.

To compute a signature of a message $m$, we compute:
$r=(g^k\bmod{p})\bmod{q}$ (where $k$ is a randomly chosen value)
$s=k^{-1}(H(m)+xr)\bmod{q}$ (where $H$ is a hash function)

The signature is then $(r,s)$. I'm assuming that it this $r$ that they are saying is colliding. This could happen if the RNG is weak and you generate the same $k$ twice.

So, the question then is why would colliding $r$ values cause a problem. As I said, a colliding $r$ comes from generating the same value $k$ twice. I found the following note on wikipedia interesting:

  With DSA, the entropy, secrecy, and uniqueness of the random signature value k is critical. It is so critical that violating any one of those three requirements can reveal the entire private key to an attacker. Using the same value twice (even while keeping k secret), using a predictable value, or leaking even a few bits of k in each of several signatures, is enough to break DSA.

  In December 2010, a group calling itself fail0verflow announced recovery of the ECDSA private key used by Sony to sign software for the PlayStation 3 game console. The attack was made possible because Sony failed to generate a new random k for each signature.

This works as follows (adapted from here)

Say you have two signatures with colliding $r$ values. Call them $(r,s_1)$ and $(r,s_2)$.

Compute: $s_1-s_2=k^{-1}(H(m_1)+xr)-k^{-1}(H(m_2)+xr)$
Redistribute: $s_1-s_2=k^{-1}(H(m_1)-H(m_2)+xr-xr)=k^{-1}(H(m_1)-H(m_2))$
Thus: $k=(H(m_1)-H(m_2))/(s_1-s_2)$, so you know $k$.
Then you compute the private key $x$ as $x=((s\cdot k)-H(m))\cdot r^{-1}\bmod{q}$ using one of the signatures.

So, even if your private key is not weak (say you generated it on another machine then moved it to the android device), signing two transactions with the same $k$ allows someone to discover your private key.

Recommendation for resolving the problem
The bitcoin folks are recommending that bitcoin software developers switch to /dev/urandom, then in their apps have all users generate a new private key, and transfer all bitcoins to the new private key.

Note
The problem only seems to affect Android's SecureRandom class. Presumably Google could fix SecureRandom, in which case Android devices could switch back to using SecureRandom (instead of /dev/urandom). Private keys would still need to be regenerated.

Why SecureRandom Fails
The details of why SecureRandom fails to generate good random numbers were presented at RSA-CT 2013 in this paper. The problem happens when creating a self seeding instance of SecureRandom (i.e., no seed, either through the constructor or through setSeed method, is passed by the programmer). The seed is stored in a buffer with the seed data, a counter, and padding. In the case where no seed is passed by the programmer, a bug in the code caused a pointer into the buffer to not be updated, which causes other code to overwrite portions of the seed. This data should be appended to the seed instead. See Figure 4 of the linked paper.

The result is that there is only 64 bits of entropy in the buffer. This is much, much too low.


Altering file for to create partial matching MD5

Yes, you can, but the amount of bits (that get translated into characters if you'd use, say hexadecimal encoding) that will be identical to the original hash are of course limited.

Say a hidden file in the folder contains a large counter $c$. The total hash $h_2^c$ will have a pseudo-random value. The first bit of the hash will be identical to the first bit of hash $h_1$ with a probability of $1 \over 2$. That the next bit also matches has a probability of $1 \over 4$, which is ${1 \over 2} \times {1 \over 2}$ or $2^{-2}$. If you try enough counter values you will quickly find a hash where the first few bytes are identical.

Of course the chances of finding a full MD5 hash of 128 bits this way are very close to zero. 48 bits or so may be doable (your counter $c$ should be at least 48 bits but preferably larger, say 64 bits).

If the contents of the first folder $f_1$ can have a pre-calculated value inserted then you may be able to attack MD-5 and create a fully identical hash as MD5 is rather broken. But from your description this doesn't seem to be the case.

Furthermore, if $h_1$ is set then you cannot take advantage of the birthday problem, which halves the security of the hash. It's much easier to find two hashes $h_x$ and $h_y$ that match for $n$ bits than finding a single $h_x$ that matches a preset $h_1$.


Why haven't any SHA-256 collisions been found yet?

I think you underestimate just how large $2^{256} \gg 64^{36}$ is.

  How has a collision never been found?

It will take a very, very, very, $\text{very}^{\text{very}}$ long time to find one. For comparison, as of January 2015, Bitcoin was computing 300 quadrillion SHA-256 hashes per second. That's $300 \times 10^{15}$ hashes per second.

Let's say you were trying to perform a collision attack and would "only" need to calculate $2^{128}$ hashes. At the rate Bitcoin is going, it would take them

$2^{128} / (300 \times 10^{15} \cdot 86400 \cdot 365.25) \approx 3.6 \times 10^{13}$ years. In comparison, our universe is only about $13.7 \times 10^9$ years old. Brute-force guessing is not a practical option.


Linear ciphers

If the s-box is the identity mapping, then the remaining cipher is linear.

If the cipher is linear (over $GF(2)$), then the expression for any given bit will be equal to: $$c_i = m_i \oplus m_j \oplus m_k \oplus \dots \oplus k_a \oplus k_b \oplus k_c \oplus \dots$$

For some varying quantity of and values of $a, b, c, j, k, \dots$ per ciphertext bit.

Basically, each ciphertext bit is equal to a xor of plaintext bits and key bits (and any round constants, as applicable).

Chosen plaintext attack

A linear cipher can be broken with 1 chosen plaintext attack.

Submit a block of all 0 bits as the plaintext to the encryption oracle.

Since the plaintext has no influence on the key schedule, the key bits that influence each ciphertext bit do not vary between invocations on different plaintexts. When the message is all 0 bits, then the equation for any given ciphertext bit is simply $$k_a \oplus k_b \oplus k_c \oplus \dots$$

Where the quantity and values of $a, b, c, \dots$ vary for any given ciphertext bit (round constants omitted for simplicity).

The resultant ciphertext will be equivalent to an encryption/decryption key.

It may/will not be the key that was used to evaluate the cipher, but it will work to recover the plaintext from a ciphertext, or vice versa.

To do so, simply XOR the equivalent key with a ciphertext, then run the "AES"* decryption routine without the addRoundKey step.

Proof of concept located here

*"AES" is in quotes, because AES is a standard. Once it is modified (e.g. by changing the s-box), it is not AES anymore.


Consequence of a change on the Guillou-Quisquater Protocol

Yes it proves that $y \ne 1 \pmod{n}$ is not an $e$-th root. That is, no $x$ exists such that $x^e = y \pmod{n}$. In particular, if $e | \phi(n)$ then for any $x$ it holds that
$\left( x^{ \frac{\phi(n)} {e}} \right)^e = 1 \ne y$.

This probably means one last final conclusion designed as a homework.

Regarding GQ protocol: prover will be unable to pick an $r$ such that
$a = r^e \ne 1$.


Using the same symmetric key in both directions?

It can be safe, but using the same key in both directions adds several things you need to be careful about:

One thing you need to make sure is not a problem is if an attacker takes a message from Alice to Bob, and sends it back to Alice as if it were from Bob.  Since Bob to Alice communications use the same key, Alice might decrypt the message, and act as if it came from Bob.  There are several possible defenses against this; the easiest (if you include a Message Authentication Code, which you really ought) is to include a direction flag within the authentication data; that way, a wrong way message would be rejected.
If you use a nonce-based encryption method (such as Counter Mode or GCM), you need to make sure that both sides don't use the same nonce.  This can be as easy as telling Alice to use even nonces, and Bob to use odd ones.  However, if you are going to use the same password (and hence the same keys) for multiple sessions, this would indicate that a nonce-based encryption method is probably the Wrong Answer; something like CBC mode + HMAC would make rather more sense.

However, even though it can be done safely, I would suggest you avoid the issue entirely.  Instead, when you send your password to the KDF, ask the KDF for twice the key length (say, 256 bits instead of 128), and use the first 128 bits for Alice to Bob messages, and the second half for Bob to Alice messages.


How do these figures represent a boolean function?

The image description page for the larger image describes it pretty well.

Specifically, the line at the top of the figure:

shows the 4-ary Boolean function $f(x_1, x_2, x_3, x_4) = x_1 x_2 + x_3 x_4$ in a graphical form.  Specifically, interpreting each possible input as a 4-bit binary number (e.g. $(0, 1, 0, 1) \mapsto 0101_2 = 5$), the corresponding square on the line (starting from square 0 on the left, and counting up to square 15 on the right) is colored red if the output of the function is 1, and white if it is 0.

The square below the shows the Walsh matrix of order 16, the rows of which correspond to the 16 linear 4-ary Boolean functions (a.k.a. the Walsh functions), using the same representation as for the top row.  The squares marked with dots are those where the nonlinear function shown at the top differs from the linear function described by the row, and the number on the right counts the number of such dots on the line.

The second square below that is the complement of the Walsh matrix, showing the 16 non-linear affine 4-ary Boolean functions (i.e. functions which are linear except for the addition of a non-zero constant, which for Boolean functions can only be 1).  The dots and the numbers have the same meaning as before.

Looking at the numbers of the right, one can see that the number of inputs at which the given function $f$ differs from each affine 4-ary Boolean function is either 6 or 10 = 16 − 6, demonstrating that $f$ is equidistant (in the sense of absolute number of differences modulo 16) from each affine 4-are Boolean function, and is therefore a bent function.

The other image just contains four smaller but otherwise similar subfigures, showing that each of the four 2-ary Boolean functions of Hamming weight one (i.e. producing the output 1 for only one set of inputs) is also a bent function.


MICKEY 2.0: Mutual irregular clocking, register states

In any keystream generator, if the state repeats, so does the keystream; which, under some standards assumptions, can be detected, and leads to a serious break (e.g. if the beginning of the plaintext is known for length a little above $k+\log_2k$ bits, where $k$ is the period of the keystream, then the period $k$ and the rest of the plaintext can be found). A necessary condition for security is thus that odds of the state repeating are negligibly low. This is insured (odds are zero) if the quoted property holds:

  ... the state of the generator does not repeat within the generation of a single keystream sequence ...

and that's why that property is desirable: it insures there is no class of weak keys leading to attack.

I'm not seeing assertion in the article, or simple proof, that “the state of S does not repeat within the generation of a single keystream sequence”. Rather, I see the reasonable assertion, without formal proof, that starting from a generator S based on iterating a lossless function, and using another unrelated generator R as an excitation to S by a combination with XOR keeping the iterated function lossless, it seems unlikely that the resulting generator S' ends up having a period shorter than R (that could occur only for a limited number of R having some sort of tight relation to S; perhaps that's even demonstrable). Rather, it is expected (in the absence of feedback of S to R, and if the function used in S is random enough) that S' has period a large multiple of the period of R, with the large factor commensurate to the square root of the number of possible states for S.


Identify similar contents in encrypted data?

Not if the encryption algorithms work. And not even if it's the same encryption algorithm. This is a consequence of one of the properties required for an encryption algorithm to be considered secure: ciphertext indistinguishability under chosen ciphertext attack. If an adversary can send ciphertext 1 for decryption, and from that learns something about ciphertext 2 (such as a similarity in their corresponding plaintext), then this property is violated.


Protocols for Authentication and Key Establishment [1] By Colin Boyd is considered very good book. That has plethora of examples, proofs etc. in very understandable language and format.

Another book is Modern Cryptography Theory And Practice [2] by Wenbo Mao. Few chapters have very good introduction to designing protocols in attack-fix cycles.

and few more

Boyd, Colin, and Anish Mathuria. Protocols for authentication
and key establishment. Springer, (2003).
Wenbo, Mao. "Modern cryptography: theory and practice." Publisher: Prentice Hall PTR,
Copyright: Hewlett Packard (2004).
Cremers, Cas, and Sjouke Mauw. Operational semantics and verification of security protocols Berlin: Springer, 2012. This is an excellent single book that covers all the aspects needed in great detail and rigor.
Bella, Giampaolo. Formal correctness of security protocols. Heidelberg: Springer, 2007.


Robust stream cipher using AES encryption block

You should use CTR mode. You will not need to have random IV every time, rather you will use incremental counter and set it to zero once you change the KEY. You should not encrypt more than ${2^{n/2}}$ blocks.

CTR mode allows both parallel encryption and decryption without padding. You can even precompute the CTR encryptions in Idle time and just Xor it with input stream to generate ciphertext once required.

OFB mode have cyclic issue and if cycle is small, the generated key stream will start repeating itself.

In fact you should use GCM to get authenticated encryption. see Disadvantages of various Authenticated modes of Operation or how to choose between CCM and GCM

Here is a List of Advantages and Disadvantages of Modes of Operation

For good comparison of mode of operations, please see
Evaluation of Some Blockcipher Modes of Operation


Security model scalar multiplication in NaCl

Since "crypto_scalarmult is the function
  crypto_scalarmult_curve25519", does this mean that Curve25519 does
  not provide any guarantees for the DDH problem to be hard?

No, it just means, that the NaCl specification or API, which is different from the NaCl implementation / library, makes no guarantees about the DDH problem being hard in the group being used. The implementation however may of course go beyond what is guaranteed by the API and use a group where DDH is hard, such as Curve25519.

  If so, how can one hash group elements to achieve this?

The output of the crypto_scalarmult function essentially is a chunk of bytes. You can then use your favorite hash function (e.g. SHA-3-256 or SHA-256) or preferably your favorite key-based key derivation function (KBKDF) (e.g. HKDF) to derive symmetric key material for bulk encryption.

  How does one implement elliptic curve El-Gamal using this
  implementation, if possible at all?

ElGamal requires the message to be represented as a group element which is not trivially possible to do in an (easily) invertible way and thus I strongly discourage anyone from using EC-Elgamal and instead use ECIES.

However you asked and I shall answer (using the notation from the HAC (PDF)):
Let $\alpha$ be your generator of the (sub)group. Let $\beta$ be your recipient's public key and $a$ be his private key. $\beta$ can be generated from $\alpha$ as $\alpha^a=\beta$, which maps 1-to-1 to a call to crypto_scalarmult.

For encryption you then pick a random $k$ which is smaller than the group's order and compute $\beta^k$ and $\gamma=\alpha^k$ which both can be done by single calls to crypto_scalarmult and then you compute $\delta=m\cdot(\beta^k)$, e.g. you apply the group operation to $m$ and the buffered $\beta^k$. Your ciphertext of the plaintext $m$ is now $(\gamma,\delta)$.

Decryption is even easier, you compute $\gamma^{q-a}$ where $q$ is the (sub)group's order and then perform a group operation using $\gamma^{q-a}$ and $\delta$, the result will be $m$.


What is a white-box implementation of a cryptographic algorithm?

This article is a nice introduction to the concept of white-box cryptography. It can be viewed as the devious cousin of code obfuscation.

In simpler words: usually, security of a cryptographic algorithm is studied in the "black-box" model: e.g., for symmetric encryption, the attacker is given access to a "device" which runs the encryption algorithm with a given key, and can submit plaintexts and ciphertexts, the goal of the attacker being to be able to decrypt a given block without submitting that exact block as ciphertext. In the "grey-box" model, the attacker also has access to some partial side-channel information; this is where power analysis fits. In the "white-box" model, the attacker has full access to the internal state. The white-box model is meant for: "the algorithm runs as software on the attacker's own computer".

White-box cryptography is less ambitious, and correspondingly a bit less impossible, than the Holy Grail of video game vendors, namely preventing any kind of reverse engineering; WBC aims at protecting "just" cryptographic keys. WBC studies techniques by which a white-box implementation could be made, and also what security characteristics could be achieved assuming that a white-box implementation exists.

Brecht Wyseur wrote a PhD thesis on white-box cryptography (there is also a downloadable presentation). See also this site (from B. Wyseur).


How secure is a lagged fibonacci sequence for encrypting brief messages?

Your key only seems to consist of n, which should be easily brute forced. So not very secure is the only answer that can be given. n could be very large (a 128 bit number or so), but in that case this scheme seems very inefficient.

Please note the remarks on this kind of generator here and here. So even if it is secure, it may be very tricky to show that it is secure (for a large n). There are plenty of better stream ciphers to choose from.


Zero byte header in RSA-OAEP vs. RSA-PSS

I think it actually is, lets read through chapter 8.1.1 Signature generation operation:

EMSA-PSS encoding: Apply the EMSA-PSS encoding operation (Section
9.1.1) to the message M to produce an encoded message EM of length
\ceil ((modBits - 1)/8) octets such that the bit length of the
integer OS2IP (EM) (see Section 4.2) is at most modBits - 1, where
modBits is the length in bits of the RSA modulus n:

    EM = EMSA-PSS-ENCODE (M, modBits - 1).

Note that the octet length of EM will be one less than k if
modBits - 1 is divisible by 8 and equal to k otherwise.  If the
encoding operation outputs "message too long," output "message too
long" and stop.  If the encoding operation outputs "encoding
error," output "encoding error" and stop.

Now the sentence "Note that the octet length of EM will be one less than k if modBits - 1 is divisible by 8 and equal to k otherwise." clearly indicates that this is similar to OAEP encryption.

Furthermore, if you look at the encoding operation in 9.1.1:

11. Set the leftmost 8emLen - emBits bits of the leftmost octet in
maskedDB to zero.

12. Let EM = maskedDB || H || 0xbc.

You'll see that the leftmost (most significant bits) are set to zero.


Dmitry said that a collision in the xor can be found with a generalized birthday attack.

Actually, it's a lot worse than that; second preimages of sufficiently long messages can be found in polynomial time; hence an enormous block size (which might help against the birthday attack) doesn't help.

Let us call the size of the output of the ideal block cipher $n$.  Then, let us consider a message that consists of (at least) $n$ blocks; and for each block, we consider two distinct alternatives, at position $i$, we would have arbitrary selected blocks $M_i$ and $M'_i$.

We would then compute $H_i = E_i( M_i ) \oplus M_i$ and $H'_i = E_i( M'_i ) \oplus M'_i$.

If we have a target value $Z$ for the exclusive or's (which we would have for a second preimage problem), we would then consider what sum of $H_i$ and $H'_i$ would exclusive-or to the target values; this can be viewed as a linear algebra problem, and can be solved with, say, Gaussian elimination in time $O(n^3)$


Is it required to use a random IV for AES-CBC with random key per message?

You can use a null IV for all files ONLY if each file will be encrypted with a unique key. If you want to reuse the key, it's safer use a random IV for each file.

The issue is reusing the IV with the same key, when you do that, you reveal which files have the same first bytes. When you use a different key for each file, you don't have this problem.


What is the idea behind hashing the QueryString in OAuth?

I asked @eranhammer on Twitter and the idea is to protect the URL from tampering.


Small roots of bivariate modular linear equation?

All solutions of such an equation in $\mathbb{Z}$ are of the form $x=x_0-\frac{ka}{gcd(a,b)}, y=y_0+\frac{kb}{gcd(a,b)}$ for $k\in \mathbb{Z}$, where $(x_0,y_0)$ is any solution.

Look at these numbers modulo $p$ and you'll have a parameterization of a family of solutions to your equation. This might help you find some small solutions, depending on the size of your parameters $X,Y$.

Now, note that the equation $$ax+by=c+p$$ will also give solutions (or replacing $p$ by any $\theta p$ for $\theta\in \mathbb{Z}$), since when in $\mathbb{F}_p$, the equation is the same. I'll let you think if the solutions are the same.


Well, whether $AES'$ is as secure as $AES$ depends on the length of $k_1, k_2$.

If they are both 128 bit, then what you effectively have is a standard 128-bit AES, except that prior to round 6, you replace the running key with an independent key (and you tweaked the last round, but that's cryptographically harmless).  Now, it is never a good idea to do random tweaks on ciphers, however, this appears reasonable to conjecture that this one is harmless; that the security of the cipher does appear unlikely to depend on the relationship of the subkeys in round 5 and round 6 of standard AES.  This, of course, assumes that we are interested solely in the standard attacks (chosen-plaintext, chosen-ciphertext); if we are allowed to consider related-key attacks, this construction may well be weaker.

On the other hand, if $k_1, k_2$ are each 64 bits (with the $AES^r$ subkey derivation process being somehow modified to take a 64 bit key), then what we have is definitely weaker than standard AES (even though $AES'$ takes a 128 bit key); even against a known-plaintext scenario.

This is due to a standard meet-in-the-middle attack, where to find the values $k_1, k_2$ that solve the equation:

$AES'_{k1,k2}(P) = AES^r_{k1}(AES^r_{k2}(P)) = C$

for some known plaintext/ciphertext blocks, the attacker just computes:

$F(k_1) = AES^r_{k2}(P)$

$G(k_2) = {AES^r_{k1}}^{-1}(C)$

for all $2^{64}$ values of $k_1, k_2$, and searches the lists to find a pair $F(k_1) = G(k_2)$.  This gives him solutions for $AES'_{k1,k2}(P) = C$ in $O(2^{64})$ time.


Does Camellia-GCM use Camellia-CTR to create GCM Hash?

GCM is a mode of operation for a 128-bit blocksize block cipher that turns it into an authenticated encryption scheme. It doesn't care about whether you're using AES, Camellia, Twofish, Serpent or MARS. It will work the same way for all of these block ciphers. So yes, Camellia-GCM uses Camellia-CTR internally in exactly the same way AES-GCM uses AES-CTR internally. with Camellia getting the exact same inputs as AES.


Threshold cryptosystem with a required share

Here's an easy way to do it:

Take your secret $S$, and select a random value $R$ of the same size, and compute $T = S \oplus R$
Give the accountant the value $R$
Use a $(k-1, n-1)$ secret sharing method to share $T$ to the other parties.

The accountant plus any set of $k-1$ other parties can reconstruct the secret.  And, any smaller subset cannot get any information on the secret $S$.


Attack on DSA modification with bad hash function

With my new idea I seem to solve the problem and answer my question, so I'll go ahead and post it as the answer. I choose the new $m'$ as $m'=t+m$ with $t>0$.
Now the verification works like this:

$v'=g^{m'w} y^{rw}=g^{m'w+xrw}=g^{tw+mw+xrw}=g^{tw} \cdot g^k=r' \mod q$

So my new $r'=g^{tw}r=g^{ts^{-1}}r$

This means I can create a legit signature to any $m'=t+m$ which is $(r',s')=(g^{ts^{-1}}r, s)$. Correct?


What kind of machine can generate 100-400 digits prime number? RSA

You can simply combine mathematical operations on 64 bit numbers to create mathematical operations on bigger numbers. Just like a computer can combine bit operations to create operations on bytes and - yes - 64 bit values. In the end it is all binary arithmetic, calculations in current computers are performed on values of just 0 and 1.


I am trying to generate a permutation of polynomial with order m

I believe this is on topic. In general this is a math question and there are various permutation polynomial families, such as Dickson polynomials, see Wikipedia under "permutation polynomials".

In the case $N=2^m$ (which seems to be the one you are interested in, though the term "order" instead of "degree" is problematic) there is a nice paper discussing such polynomials, by Ron Rivest entitled "Permutation polynomials modulo $2^w$ $w\geq 1.$ I state the main result.

$P(x)=a_0+a_1x+\cdots+a_d x^d$ over the integers modulo $2^w$ is a permutation polynomial if and only if $a_1$ is odd, $a_2+a_4+a_6+\cdots$ is even, and $a_3+a_5+a_7+\cdots$ is even.

See the paper for more related results, e.g., on polynomials generating latin squares mod $2^w$, just google "Rivest permutation polynomial".


justification for method to factorize n knowing RSA private exponent d

We have $y^2-1 \equiv 0 \pmod n$, meaning that $y^2-1 = (y+1)(y-1)$ is a multiple of $n$. $y \not \equiv \pm 1 \pmod n$ means that neither of $y+1$ and $y-1$ is a multiple of $n$. Now, clearly $\gcd(y-1,n)$ is a divisor of $n$; we want to show that it is not $1$ or $n$.

It cannot be $1$, because that would imply that $n$ divides $y+1$, which we assume is not the case.
Likewise it cannot be $n$, because that would imply that $n$ divides $y-1$.

The reason we take $y$ such that $y^2 - 1 \equiv 0 \pmod n$, by the way, is so that we have a good chance of finding a non-trivial factor. Indeed, if we just pick any random $y$, it is overwhelmingly likely that $\gcd(y-1,n) = 1$, which does not help us.


How to get ramdom number between 1 and 2048 from /dev/hwrng?

There are different versions of jot, and they use different sources of randomness. The Debian man page states:

Random numbers are obtained through random(3).

s defaults to a seed depending upon the time of day

random is not cryptographically secure. This is not explicitly mentioned in the documentation, so it's a good guess that it isn't¹. Even if it was, The seed being the time of day is very predictable. So jot on Debian is not at all suitable to generate a key or anything else that needs to be secure.
The OpenBSD man page states:

Random numbers are obtained through arc4random(3). Historical versions of jot used s to seed the random number generator. This is no longer supported.

arc4random on OpenBSD is secure, as documented in the man page². So on OpenBSD, your script generates a passphrase securely, with $24 \log_2(n)$ bits of entropy where $n$ is the length of the word lists (assuming the word lists has no duplicates).

If you have GNU utilities, use shuf. It can be instructed to use secure randomness:

--random-source=file
Use file as a source of random data used to determine which permutation to generate. See Random sources.

By default these commands use an internal pseudo-random generator initialized by a small amount of entropy, but can be directed to use an external source with the --random-source=file option. (…) The set of available sources depends on your operating system.

On Linux, /dev/urandom is secure except on a freshly installed system that doesn't have a hardware random generator. Since your platform has a hardware random generator, you don't need to worry about the initial seeding of the system random generator.
So with GNU coreutils, your script can just be
shuf --random-source=/dev/urandom -r -n 24 <bip39.txt

¹I confirm that guess.
² Historically, arc4random used RC4, which is now broken. The output is biased, which would reduce the entropy of the resulting key, but not enough to break it. In any case OpenBSD switched to a different algorithm (currently ChaCha20), so arc4random is safe. Other modern BSD variants have switched arc4random to be secure as well, but beware that older releases of FreeBSD and NetBSD were insecure..


I believe you misunderstood the linked question and probably the definition of PRG.

PRG maps a key $K$ (also called seed) of bit length $l$ into a bit sequence $x\in\{0,1\}^n$ of bit length $n$. PRG is secure if the generated bit sequence $x$ is computationally indistinguishable from truly random.

What the answer to the linked question has shown is that the given PRG's output is easily distinguishable from random because two bits in fixed positions of the PRG's output are equal for any key $K$.

PS: Probably the questions like the linked one implicitly assume the following construction that creates PRG from PRF:

Suppose we have a PRF $F:K\times D \to R$ which map keys $K=\{0,1\}^l$ and domain $D=\{0,1\}^n$ into range $R=\{0,1\}^m$. Now, we can build a PRG $G: K\to \{0,1\}^{n+m}$:

$$G(k)[x]=F(k,x)$$

Note that $x$ is an argument of $F$ but not of $G$; on the LHS $x\in\{0,1\}^n$ denotes a position of a bit sequence of length $m$ in PRG output.

In the simplest case $m=1$, that is PRF $F$ outputs just one bit: $R=\{0,1\}$, and $x\in\{0,1\}^n$ denotes bit position in $G$ output.


NIST's Public-Key Post-Quantum cryptographic public calling

The second paragraph in the link you shared says the following:

  It is intended that the new public-key cryptography standards will specify one or more additional unclassified, publicly disclosed digital signature, public-key encryption, and key-establishment algorithms that are capable of protecting sensitive government information well into the foreseeable future, including after the advent of quantum computers.

So it appears that they want both key establishment algorithms (what you refer to as "public key distribution method") as well as public key encryption algorithms (and digital signature algorithms too).


how to calculate non linearity of AES S-box?

The non-linearity of an s-box is related to its linear approximation table.

For an $n$-bit input x $m$-bit ouput s-box the LA table is a $2^n$ x $2^m$ table. In the case of AES this is a 256x256 table. The entries of this table represent the difference between how many matches are found and how many are expected for a linear expression of the s-box boolean functions given an input/output mask pair. The expected value is half of all combinations match, which would be a value of 0. A value that differs from 0 means that combination is more likely to be either a 0 or a 1, resulting in a bias.

The linearity of an $n$ x $n$ s-box $S$ such as AES is the maximum distance from 0 in the LA table for input and output masks not equal to 0 (nonzero linear combination), which is 65025 out of 65536 entries for an 8x8 s-box. For AES the maximum value is +128 (256 matches) for a 0 mask, and +/-16 (112 or 144 matches) for a non 0 mask, therefore $lin(S)$ = 16.

For an $n$ x $n$ s-box $S$ such as AES, the non-linearity is $2^{n-1} - lin(S)$, which for AES is 112. All 8x8 s-boxes created using Galois Field inversion plus an Affine Transform have the same non-linearity, as the Affine Transform does not change the linear or differential properties. In practice, the LAT is calculated much faster than testing linear expressions per mask 1 at a time by using something called a Walsh Hadamard Transform.

Propagation is related to avalanche. If a specific bit changes to the s-box input, then of the $m$ output bits, they should change with probability of exactly $1/2$ for all inputs and all changed bits. If an s-box meets this, it meets the 1st order Strict Avalanche Criterion (SAC). In reality, very rarely (never) does this happen, so we want it to happen with probability of $1/2$ or higher, with the probability being as close to $1/2$ as possible, and the combined difference in probabilities being as small as possible (Distance to SAC (DSAC)). Functions that do meet SAC are generally not suited for cryptographic use, as they do not meet other required properties, such as to resist differential analysis.

There are 8 input bits in the AES s-box, there are 8 1-bit masks for 256 inputs, 8 output bits, resulting in 2048 8-bit values being tested, and 64 compared values of s-box output bits to 1-bit masks. AES meets probability $1/2$ or higher for $43/64$ bitmask/outbit combinations, with a min difference of 12 bits for those that do not, and a max difference of 16 bits for those that do. DSAC is 432 bits.

Higher orders of SAC use larger input masks. For 2 or 6-bit masks there are 28 combinations, for 3 or 5-bit masks there are 56 combinations, for 4-bit masks there are 70 combinations, and for 7-bit masks there are 8 combinations. The $k$-th order SAC is met if for a $k$-bit mask, the output bits change with probability of exactly $1/2$. For 2nd order SAC, AES meets probability $1/2$ or higher for $127/224$ bitmask/outbit combinations, with a min difference of 16 bits for those that do not, and a max difference of 16 bits for those that do. 2nd order DSAC is 1664 bits.

Propagation extends to ALL combinations of input bit masks of $1$ to $n-1$ bits. An s-box is said to meet $k$-th order Propagation Criterion if SAC is met for all orders {$1 .. k$}. 3rd order PC would mean 1st 2nd and 3rd order SAC are met. Maximum order PC means all orders of SAC are met. Once again, this is not likely to occur, so we try to target SAC orders with the probabilities closest to half, and with the smallest difference from SAC. Unlike linearity, the affine transform of AES has dramatic changes on SAC test results, although there are groups of AES-like s-boxes with different affine transformations that have the same results. These groups are called Affine Equivalence Classes, with each group having identical results in a variety of other tests as well.


How can I get the binary form of AES's MDS matrix in MixColumns tranformation?

Concretely, given an element $x \in$ GF($2^8$), to multiply it by 2, we simply do a left shift and xor with 0b100011011 if the result of the shift gets above 0b11111111 (255). To multiply by 3, we multiply by 2 and add the input.

Those two multiplications can be described with 8x8 binary matrices. The easiest way to find the matrices is to think how those operations would be implemented in hardware. Well, there is an efficient way to do it. Given a 8 bit inputs, $y_0 y_1 y_2 y_3 y_4 y_5 y_6 y_7$, first store $y_0$, do a left shift, and xor the result with (0b00011011 $\cdot \ y_0$). And the multiplication by 3 is simply a multiplication by two xored with the input.

Those multiplications by 2 and 3 are described by the following binary matrices :

$M_{mul2}$:

\begin{bmatrix}
     0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
     0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
     0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\
     1 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
     1 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\
     0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
     1 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
     1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
\end{bmatrix}

$M_{mul3}$ (which is $M_{mul2} \oplus M_{identity}$):

\begin{bmatrix}
     1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
     0 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\
     0 & 0 & 1 & 1 & 0 & 0 & 0 & 0\\
     1 & 0 & 0 & 1 & 1 & 0 & 0 & 0\\
     1 & 0 & 0 & 0 & 1 & 1 & 0 & 0\\
     0 & 0 & 0 & 0 & 0 & 1 & 1 & 0\\
     1 & 0 & 0 & 0 & 0 & 0 & 1 & 1\\
     1 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
\end{bmatrix}

Actually, from $M_{mul2}$ and $M_{identity}$ you can construct all the matrices of for the multiplication in the AES field by combining them with a double and add algorithm.

From this, you can construct the 32x32 binary matrice of the the MixColumns operation (here 1 is $M_{indentity}$) :

\begin{bmatrix}
        M_{mul2} & M_{mul3} & 1 & 1\\
        1 & M_{mul2} & M_{mul3} & 1\\
        1 & 1 & M_{mul2} & M_{mul3}\\
        M_{mul3} & 1 & 1 & M_{mul2}\\
\end{bmatrix}

and you can deduce the rest (as well as how to do the same for decryption).


Is this number used for factoring challenge only? Lets say one day a VERY VERY lucky guy just GUESS the factor P and Q correctly will there be any security issue in the world. Is anyone using this particular RSA 2048 for anything?

I don't believe so.  On occasion, the need for a composite of unknown (to anybody) factorization comes up; someone might be using it for that.  Such numbers are harder to generate than you might think;  if you just select a random 2048 value, find that it is composite, and run ECM on it a bunch, well, you won't know whether running ECM a bit longer would find the factorization.  Using one of the RSA challenge numbers would make sense in that case, but again, I don't know of anyone who's actually doing it.

On the other hand,

  Cracking this one by luck doesnt mean much right?

While there isn't a great deal of significance to this specific number, if someone did manage to factor it, it would certain raise the issue whether other 2048 bit numbers were hard to factor (which, incidentally, is precisely why RSA generated their challenge numbers in the first place)


What is the difference between different corona tracing protocols?

I'm not aware of websites providing a detailed comparison. Note, in particular, that DP-3T is not one, but three different proposals, and the Google-Apple system is an API specifying structural requirements for a contact tracing app, rather than a full-fledged application.

However, the DP-3T white paper is fairly detailed and explains in a very readable way how each of the three proposals work. It can be found here :https://github.com/DP-3T/documents/blob/master/DP3T%20White%20Paper.pdf.

As for the main differences between DP-3T and Apple-Google: DP-3T already provides an in-depth comparison between their three proposals in the white paper. Out of the three, the hybrid design is very close in spirit to the Apple Google proposal. To my knowledge, there are essentially two main differences between the Apple-Google proposal and DP-3T's hybrid design:

Both require to upload and publicly reveal session keys, from which several ephemeral IDs are derived, corresponding to some fixed time-period. However, the hybrid design allows a variable duration for the session key, and recommends 2 to 4 hours, while the Apple-Google recommends a 24 hours window. To explain why this matters:
1) the smaller the window, the larger the amount of material each user must download on a daily basis (numbers are given on the white paper and depend on the number of daily new cases).
2) however, a user is traceable for the time of the window, in the following sense: if two users have been in contact with the same user with the same time period, they both know the same session key from which the ephemeral IDs broadcasted during this period have been generated, hence they both know that they have been in contact with the same infected user. Of course, the smaller the time window, the less of a real concern this is. Hence, the choice of the time window is a tradeoff between efficiency and traceability.
DP-3T allows to redact your upload. This means that it gives you the opportunity, when you are infected, to not upload some of your session keys. This is useful for example if you've been on a one-to-one job interview for two hours: you might want to not upload the session key corresponding to those two hours, since the interviewer might have turned on his phone during this period alone and therefore learn whether you are infected, breaking anonymity. The Apple-Google app does not allow for this.

Otherwise, the exact choice of cryptographic primitives might differ very slightly for generating the ephemeral ideas (and hashing, for the variants that involve hashing), but honestly it does not matter, all use standard and well-established cryptographic primitives in a correct way.