What kind of operations are involved in NTRU?

Almost all lattice-based schemes that have somewhat practical performance use lattices from a subset of all lattices. Those lattices have additional structure and can be described using polynomials. The big advantage of doing this is that on the one hand the size of a description of the lattice is much smaller than for arbitrary lattices and on the other hand that one can use the fast Fourier transform (FFT) to do multiplication. If you want to learn more about this google for Ideal lattices or "the Ring setting" / Ring-LWE.

A different point one should note is that these advances in terms of performance are caused by additional structure that these lattices provide. Currently, we do not know any attacks that can exploit this additional structure to actually break the schemes (at least for the classes of lattices proposed). However, this is a topic of ongoing research and it is already known that for some spacial cases (if one selects these subsets in a bad way) schemes get insecure (see e.g. https://eprint.iacr.org/2015/176.pdf).


Proofs of collision resistance by reduction

When you try to reduce the security of one primitive (H') to the security of another primitive (H), you assume that there exists an adversary that could break H'. Then you show that existence of said adversary implies an adversary against H by describing an algorithm (the reduction) that uses the adversary to break H.

as a very simple example, consider the hash function $H$ and the hash function $H'(x) = H (x \oplus 1^{|x|})$ (with $\oplus$ being XOR and $1^{n}$ denoting the string of $n$ ones).

Now assume there exists an adversary $\mathcal{A}$ against the collision resistance of $H'$, i.e. there exists a ppt algorithm $\mathcal{A}$ that on input $s$ (and potentially a security parameter) will output $x$, $x'$ such that $H'(x)=H'(x')$ (with non-negligible probability).

Now your reduction needs to transform such a collision into a collision for $H$. If you look at how $H'$ is constructed, you can easily see that this can be done by computing $y = x\oplus 1^{|x|}$ and $y' = x'\oplus 1^{|x|}$ and outputting $y,y'$.

So your reduction is the algorithm that runs $\mathcal{A}$, flips all the bits in $\mathcal{A}$'s output and returns it. You can easily verify, that this reduction is successful whenever $\mathcal{A}$ is successful. As $H$ is collision resistant, the probability that $\mathcal{A}$ is successful must therefore be negligible and thus $H'$ is collision resistant.

So the problem you need to solve for your case is basically the question "How can I turn a collision of $H'$ into a collision of $H$?" When you think a moment about the way $H'$ is constructed, I am sure you will see an obvious way to do that.


To answer this, let's look at what the elements of $\mathbb{F}_{2^4}$ are: polynomials with coefficients in $\mathbb{F}_2$ that are reduced modulo $f(x)=x^4+x+1$. This reduction means that any power of $x$ greater than or equal to $x^4$ can be rewritten as a sum of smaller powers: in particular, $x^4=x+1$, and higher powers we can factor this $x^4$ out first. Using this, our elements are of the form $a_3x^3+a_2x^2+a_1x+a_0$, where each $a_j$ is either $0$ or $1$. Now, if we take an element of our field, say $g=0x^3+0x^2+1x+0=x$, we can compute powers of $g$ by repeated multiplication:

$g^0=1$
$g^1=x$
$g^2=x^2$ and so on.

When we take higher powers, this starts getting interesting. For $g^4=x^4$, we can reduce our element mod $f(x)$, and we get $g^4=x+1$. We can continue from here and get $g^5=g\cdot g^4=x\cdot(x+1)=x^2+x$. At $g^7$, we have $x^4+x^3$,
which we once again reduce and get $x^3+x+1$; $g^8=x^4+x^2+x$ which reduces to $x^2+1$.

Your question asks how we can compute powers of a generator $g=(0010)$, so let's examine what the notation $(0010)$ means in this case. As mentioned above, our elements are of the form $a_3x^3+a_2x^2+a_1x+a_0$. We can identify this polynomial with its list of coefficients, $(a_3a_2a_1a_0)$, so that
$1=(0001)$, $x=(0010)$, $x+1=(0011)$, and so forth. In your particular example, you have $g=(0010)$, which is just $x$. Then $g^2=x^2$ like before, which converts to the list $(0100)$. So to calculate these, what we do is convert to polynomial form, do the polynomial arithmetic described above, and convert back to a list of coefficients.


Shamir's Simple Sharing Scheme - preventing partial recovery of data

With SSS you are sharing field elements, so if the secret to be shared is larger than one field element, you are going to have to break up the secret somehow and share the parts. I am not aware of any standard method that allows you to make the sharings dependent on one another. Probably the best way is to encrypt the secret with a key and then share the key (using Shamir) and the encrypted secret (e.g using an appropriate erasure code) and store the share/fragment parts at different locations.

Note that this is not a problem of SSS. In SSS if a share is slightly corrupted it cannot be used in reconstruction.

You could also pick a field large enough for your secret.


Can post-quantum algorithms be run on commercial devices?

Post-quantum cryptography addresses the problem of developing public-schemes whose underlying assumptions are (believed to be) quantum resilient, i.e., the assumptions hold even in the presence of quantum computers.

There are many proposals for the underlying assumption and this leads to several branches like lattice-based cryptography, multivariate cryptography, code-based cryptography, hash-based cryptography or isogeny-based cryptography, among others.
The cool thing about these assumptions and techniques is that they can be implemented in classical computers.
In fact, many of these are already implemented and there is a competition driven by NIST to standardize some of these.

So, yes, these primitives are usable nowadays. Maybe these companies use a scheme of this nature, that may be the case.


How to know which key was used for an AES encryption?

I agree with your solution. Log that stores info about who and when is active with a particular role. You could use ID or name, but password hash seems ideal, to see when user changed the password, to not to show him his old data that he will try to decode with a new password. SHA3 is considered secure. If user makes a password and then sends SHA3(password) - there is no way for you to get the password out without brute force.
Could use SHA3(company name + password) to avoid easy guessing of known password hashes from the table. If someone gets the table, makes pre-calculated table with values like sha(12345) and scans the whole database, he is likely to find some matches.
Could also use SHA3(username + password), to avoid search for dublicates if the whole database is leaked or to show that even you cant search for dublicates. In addition to the previous bonus.
Could go further and use SHA3(your own secret + SHA3(username + password) to protect from all sides, leaked database and your own actions against the users. That is, user sends SHA3(username+password), but on your server you make SHA3(your secret+what user has sent you), and only that becomes public and is written in the database. One more way to make it better is a long generation time on the user side, like 100 or 100k steps of SHA3. But this is questionable for weak devices. Reason for this is mainly to prevent you to quickly crack users passwords with a dictionary, since you know how their response is calculated and what is there. One step further is to use algorithms that are hard to speed up on asics or GPU. https://en.m.wikipedia.org/wiki/Argon2
TLDR: use SHA3(your secret + 1000 chained steps of SHA3(username+password)), OR SHA3(your secret + argon2(SHA3(username + password)). Check if mobile device can handle it under 1 second.


Usage difference between x86 RDRAND and RDSEED

The processors come, at a first approximation, with three components:

A hardware noise source;
A pseudorandom generator that's periodically seeded from that noise source, whose output is available through the RDRAND instruction;
A true random generator that's driven off the noise source, whose output is available through the RDSEED instruction.

Intel's longer documentation has some explanations and a number of useful diagrams, which in turn refer to NIST's documents on random bit generators (SP800-90A, B and C).  But if I were to summarize the security goals of these two instructions, I think they are this:

No bit of the output of RDSEED should be predictable to a computationally unlimited attacker who observes any other output bits at any other time.
No bit of the output of RDRAND should be predictable to a computationally limited attacker who observes any other output bits at any other time.

But some such bits might be predictable to a computationally unlimited attacker under some circumstances.

In practical pseudorandom generators, even ones that reseed themselves periodically from fresh entropy input, it's generally the case that output bits are predictable from nearby bits, given enough computational effort.  For example, Intel's document tells us that their implementation of RDRAND uses NIST's CTR_DRBG algorithm.  This algorithm uses a block cipher in CTR mode to produce blocks of output data in caller-requested sizes, and the generator is only reseeded between output blocks.  So given a sufficient fragment of such a block, a brute force key recovery attack can predict the rest of the block with a better than chance success rate.

The document also tells us that both instructions use an "AES-CBC-MAC Based Conditioner" to process the output of the hardware entropy source.  This concept is explained in NIST SP800-90B (second draft) (p. 5):

  The optional conditioning component is a deterministic function responsible for reducing bias and/or increasing the entropy rate of the resulting output bits (if necessary to obtain a target value).

Basically, AES is here being used in a mode that, given true random but biased inputs, produces less biased, true random outputs.

Intel's document doesn't go at length about the "ENRNG" ("Enhanced Nondeterministc Random Number Generator," Intel's own term) used by RDSEED, but they refer us to NIST SP800-90B and SP800-90C.  Looking at the latter in particular suggests that this "ENRNG" might also use AES, but again in a mode that maps true random inputs to true random outputs.  There doesn't seem to be enough information to tell exactly what's going on here, but reading between the lines I'm guessing it's one of the NRGB ("Nondeterministic Random Bit Generator") constructions from SP800-90C, section 9 (pp. 32ff), which combine the true random output with that of a pseudorandom generator in an entropy-preserving fashion, as a practical safety mechanism:

  The advantages of using these NRBGs include the following:

  If the underlying DRBG mechanism in the NRBG has been instantiated securely, and the entropy source fails in an undetected manner, the NRBG will continue to provide random outputs, but at the security strength of the DRBG instantiation (the “fall-back” security strength), rather than providing outputs with full entropy.
  Small deviations in the behavior of the entropy source in an NRBG will be masked by the DRBG output.


Does a padding oracle have the encryption key? Where in real life do I see such an oracle?

There are many examples of real padding-oracle attacks in practice. SSL/TLS is arguably the most famous example. However, they appear everywhere. In a paper by Practical Padding Oracle Attacks by Rizzo and Duong they find a number of interesting examples. But, they are really all over the place.


Why Might XOR's Lead to Hash Functions Lacking 2nd Pre-image Resistance?

Well, if you construct what you described you basically create a function $f: \{0,1\}^{2m} \rightarrow \{0,1\}^m$.

As you correctly pointed out these two strings give the same when xor'ed. So the messages $10101111$ and $00000101$ will result in the same xor and hence will get mapped to the same hash, resulting in a second preimage as you found two $x,x'$ with $x\neq x' \wedge h(x)=h(x')$.

Now let's see what happens if $x$ is fixed:

Assuming you're given a value $x \in \{0,1\}^{2m}$ for which you want to to construct $x'\in\{0,1\}^{2m}$ with $x \neq x' \wedge h(x) = h(x')$.
Now observe that $x_1 \oplus x_2 = x_1' \oplus x_2'$ (with $x_1, x_2$ being the first and second half of $x$) will give the same hash $h(x_1 \oplus x_2)=h(x_1'\oplus x_2')$.
Now for a given $x=x_1||x_2$ one can easily construct $x'=x_1'||x_2'$ by using the equation $x_1 \oplus x_2 \oplus x_1' = x_2'$ so one can arbitrarily choose half of the second preimage and can then compute the other half. As $x_1' \in \{0,1\}^m$ this yields $2^m$ second pre-images for any given $x$.


Consider the use of double encryption applied to the AES algorithm with two 128-bit keys

Double encryption applied to the AES-128 algorithm and two random keys is theoretically breakable from 3 plaintext/ciphertext pairs by the generic Meet-in-the-Middle attack with 2128 encryptions for building a dictionary, and an expected 2127 attempts each requiring a about one decryption and two encryptions (the later is for checking an average of one candidate key pair). This totals to an expected 5⋅2127 AES-128 operations. That's so large as to be currently impossible: the realm of feasibility nowadays stops somewhere a 275 to 2100, with the later acknowledged good to 2020 by many authorities. Thus we have a margin like a thousand millions, which I guess is fine for a good two decades, save for fairies or imminent breakthrough in quantum computers making them useful for such tasks.

The amount of memory required for the schoolbook MitM attack is 2128 words each 128-bit, that is 2135 bits. Nowadays, a silicon wafer is seldom less than 80µm 50µm thick (these are used in Smart Cards, and obtained by milling normal wafers rather than by using ultra-thin wafers), a DRAM cell occupies an area of at least 4F2 with feature size F=10nm, thus we are talking 0.9⋅1021m3 of silicon; that's 80% of the volume of earth, which contains only 15% silicon. Quick, make these wafers even thinner or (more realistically) start making 3D silicon that is not stacked wafers!

Computing that silly amount of RAM is pointless, because there is a well-known (but seldom taught) refinement of MitM that requires a feasible amount RAM, and only slightly more computation than the generic MitM. See Paul C. van Oorschot and Michael J. Wiener: Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, 1999).

Interestingly, it is not known any generic technique that uses moderate amount of RAM and breaks two-key triple encryption of some b-bit block cipher with cost commensurate to 2b or even 23 b /2 encryptions.


Reversed One-Time-Password - generating secret server side

No, that can't work. Reasons:

There would still be the need to compare secret out of fn' against some reference in order to determine if it is correct, hence something confidential in the server (a comment has clarified this is not an issue in the application)
One Time Passwords are short and have little entropy, secrets are longer/have more entropy, and fn' is thus impossible by an information-theoretic argument.
The time is not always the same on the client and server. That issue also occurs for normal OTP, and has various workarounds (trying variations of time, or/and replacing time with an incremental counter which additionally saves on timekeeping power consumption on the client's OTP device).
[Addition] If fn' was public, then knowledge of one OTP and time would be enough to reconstruct secret, allowing to forge other OTPs (assuming fn is public or OTPs are short). That goes against a basic requirement in OTP authentication.


Which hash is used when providing signature algorithm ED25519 or ED448?

Hash algorithms:

Ed25519 uses SHA-512 (As referenced on wikipedia or on bearssl.org)
Ed448 uses SHAKE-256$^1$ (As referenced on bearssl.org)

$^1$ SHAKE-256 is a SHA-3 algorithm, a subgroup of the "Keccak" family.


Why does a padding block exist for ECB and CBC modes?

In ECB and CBC mode, the size of cipher text is more than the plain-text size by one padding block.

Block ciphers can only permute plaintext blocks and produce the permuted output ciphertext blocks. As such, modes of operation are responsible to make sure that the messages in the target messages space can be encrypted and decrypted given this restriction.

Now for a generic cipher you would expect to be able to encrypt / decrypt any message or any size. ECB and CBC mode do not provide this functionality by themselves. They need to be paired with a deterministic padding mode such as PKCS#7 compatible padding to operate on messages of any size.

Such deterministic modes must at least add a single bit of padding as otherwise the padding cannot be distinguished from the last bit of the message. Therefore such deterministic padding modes add one bit to N bits of padding, where N is the block size.

For these deterministic modes a full "padding" block is added if the message is already a multiple of the block size. Otherwise the last block contains a mixture of the plaintext message and padding.

If a fully generic cipher is not required you can use many different methods:

just requiring that the message size is a multiple of the block size (the key size of symmetric keys is often a multiple of the block size, so this often works for key wrapping);
nondeterministic padding methods such as zero padding (where the message should commonly not end with zero bits, or contain the message size internally);
ciphertext stealing, which poses constraints on the minimum message size / IV.

Notes:

many implementations are lazy and allocate a buffer size of the message size + 1 block for the ciphertext, this is however a waste of space.
AES-192 keys are not a multiple of the block size, which makes key wrapping more awkward.
deterministic modes require at least one padding bit, but usually implementations only handle bytes, so the padding would consist of 1..N/8 bytes.
Most other modes (CTR, GCM, OFB, CFB) are streaming modes and do not require padding to be able to encrypt messages of any size.


Trapdoors of Lattices: SampleD and SamplePre

No, they aren't the same. One of them maps 4 values to a single value, the other maps 2 values to a single value.

But yes, both functions have some similarities. Both compute the inverse of a known function witch can be computed only because a trapdoor is given (t in SamplePre and R in SampleD). We can use SampleD to create different SamplePre functions changing the parameters creating this way different trapdoor schemes.


You don't normally encrypt anything with just AES.  AES is a block cipher, and needs to be used with an appropriate mode of operation in order to securely encrypt general data.

In general terms, there are two kinds of modes of operation: traditional ones, such as CBC, CFB, OFB and CTR, which only protect the data against passive attacks by eavesdropping adversaries, and authenticated modes which also protect the data against active tampering.  While a traditional mode of operation may be sufficient for your particular needs, my advice would be to always use an authenticated mode such as AES-SIV if at all possible.  It's safer, and has no real down sides.

In any case, as long as you use AES with a secure mode of operation, with a random and/or unique IV/nonce as required by the mode, and respecting any other relevant constraints such as the maximum number of plaintexts encrypted with a single AES key (e.g. up to $2^{48}$ plaintexts for AES-SIV), and take care to keep the AES key secret, then you're safe from any known-plaintext (or, for authenticated modes, even chosen-plaintext) attacks.  For details, consult the definition and any relevant standards documents for your chosen mode of operation (such as RFC 5297 for AES-SIV).

Ps. Many lists of block cipher modes of operation, such as the Wikipedia page I linked to above, also include "ECB mode".  This mode exists to provide direct access to the underlying block cipher, and generally should not be used except to implement other modes of operation (or MACs or other similar block cipher based cryptographic algorithms).  In particular, it is not generally secure against known-plaintext attacks.

In your particular use case, where all the messages to be encrypted consist of small numbers, one can define various custom schemes that can provide known-plaintext and even chosen-plaintext attack resistance without using a conventional mode of operation (and thus possibly avoiding the slight storage overhead they require).

For example, you could encode your numbers as 64-bit integers, combine each integer with a unique 32-bit nonce value (ideally, a unique ID for the database row the number belongs to) and a fixed 32-bit check string (e.g. all zeros), and encrypt the resulting 128-bit block with the raw AES block cipher (i.e. "ECB mode").  This would produce a 128-bit ciphertext which is guaranteed to be unique (as long as all your nonces are distinct), which is tied to the database row it belongs to (via the nonce), so that moving an encrypted value from one row to another can always be detected as a forgery, and which is fairly resistant to forgery attacks even if the nonce cannot be checked (since a forged ciphertext has only a $1/2^{32}$ chance of decrypting to something with the correct check value).

However, while such a scheme should indeed be secure, I would generally not recommend it, since it isn't standardized (and thus requires extra implementation effort and extra security review) and lacks the flexibility of standard modes of operation.

In particular, using AES-SIV (with the row ID as the nonce) achieves a comparable security level, requires less than twice as much storage space (128 + $d$ bits, where $d$ is the size of the field being encrypted), and allows you to also link the ciphertext with arbitrary associated data (e.g. column name, timestamp, transaction ID and/or any other relevant unencrypted metadata) and to use the same method for encrypting other data of arbitrary type and size.  It's also a standard construction provided by many crypto libraries, and hopefully familiar to anyone reviewing your design.


Is there a digital time-stamping scheme that does not rely on a time-stamping authority?

If being decentralized with no trusted timestamping authority that could backdate things is a must, then the solution is Bitcoin's blockchain (or a similar cryptocurrency's blockchain). OpenTimestamps is a project for efficiently using it to timestamp files.

Most of the design for a possible basic decentralized cryptocurrency has been known since public key cryptography was invented (have a shared ledger of public keys with associated balances, and anyone can transfer currency from their balance to another by signing a transaction with their private key), but it had always been blocked by the double-spend problem (Alice could sign a transaction sending currency to Bob to buy a physical object, and then once it's in her possession, she could broadcast a second transaction with an older timestamp that sends that same currency to a 3rd address also controlled by herself instead, and try to convince everyone else that it came first and should be honored instead of the transaction to Bob). Essentially, without a decentralized timestamping service, there's no way for a decentralized cryptocurrency to get everyone to agree on the same order of transactions.

The double-spend problem was finally solved in 2009 by Bitcoin through its use of a proof-of-work blockchain. Each block contains a proof-of-work based on a hash of the rest of the block, the hash of the previous block, and a list of transactions. People ("miners") are incentivized to compute the blockchain proof-of-works by receiving newly minted bitcoins and bitcoin transaction fees. Each block contains a timestamp, and the proof-of-work difficulty automatically scales so that the proof-of-work (and therefore a new block) can be made every 10 minutes. Every Bitcoin node knows to use the longest blockchain. For an attacker to backdate a transaction N blocks into the past so that it would be before a conflicting transaction, they would have to calculate N proof-of-works, but the while they are computing these proof-of-works, the rest of the miners are on the network are still building the blockchain by creating more proof-of-works. The attacker would have to have more computing power than the entire rest of the miners on the network in order to race them and create a bigger blockchain.

Now to rewind a bit: to actually use this for timestamping files, then you would just want to encode a file (or merkle tree) hash into a transaction in the Bitcoin network. OpenTimestamps is a project for doing this efficiently. (There are other such projects, but OpenTimestamps is much more efficient than most and is made by a Bitcoin developer.) You might be wondering "why involve Bitcoin at all?" and want to extract out its blockchain, but that can't work as Bitcoin's blockchain only works because the miners have a cryptocurrency incentive to contribute, and a blockchain without a significant number of miners like Bitcoin's already has could be easily attacked.


Question about why RSA is hard to attack

There are a number of small mistakes in the question. Let's clean up that first.

$\gcd(e,n)=1$ is likely, but neither necessary nor sufficient for RSA to work; the right condition is $\gcd(e,p-1)=\gcd(e,q-1)=1$. Notice this implies $e$ odd for any non-trivial choice of $p$ and $q$.

Even in textbook RSA, the right equation is not $c\equiv m^e \bmod n$, but $c=m^e\bmod n$. The first can be understood as $c\equiv m^e \pmod n$, and only the second implies that $0\le c<n$. The distinction is important: $c'=m^e$ satisfies the first, but (for most $m$) not the second, and would make RSA both unsafe and (except for small $e$ like $e=3$) extremely impractical as an encryption method.

Although that is not directly relevant to the questions, RSA as practiced is PKCS#1. A number of things change. The most important is that $m$ is not the message, but rather a randomized and reversible function of the message. Also, it is used $p≠q$, $1<e<n$, and $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ where the question and the original RSA article uses $\phi(n)=(p-1)⋅(q-1)$, for determining the private exponent $d$ such that $e\cdot d\equiv1\pmod{\lambda(n)}$ and $1<d<n$.

Coming to the question about tactic 1:

An attacker Eve has the choice of means; she do not have to try a particular strategy, as in "in order to find $m$, we'd have to try all $k$'s in the natural numbers.."; she could try that strategy.

If she elected to follow the proposed strategy, try some $k$'s in the natural numbers and compute $m=(c+k\cdot n)^{1/e}$, she'd have a much better option than trying to guess if the resulting $m$ looks like a message; she can conclusively rule out a guess of $k$ when the resulting $m$ is not an integer, which occurs for the overwhelming majority of $k$. And also, she can decide if an integer $m$ in range $[0\dots n-1]$ is the right message by computing $m^e\bmod n$ and comparing that to $c$; they are equal if and only if she guessed the right $k$, and/or otherwise recovered $m$.

Tactic 1 is of course futile because they are too many $k$ to test.

Concerning tactic 2: the assertion is correct, for some loose use of "This is because"; exposing two methods to find $\phi(n)$ does not implies that they are the best ones, much less the only ones.

Notice that if an attacker Eve knew $\phi(n)=(p-1)\cdot(q-1)$, she's done: she can then compute an $f$ such that $f\cdot e\equiv 1\pmod{\phi(n)}$ and that let her decipher using that $m=c^f\bmod n$. Although her $f$ might not be the $d$ used by the legitimate key holder, which is any $d$ such that $d\equiv f\pmod{\lambda(n)}$, she does not care.

Attacking RSA encryption is believed hard when $n$ and $e$ have been properly chosen, and the message $m$ is a random integer in the set $[0\dots n-1]$, and all else that's known about $m$ is $c=m^e\bmod n$, because the best methods we have to solve that problem are of cost as high as factoring $n$, and the best general method known for that is GNFS, and the expected cost for that is prohibitive by definition of "$n$ has been properly chosen". This is circular, loose, and not a mathematical proof that RSA or factoring is hard. Neither is known with certainty. Notably, the definition of "$n$ has been properly chosen" has changed drastically since that original RSA article. That "RSA hard" implies "factoring hard" is obvious, but the converse is an open problem.


But how secure would that be ?

Not very; there's an obvious known-plaintext-attack that recovers the key settings with effort equivalent to about $2^{28}$ encryptions; that'd be less than a minute on a single CPU core (perhaps much less, depending on the speed of the cipher implementation).
Two obvious observations:

You count the initial positions of the rotors as 'key'; however you expose them in the ciphertext (and so the attacker would know them).  The only thing initially unknown to the attacker is the rotor selections (and the initial settings used to generate the IV; the attacker doesn't care about that)

There's an obvious meet-in-the-middle attack; with a known plaintext/ciphertext pair (with known IV settings), we can scan through all $47^5$ possible selections for the first five rotors, and encrypt the plaintext through the first half the cipher with those, coming up with $2^{47}$ possible intermediate values.  Then, we can scan through all $57^5$ possible selections for the last five rotors, and decrypt the ciphertext through the last half of the cipher, coming up with $2^{47}$ possible intermediate values.  Check the two lists for a common value - that'd be the rotor settings.

BTW: if you are really interested in this 'encryption with a reduced alphabet' problem (rather than just playing around with designing your own system), you might want to read up on Format Preserving Encryption...


How difficult is it to get a key using simple XOR

That "algorithm" is fine, as long as the random values cannot be guessed by an attacker. The scheme is known as (trivial) secret sharing.

XOR with completely random data is called a one time pad or OTP. The security of the algorithm therefore depends on the random number generator. Of course there are additional operational requirements to obtain system security (if somebody just distributes his share of the key ...).


In practical terms, you can take 32 bytes, and safely expand them into up to $2^{128}\cdot64$ bytes using ChaCha, which is more bytes than you can actually expand anything into even if you could enlist the help of all the queen's horses and all the queen's men even if they weren't busy putting Humpty together again.

Some practical PRGs are more limited.  For example, by the birthday paradox, the distinguishing advantage against AES-256 grows with $q^2\!/2^{128}$ where $q$ is the number of blocks of output, so it falls apart around $2^{64}$ blocks and you should really limit yourself to well below that many, say $2^{32}$ under a single key in order to keep the distinguishing advantage below $1/2^{64}$.  This is because AES is a permutation, and a permutation of 128-bit strings at that; in contrast, ChaCha is a function into 512-bit strings.


RSA Encryption problem for Discrete Math


Why are processes requiring (almost) as much work as brute force considered an "attack" on a hash function?

It's just a matter of terminology, which (as often in mathematics and related disciplines) may not match your intuitive interpretation of the words.

An attack is any algorithm that performs better than the "obvious" brute force algorithms. Cryptographic primitives are designed to admit no attack better than generic ones, so any proof that this goal is not met constitutes a break (but maybe not a complete break) to a theorist. For more practically-minded people, it demonstrates attack vectors and techniques which may be useful in constructing more efficient algorithms.
If an attack is effectively breaking the system for realistic key sizes, it is often referred to as a practical attack. (And people usually proudly put this term into their paper's titles if their attack performs this good.) For well-studied primitives, this luckily does not happen very often.
Some papers describe attacks against round-reduced variants of a cipher: this again serves as a demonstration of attack techniques and (just like any other kind of cryptanalysis) is an important step in cipher design, because it provides an estimate for the number of rounds the cipher should have. Papers should (and usually do) clearly point out that they're attacking non-standard variants.

Then of course, unfortunately some (if not many) people have a tendency to oversell their results — there's nothing you can do against that, but the above should help in filtering for the kind of attacks you're interested in.


Can a Feistel network have more than two halves, widening the block width?

There are designs called generalised unbalanced feistel networks which do exactly this.

See the paper by Schneier and Kelsey here. The CAST cipher, an AES competition entry was an early example.

The article on cryptowiki gives a brief summary here

Here is an example:


Is this correct or is just a matter of javax.crypto.Cipher implementation?

It is correct. You need to always add some amount of padding if you are to distinguish between different padding lengths. With PKCS5 padding the length of the padding is $b - |m| \mod b$, where $b$ is the block size. With $|m|$ a multiple of block size a whole block of padding is added.


Public Key Encryption, how do you handle not trusting the middle man?

With public/private key encryption you must trust the central authority correct?

Not quite.  The honest parties must have an authenticated (but not necessarily confidential) channel to obtain each other's public keys.  A central authority that both parties trust is one way of fulfilling that requirement, but is not the only one.  For example, public keys could instead be exchanged through a face-to-face meeting.

  What can you do if you don't want to trust the centeral authority? Are there any ways around that?

  for example in a chat app

Apps like Signal and WhatsApp provide two authentication methods:

Use the service itself as a "central authority" that provides you with your contacts' public keys.
Out-of-band contact verification through security codes, which users can compare independently to verify that the central authority is not cheating them.

From Signal's support page on this:

  Each Signal conversation has a unique safety number. The safety number gets stored the first time you exchange a private message with a new contact. You will be alerted if a conversation's safety number ever changes. This can happen if someone else is pretending to be them, or if they get a new phone and reinstall Signal.

  [...] The safety number on your phone should match those on your contact's phone. If the safety number is identical then you can be sure that you are communicating with the right person. If the safety number does not match, then make sure you and your contact are using updated versions of Signal, open a conversation with just that contact, and then try again.

WhatsApp has a similar feature as well:

  Each of your chats has its own security code used to verify that your calls and the messages you send to that chat are end-to-end encrypted.

  Note: The verification process is optional and is used only to confirm
  that the messages you send are end-to-end encrypted.

  This code can be found in the contact info screen, both as a QR code
  and a 60-digit number. These codes are unique to each chat and can be
  compared between people in each chat to verify that the messages you
  send to the chat are end-to-end encrypted. Security codes are just
  visible versions of the special key shared between you - and don't
  worry, it's not the actual key itself, that's always kept secret.

If this is something that concerns you at all, you should be at least on occasion   checking your conversations' security codes when you meet your contacts in person.  For such services not to be abused for mass surveillance, a small but significant percentage of users need to periodically exercise this kind of vigilance.


Upgrade password hash in an existing system: Pbkdf2( salt , OldSha1Hash )

Yes, mostly

But wait, isn't SHA-1 broken?

It is. SHA-1 has collisions found as of 2017. But this isn't important for our usage, since we only require that SHA-1 won't collide for our inputs. Difference is that with 2017 attack attacker knows plaintext and tries to find another plaintext that gives same hash, in our case attacker doesn't know anything (not even hash). And we can assume that SHA-1 won't collide for real-life passwords, since if this was case it would be very major breakage of SHA-1 (that would have been found earlier).

There is however one catch: SHA-1 will limit your security to 80bits, since it has 160bit output and birthday attack can "limit security" to half of output bits (in our case). This is in fact reason PKDBF1 was abandoned in favor of PKDBF2, but most passwords are far from 80bits in security.

Note: I didn't take any of other problems into account in my answer. Choice of PKDBF2 might be considered outdated by this point too. I personally would suggest Argon2 (but some would call it too new to be adopted). Also PKDBF2 doesn't have one input, as others noted, but I'll assume it's just overlook.


Multiply by 3 problem with MixColumns in AES

The issue is that the "XOR with 0x1b" step is performed when it must not.
That "XOR with 0x1b" should be performed after a LSL if and only if LSL dropped a 1 on the left (that is, if LSL started from a byte with bit 7 at 1).
Equivalently: LSL drops nothing, we "XOR with 0x11b" if the result of LSL has bit 8 set.
Yet another equivalent alternative: we convert the argument to a polynomial of degree at most 7 with binary coefficients, multiply that polynomial by $x$, and if the result has degree 8, we reduce it by adding the reduction polynomial $x^8+x^4+x^3+x+1$. Then we convert back to bits to get the result.
Minimally fixing the question's "Next" One (second row of the first matrix multiplication):
87 = No changes (Multiply by one)
6e = 01101110 => SHL = 11011100
46 = 01000110 => SHL = 10001100 => XOR with the Byte itself 10001100 XOR 01000110 = 11001010
a6 = No changes (Multiply by one)
10000111 XOR 11011100 XOR 11001010 XOR 10100110 = 00110111 = 0x37


What does "bits" mean in the context of hash functions?

That's referring to the size of the output, or message digest, of a hash function. MD5 outputs an 128-bit hash value. Or: there are $2^{128}$ possible outputs.

In Python:

>> md5("hello, world").hexdigest()
'e4d7f1b4ed2e42d15898f4b27b019da4'

You can see 32 hexadecimal (hex) digits that represent 16 bytes or 128 bits. Here's that value in binary; there are 128 $0$s and $1$s, or binary digits that represent bits:

  11100100110101111111000110110100111011010010111001000010110100010101100010011000111101001011001001111011000000011001110110100100

To calculate, just count them!

Likewise, for SHA-1, you have 160 bits, 20 bytes or 40 hex digits. There are $2^{160}$ possible outputs:

 >> sha1("hello, world").hexdigest()
 'b7e23ec29af22b0b4e41da31e868d57226121c84'

The output size of a hash is directly linked to the maximum security level that can be achieved. The security level is half of the bits if the birthday problem applies for example if the hash is over a string as above. It's the full amount if this isn't the case.

Note that both MD5 and SHA-1 are considered broken for most usage scenarios, so the above calculations do not apply to them anymore. The amount of security offered is much less than the output size would suggest.


My first thought was that it is perfectly binding.

It's not.

  $commit_B(C_{H1}) = commit_B(C_{H2})$

That's fine

  This would be a contradiction, because $commit_B$ is perfectly binding.

Actually, that's not a contradiction, because it's possible that $C_{H1} = C_{H2}$

After all, $H$ is not perfectly binding; what that means is that you can have two different messages with the same commitment (one would hope that it is hard to find both sets of the random coins that would yield the common commitment; but we're talking about existence, not computational complexity).  In fact, if $H$ is perfectly hiding, then any valid commitment could possibly correspond to any message (if there's a message that it could not reveal, then the receiver could deduce that message was not the committed one).

Hence, $commit_H(M_1) = commit_H(M_2)$ is perfectly possible, given the appropriate random coins.

And, so, when we open the larger scheme, the committer can (given unbounded computation) change his mind what he opens $H$, and so this is not perfectly binding.


Probability approximation of no collisions

For a hash function with a 128 bit output, n=128. Such a function has $2^{128}$ possible outputs.

For the birthday paradox you have 365 different outputs, i.e. $2^n = 365$ or $n = \log_2 {365} \approx 8.5$.

You'll also find alternative versions of this formula, which omit the 2^ part in the formula: $\frac{e^{-t(t-1)}}{2 \cdot N}$. In that case you'd use $N=365$ for the birthday paradox and $N=2^{128}$ for the 128 bit hash.

If $t$ is small compared to $N=2^n$, the formula can be approximated as:

$$1-\frac{t(t-1)}{2}\frac{1}{
N}=1-\frac{1+2+3+...+(t-1)}{N}=1-(\frac{1}{N}+\frac{2}{N}+\frac{3}{N}+...+\frac{t-1}{N})$$

Which is intuitive, since the first value has no chance of collision, the second can collide with 1 existing value with probability $\frac{1}{N}$, the third can collide with 2 existing values with probability $\frac{2}{N}$, etc.


Practical implications of the switching lemma and the counter mode security bound

Does this $q^2 2^{−l−1}$ just show that there is no attack that is better than this bound, or does it also give us an attack? And if so, what does that imply?

The switching lemma is tight up to constant factors. If you make $q$ queries, then you can indeed distinguish between a PRF and PRP with probability at least $0.632 q^2 2^{-l-1}$. Here the 0.632 is $1 - 1/e$. More specifically, this is the probability that you will see a repeated output by a PRF (and obviously a repeated output from a PRP is impossible).
You can indeed attack the IND-CPA security of PRP+CTR with this advantage.

Suppose you ask for $q$ identical blocks to be encrypted. Assuming the IV+counter never repeats, it is not hard to see that there will be no repeated ciphertext blocks under a PRP.

Suppose you ask for $q$ uniformly distributed blocks to be encrypted. Then the ciphertext blocks will be uniformly distributed and therefore display duplicates with the above probability.

  Is $q$ the amount of queries that is allowed by the oracle and thus, assuming no other leaks, the total amount of cypher calls by my system?

In this context, $q$ is the number of calls to the PRP that the attacker induces the honest party to make.


Why perfect secrecy can be ensured when a plain message and a cipher-text based on one-time pad are correlated?

Are M and C correlated?

No.

The distribution that the values the M and C may take on are independent of each other.  The condition probability distribution that M has is unchanged no matter what the observed C value is.

This is true whether you are using the statistical meaning of correlation, or whether you are looking more specifically at linear correlations.

Here's why the answer to the math stack exchange is "they might be correlated", while the corresponding answer here is "they aren't"; consider in the math stack exchange case that $X$ and $Z$ are independent variables that can take the values 0 and 1 with probability 0.5 each, and that $X=Y$, and that the addition is integer addition.  In this case, if $Y$ is 0, $X+Z$ can take on the values 0 and 1, while if $Y$ is 1, $X+Z$ can take on the values 1 and 2; hence the probability distribution of $Y$ and $X+Z$ are not independent.

This corner case can't happen with one time pad.


Initialization vector length insufficient in AES

CBC mode is a method of encrypting messages of arbitrary length; it can handle messages longer than 16 bytes, and it takes an fixed length IV (16 bytes in the case of AES) for each message.  So, if the question is "how does CBC work for messages longer than 16 bytes (even if the IV is only 16 bytes)", the obvious answer is "quite well, thank you".

The source of your question would appear to be "in the case I tried, the decryptor used a different IV than the encryptor; how could it decrypt properly after the first 16 bytes?"  The answer to that is, well, that's how CBC mode works.  On an IV mismatch, the first 16 bytes will be garbled, and the rest of the message will decrypt properly.  Actually, this isn't limited to only the IV; the ciphertext has a similar property; if you modify bytes 0-15 of the ciphertext, then bytes 0-15 and bytes 16-31 of the decrypted plaintext will change, but the rest of the decryption will be unaffected.  This happens because block N of decrypted plaintext is a function of blocks N and N-1 of the ciphertext (and no other part of the ciphertext); if N=0 (the very first block), the IV stands in for block -1 of the ciphertext.

Also, you are probably already aware of this, but I'll add it anyways: for CBC mode to work, both the encryptor and the decryptor need to use the same IV for a message.  Now, the most common method of achieving this is to have the encryptor select the IV randomly, and send the IV it used along with the encrypted message.  This works (and it's easy to show that giving the IV to an attacker doesn't help him), however, that's not the only possible method; both sides could be able to select IVs via a formula.  It turns out it is important that someone in the middle can't predict the IV's that we'll use before the message is sent (otherwise there are subtle attacks); but as long as we have that, deterministic IV generation is possible.

And, if you're looking at your experiments and are wondering "if the decryptor can decrypt after the first 16 bytes, why doesn't the encryptor just add a dummy 16 bytes, which the decryptor ignores", well, the surprising answer is that it works well.  In fact, that turns out to be equivalent to selecting a random IV, and sending it along with the message (in the 16 bytes immediately prior to the ciphertext).

My guess is that you're not really interested in digging into how CBC and AES work internally, and so I won't go into those details. If I am wrong, you can get started by looking at Description of CBC Mode; if you have further questions about that, well, this is a good forum for asking those questions.


Why should one model an entropy source in order to build a TRNG?

Why use a model?
The utility of a scientific model is the ability to make predictions. An example of a simple model is one describing the motion of projectiles based on Newton's laws of motion and gravity.
You could use two strategies on a battlefield to make a cannonball land where you want it to.
You could point the cannon in the general direction of a castle and fire. If the projectile flies over the target you try again, aiming lower. If it still overshoots the castle you aim a little lower again. (Or if it falls short aim a little higher.) You try and make adjustments until you get the result you want.
Alternatively you could determine the distance between you and the target, how much higher the target is than the cannon, the initial speed of the cannonball. You model the cannonball as a point mass. You ignore the effect of drag. (It might be fine depending on how dense the cannonball is, how thin the atmosphere, how far it needs to travel.) In such an environment, a consequence of Newton's laws is that the relative position of a projectile can be determined from its initial velocity. You use the numbers and formulas to determine where to aim. Not your eyes.
The first method does not use a formal model. It is not preferable because it will waste resources and because any mistakes will put you in danger. The second method (potentially) enables you to hit your target on the first try.
Science is full of models. You want to find one that is sufficiently accurate in order to have confidence that things will work out right. You want a simple enough model for it to be practical. The Newtonian cannonball model does not describe exactly how the real world works. It simplifies things while remaining useful. For some applications you need something more complex. All models are like that.

Example
If you want to build an RNG that uses radioactive decay as it's source of unpredictability, then first you model the process of decay using the half life model. It lets you treat the physical phenomenon as a clean mathematical abstraction.
Next we figure out how much of the material you have and what fraction of the decay events we can detect. Then we use our knowledge that the half life decay model can be described as a Poisson process to create a statistical model.
The model will tell use how likely we are to detect an event in any given time slice of a certain length. If the half life is long enough and we have enough material this probability should remain accurate for a long time.
Now we have a Bernoulli process. The samples are binary (detection or non-detection), independent, and will have effectively constant probabilities.
We can look at the probabilities of the two possible outcomes. From that we can easily determine the min entropy. That number can tell us how many samples we need to take to ensure we have sufficient entropy. (And therefore also a lower limit on how long we need to wait to generate a key.)
Multiply the number of samples you need by 2 or 2000 just be conservative and paranoid. Now you know how many samples to process through a cryptographic hash before you can use the output to generate a key.
We could have stopped once we knew we could model detection as a Poisson process and not calculate probabilities. Two non-overlapping time slices are statistically independent in a Poisson process model. We could use von-Neumann's debiasing algorithm for that reason without needing to know the detection probability because (assuming the hardware is working correctly) the kind of samples we have are independent and identically distributed.
But calculating the probability gives us the opportunity to test if things are working as intended. (Use a better model to build a safer HWRNG.) If the CPU sees detections far more frequently than expected, then maybe someone is using another radioactive source to try to bias our RNG. If we see too few detections or too many identical consecutive samples then maybe a circuit has been damaged.
Note: I'm confident that I don't know how every real world radioactivity-based HWRNGs work with 100% accuracy. There could be different designs with different design justifications. Physics is not something I plan on studying further. And I'm definitely not going to bother with reverse engineering proprietary things.

Other questions
Use a histogram?
No. Don't use a histogram. Use a probability mass function.
Creating a histogram requires sampling. A histogram can only be used to estimate probabilities. If you don't know what to look for then you definitely can't tell the difference between a working system and a broken one.
You also don't want to calibrate the system based only on empirical results. It's important to know how likely components are to fail, to know whether or not aging of components will render the calibration invalid.
Calibrating to lab conditions is dangerous because the characteristics of the entropy source you use might be different at different temperatures, in different environments, as the components age, when exposed to different strengths and frequencies of electromagnetic noise, on different power supplies.
It's a better idea to use a design based on knowledge of a physical process that will be robust enough to still be unpredictable (and predictably unpredictable) in the future under different conditions.
Theoretical necessity?
Theories for why you don't need theories? Maybe. I don't know how many theoretical researchers have an interest in that niche.
Results don't match theory?
You're model is wrong or your hardware is broken. If a device isn't working the way it's expected to and there are any safety implications if it's broken, then why not fix it or use a different device? If your model is wrong and your hardware is fine, then why not find a model that does explain things?
50% error?
I don't know what metric you're using. That sounds really high.


First, note that having a one-way function is far from enough to construct a public-key encryption scheme (a famous result of Impagliazzo and Rudich actually shows that it is impossible to construct public key schemes from one way functions only).

Second, cryptographic constructions which aim at being implemented at some point rely on the hardness of problems over finite sets in general (this is a vague statement, but quite intuitive). Over finite fields, finding roots of a univariate polynomial is easy.

However, a problem related to what you ask about is that of the difficulty of solving systems of equations of multivariate polynomials. This problem is hard (it is even NP-hard) and was used as the underlying cryptographic assumption for the construction of public key cryptosystems and signatures schemes. Unfortunately, no public key cryptosystem built on such assumption has survived cryptanalysis (to my knowledge); every attempt was proven insecure at some point (this is not true, however, for signature schemes).

Hence, even though it might be possible to construct public key cryptosystem based on problems related to finding roots of (multivariate) polynomials, this has proven to be at least a very hard task. See e.g. the Wikipedia article on Multivariate cryptography for more details on the topic.


Number of cryptographic operations required to perform a MitM for 4DES

In MitM for 2DES, in a tabulation phase we compute and keep $2^{56}$ 64-bit values and their associated key, then in a search phase we compute up to $2^{56}$ 64-bit values and search these in the table. There's a hit about once in $2^{64-56}=2^8=256$ searches, that is about $2^{56-8}=2^{48}$ hits, and all except one are false hits. We need to eliminate false hits with a few extra DES operations: typically two, testing an extra plaintext/ciphertext pair². Further, a fraction of the 64-bit values have been obtained $k>1$ times in the first phase, and when we hit one of these in the search¹, the number of DES operations required to eliminate the false hit is $1+k$. All these details increase the number of DES operations by less than 1% from the base $2^{57}$ (for full search, or $3\times2^{55}$ on average), and some expositions neglect that detail³.

But if we implemented MitM for 4DES by precomputing $2^{112}$ 64-bit values, each 64-bit value would be obtained an average of $2^{112-64}=2^{48}$ times, thus in the search phase we'd be swamped in false hits: rather than rare (once in 256 searches) that would be the norm, and eliminating a false hit would need an average of $1+2^{48}$ extra DES. This is an unreasonable amount of extra work.

A simple line of though to attack 4DES is to attack using normal MitM the block cipher 2BIG, where BIG is a block cipher with double the key size and block size of normal DES (that is 112-bit key and 128-bit block size) obtained by applying 2DES with the 112-bit key on each 64-bit half of a 128-bit block, requiring two DES operations. MitM will theoretically³ break 2BIG in about $2^{113}$ evaluations of BIG (for full search), thus about $2^{114}$ evaluations of DES.

¹ Assuming we kept all the corresponding keys in the tabulation phase, which is required if we want to be sure the find a solution.

² When we get a confirmation with that second plaintext/ciphertext pair, most often we have hit the right pair of 56-bit key halves. But probability of the contrary remains about $2^{-16}$, so we want an extra check using a third plaintext/ciphertext pair, at a cost 2 DES operations.

³ There's an elephant in the room: even against 2DES, much more against 4DES, basic MiTM requires so much RAM and RAM accesses that the cost of DES operations is comparably negligible.


Is SSH public key authentication weakened by 'none' cipher?

It is critical to combine both the key exchange and the secure channel, otherwise someone can mount a man-in-the-middle attack.

The way we prevent a man-in-the-middle attack is to do a key exchange, to exchange a session key that both endpoints know but no one else (including the man-in-the-middle) can know, and then authenticate both endpoints.  You seem to suggest that we remove the encryption, remove the secure channel, don't bother negotiating a session key.  If we did that, then the protocol would become vulnerable to man-in-the-middle attacks (active attacks), because nothing binds the signature/authentication phase to the rest of the stuff sent over the SSH channel.


In asymmetric crypto including RSA, we ALWAYS encrypt with the public key, and decrypt with the private key (NEVER the other way around). In the question, what's wanted is to sign with the private key, not encrypt.

And that's enough to solve the whole problem, since RSA signature schemes exposed in BouncyCastle or the Java crypto API allow to sign data of arbitrary length.

Addition: The objective of encryption in modern cryptography is to prevent an adversary from gaining information about what's encrypted (with the exception of its length). When a piece of data is transformed into a cryptogram that can be returned to the original data using a public key, in such a way that only the holder of the private key could have prepared the cryptogram, that's not encryption; that's signature with message recovery.

In that name, signature covers that holding the private key is necessary to prepare the cryptogram, and that the private key allows to check the cryptogram. Message recovery covers that the cryptogram can be transformed back to the original message.

RSA signature schemes with message recovery (such as those in ISO/IEC 9796-2) have an advantage over those with appendix (such as those in PKCS#1): the size overhead for signing is smaller (slightly over a hash size, rather than a modulus size). For example, when using RSA-2048 and SHA-256, ISO/IEC 9796-2 embeds a 222-byte message into a 256-byte cryptogram, when PKCS#1 requires a 478-byte cryptogram (222 bytes for the message in clear, and 256 bytes for its signature).

As I understand it, the question attempts to make an hybrid signature scheme with message recovery, by mixing textbook RSA (used for signature with message recovery of a symmetric key), and AES/GCM (for integrity check and recovery of the bulk of the message). This is insecure to the utmost: an adversary (assumed to hold the public key, by definition of that) can determine the symmetric key from the RSA part, and then alter the message itself to whatever is desired.

Again, the problem at hand is finely solved with standard RSA signature. Appropriate schemes with appendix are directly available from the BouncyCastle or the Java crypto API. Message recovery could be used if reducing the size of the cryptogram by a few hundred bytes matters. While ECDSA signature (also readily available) would also reduce the signature overhead (to only about double that of RSA with message recovery), and significantly speed-up signature, it has the disadvantage that checking a cryptogram is significantly slower than with RSA.


Message authentication codes construction

The short answer is:  They prepend bits in that way because the scheme is not secure without them.  While they might not explain it in English, their proof makes it clear where they use it.

Let us construct an attack against the scheme that does not prepend a bit to the blocks.  The same idea will work against a version of the scheme that prepends the same bit to every block.  In this version of the scheme, a tag for a single-block message $M\in\{0,1\}^{32}$ is $(r,z)$, where $$z = F_a(r)\oplus F_a(\langle1\rangle\| M).$$
Our attack will obtain about $2^{32}$ tags for an arbitrary single-block message $M$, stopping
if it ever gets a tag $(r,z)$ such that the upper $32$ bits of $r$ are equal to
$\langle1\rangle\in\{0,1\}^{32}$ and lower $32$ bits are not equal to $M$.  When it finds such a tag $(r,z)$, let $s\neq M$ denote
the lower $32$ bits of that $r$.  The adversary outputs a forgery on the message $M' = s$ with tag $(r',z')$ defined by
$$r' = \langle 1\rangle\| M \quad \text{ and } \quad z' =z$$  This tag will verify with message $M'$ because
$$z' = z=  F_a(r)\oplus F_a(\langle 1 \rangle\|M)= F_a(r')\oplus F_z(\langle 1 \rangle\| M'),$$
where the second equality uses the fact that our $r$ is equal to $\langle 1\rangle\| s = \langle 1\rangle\| M'$ (it switches the order of the arguments to $\oplus$).  Moreover, our adversary never queries the message $M'$ and one can verify that it will get the needed $r$ with good probability in about $2^{32}$ tries, so it will win the security game.

The intuition is that prepending the bits prevents this sort of thing from happening.  Specifically, this adversary found a way to force the verification algorithm to treat a previously used $r$ as a message, which can't happen with their domain separation strategy.


I2OSP and OS2IP mean Integer to Octet Stream Primitive and Octet Stream to Integer Primitive. There is an often used play on words here: "two" (2) has almost the same pronunciation as "to". The word "octet" simply means 8-bit "byte" and that "stream" can be replaced with "array". So these are conversion functions between integers to byte arrays.

The I2OSP function simply represents an integer in a statically sized byte array. For this it requires two inputs: the integer itself and the required size of the byte array. If the integer "doesn't fit" then an error is produced.

The integer is encoded as an unsigned big endian (network order) number, prefixing leading zero bits and bytes at the left hand side until the size is reached.

So lets take a look at some examples with output size of 2 octets with the integer (in decimals) on the left and octets  / bytes at the right (in hexadecimals, separated by colons):

   -1  ->  error
    0  ->  00:00
    1  ->  00:01
  255  ->  00:FF
  256  ->  01:00
65535  ->  FF:FF
65536  ->  error

So any integer will be represented with the same number of bytes, and each number will have a unique (or canonical) representation.

This function is used to make sure that signatures and encrypted values for a specific key size will also be represented in the same way, using the same number of bytes. For instance in RSA - for which these functions are defined - the size of the signature and ciphertext is always the same as the key size (or: modulus size) in bytes.

The size of the array used for RSA is the minimum size of the modulus encoded using I2OSP. The size of the modulus in bits is the same as the key size. So signatures for RSA with a 2047 bit key size (generally not used) and 2048 bit key size will both be 256 bytes in size.

The error conditions of I2OSP should never happen for RSA / PKCS#1 as all calculations will result in a number smaller than the modulus. So the number will fit - by definition - in an array that can also hold the modulus.

The encoding returned by I2OSP is specific to RSA instead of specific to the internal number representation within a language / runtime / operating system / CPU architecture. This means that the byte encoding of the signature is portable across the different runtimes.

OS2IP will do the exact reverse. It's usually easier to implement as languages/runtimes generally simply skip leading zeros when converting integers from bytes. You must however make sure that the bytes are interpreted as an unsigned big endian value.

For little endian machines it may be required to reverse the order of bytes. It could also be required to add a 00 valued byte at the most significant location. Otherwise the number may be interpreted as a (two-complement) signed value, which may result in a negative value.

Often I2OSP is programmed the way it is described in the PKCS#1 specifications. This however is a rather mathematical description of the encoding. Generally integers are already represented in a way that is largely compatible with the description of I2OSP, which means that some copying and resizing (and possibly reversing for little endian systems) is all that is required. For instance, check my implementation for Java here.


What are the approaches to private computations?

If the VM actually has anything that needs protection, running the VM on untrusted hosts is not secure (period). There is nothing that will change that.

Going to homomorphic encryptions etc. implies that even the VM doesn't know any secrets, only the source of the data (outside of VM and host) does. In this case, having a VM or not isn't even relevant.
There are of course still problems with the authenticity of the results etc. - just encrypting is never enough.

Using Intel SGX from within VMs relies on the support/cooperation of the VM software - meaning, it might be useful for separating VMs fom each other, but it can not help VMS against their malicious host.
Given that VMs are, well, virtualized, any hardware support is useless in your scenario. If the host and the virtualization software can't be trusted, your VM is not secure.


Is it possible to extract the decryption key from a locked android device

Is the data only safe when the phone is off?

This is really hard to properly assess and depends on your definition of "safe" alot. However I'll assume that you mean "is the data protected by the FDE encryption?".

The clear (and obvious) answer to this is no.
You can unlock your phone quickly (without having to wait one or two seconds) so the key for the FDE must be stored in RAM and thus the security level is "lower" than when the device is turned off.

To verify this yourself, observe that you enter your password in the pre-boot authentication and have to wait a moment until your phone can tell you whether the password was correct or not. This is due to the password-based key derivation function being used there which takes a lot of computation power which can be spend right after startup bu not each time the screen is unlocked (where the user wants to access his phone quickly and doesn't want to waste CPU / battery)


/dev/random only needed for key generation / CPU pattern encryption

This first scenario: it depends on the specific command, but it should need randomness when generating the key (or when deriving the key from a password, when generating the salt) and when generating the initialization vector for encryption.

The second scenario: when generating the master key, and when generating the salt used with the user's password to encrypt the master key. It does not need randomness for encryption, since there is no place to store initalization vectors. The algorithms usually try to compensate for this by using the index of the disk sector in the algorithm.

Also, I'm not sure if /dev/random is used; I think that at least OpenSSL uses /dev/urandom/.

For the second question, there are side channel attacks as mentioned. Depending on the implementation, it may be possible to retrieve keys by analyzing timings or energy consumption.


If we remove from RSA the requirement that the factors $p$ and $q$ of the public modulus $n=p\cdot q$ are prime, and instead allow composites, then depending on the definition of RSA used, the resulting cryptosystem works in the sense of allowing decryption either:

almost not (only for few messages or exceptional choices of $p$ and $q$); that's if we blindly apply one of the common definitions of the relation between the public and private exponents $e$ and $d$, including $d=e^{-1}\bmod((p-1)\cdot(q-1))$ and $e\cdot d\equiv1\pmod{\operatorname{lcm}(p-1,q-1)}$;
for some messages (often all or most); that's for relations like $d=e^{-1}\bmod\varphi(p\cdot q)$ and $e\cdot d\equiv1\pmod{\lambda(p\cdot q)}$, and if we compute Euler's totient function $\varphi$ (also noted $\phi$) or Carmichael's function $\lambda$ with knowledge of the factorization of $p$ and $q$;
for all messages; that's when in addition of using the above relations, $p$ and $q$ are coprime and squarefree, or otherwise said when all the factors of $n$ are distinct primes.

For an illustration of case 2., consider $p=187=11\cdot17$, $q=253=11\cdot23$, $n=p\cdot q=47311$, $\lambda(n)=\operatorname{lcm}(11-1,17-1,23-1)=880$, $e=3$, $d=e^{-1}\bmod880=587$. For any $x$ with $0\le x<47311$, $(x^e\bmod n)^d\bmod n=x$ holds when $x\bmod11\ne0$ or $x=0$, but all other $4300$ values of $x$ are exceptions; e.g. $42^{3\cdot587}\bmod47311=42$, $43^{3\cdot587}\bmod47311=43$, $44^{3\cdot587}\bmod47311=12947$.

Notice that choosing $p$ or $q$ as a huge random composite is unpractical: in order to compute a working $(e,d)$ pair we practically must know the factorization of $n$, and factoring a big-enough composite $p$ is seldom easy, and sometime entirely impractical. Also, this method of choosing $p$ and $q$ would lead to $n=p\cdot q$ that could be relatively amenable to factorization, making the cryptosystem unsafe.

By the definition of RSA per PKCS#1 after PKCS #1 v2.0 Amendment 1 of July 2000, RSA only requires that all the factors of $n$ are distinct odd primes $p_j$, and that $e\cdot d\equiv1\pmod{\lambda(n)}$, where $\lambda(n)$ simply reduces to the Least Common Multiple of the $(p_j-1)$. When there are more than two $p_j$, the cryptosystem is known as Multiprime RSA. It allows for faster computation of the private function, and is safe with proper choice of the $p_j$.


I guess it is wanted to assign a 32-bit integer to each of human readable strings in some collection (for the problem as worded, the answer is 00000000000000000000000000101010).

Assuming that the human readable strings are chosen independently of the definition of MD5, then the first 32-bit of the MD5 hash of each string is about uniformly distributed. That would be a classical result for any hash that is a PRF (for any distinguisher able to recognize the first 32 bits from a random function can trivially be turned into a distinguisher for the full function). MD5 was designed with the goal to be a PRF, and remains good enough. Sorry I do not have a reference.

Odds that there is at least one collision with $n$ strings is
$$p=1-(2^{32})!/(2^{32}-n)!/2^{32\cdot n}\approx1-e^{-n\cdot(n-1)/2^{33}}\approx n\cdot(n-1)/2^{33}$$
The approximation on the right is quite good for $n$ up to about $2^{14}$, arguably including " a few thousand strings ". For $n=10,000$, $p\approx1.2\%$.

However, one knowing your plan to do this and in a position to generate the human readable strings can make the number of collisions high (including having all the strings giving 00000000000000000000000000101010). That MD5's collision resistance is now badly broken is not relevant: the problem is that a 32-bit value is too small. To solve this issue (and return to the probability of collision previously stated even for evil choice of the strings), use a MAC with a secret key, e.g. a truncated HMAC.

Note: the MAC solution also allows to solve the problem of finding a hash with no collision for a particular collection, known as a perfect hash, in a simple way: try distinct keys at random until finding one for which there is no collision: that's easy to check with with $2^{32}$ bits (512 MiB) of RAM. It is tried on average $1/(1-p)$ keys and less than $n/(1-p)$ MAC computations. When $n$ grows past about $2^{17}$ that becomes increasingly impractical, and dynamic perfect hashing comes to the rescue.


Should different key pairs be used for signing and encryption?

Yes.

Modern cryptosystems are designed and analysed under the assumption that the key is never used for anything else. If you use your encryption keys for digital signatures, you are violating that assumption, and it is very easy to construct schemes where this violation will compromise security.
It is possible to construct schemes that can use the same key, but there is little reason to do so.

I have not looked at the specifics of iMessage, but I suspect that every time you send a message, you encrypt that message for many recipients (each device, possibly), but sign only once. Each device will have to decrypt only one ciphertext, and verify one signature.
RSA is very fast for encryption, while ECDSA is faster at verification. EC-based encryption would be more expensive for encryption. Apple's choices seem reasonable.


To the best of my knowledge, this is unknown. That is, Levin's construction is a one-way function but most certainly not a one-way permutation. I don't see any way in which it can be modified to make it a permutation, since the way it works is by running arbitrary machines and then amplifying. Since there is no efficient way of checking if something is a permutation by looking at the machine (to the best of my knowledge), I don't see how one could modify Levin's construction.
Of course, this is just a limitation of what we know, and it begs a very interesting research question. Does there exist a universal one-way permutation? Similar questions can be asked about other primitives as well. A good paper to read that has some relation to this question (for other primitives) is On Robust Combiners for Oblivious Transfer and other Primitives by Harnik et al.


Is it secure to use ECDSA for any arbitrary point on the Elliptic Curve as the Generator point?

However, suppose that you are aware of public key $K$ and are looking to do a tweak of $K$. Let $t$ be the tweaking factor, and so $tK=K'$. If you then wanted to prove that you are in possession of $t$, how would you do that?

The obvious way to do this is a Schnorr proof of knowledge, which does precisely what you're looking for; given a public $K, tK$, it demonstrates that you know $t$.  Wikipedia lists the interactive version; it can be made noninteractive by having the prover generate $c$ based on a hash of the commitment $t$ (and possibly other stuff if you need to bind the proof to something).

  An immediate thought (which I am confident will not work) is to use ECDSA with $K$ as the generator point. However, it might be the case that $K$ is of a very small order $n$ which may not be prime.

That would also work (which isn't that surprising; ECDSA is essentially based on Schnorr, tweaked enough to avoid patents that have since expired); it's kludgier, however it might be preferable if you just happen to have an ECDSA implementation just lying around.  If $K$ does have small factors, you might need to work around it (as some values might not be invertable), however that wouldn't appear to be a major issue.

And, if $K$ is a very small order, then deriving $t$ would be easy, no matter what proof-of-knowledge method you use (and so there's little point in the problem).  In any case, we almost always use elliptic curves where the order of the curve is $hq$, where $h$ is a small value (the most common values are 1 and 8), and $q$ is a large prime - except for a handful of points (actually, a total of $h$ points), all points have a large order (at least $q$).


What is the minimum and maximum value of an RSA private exponent?

In summary:

Modern practice is to fix a small public exponent $e$ such as $e=2^{(2^4)}+1=65537$, then choose a public modulus $N$ of $\text{nlen}$ bits (the key size) with large random prime factors compatible with $e$, then compute the RSA private exponent $d$ from that. With near certainty, that $d$ will be at least $\text{nlen}/2$-bit. That can be used as a minimum for other methods. For RSA1024, that's $d$ at least 512-bit.
If given a choice, compute $d=e^{-1}\bmod\lambda(N)$, and it's bit size will be strictly lower than the key size. For RSA1024, that's $d$ at most 1023-bit. See Carmichael function for the definition of $\lambda(N)$.
Otherwise, it is still recommendable to keep $d<N$ for compatibility with common software. For RSA1024, that implies $d$ at most 1024-bit.

Note: by the mathematical definition, a positive integer $m$ is $b$-bit when $2^{b-1}\le m<2^b$. Computer implementations often measure the size of integers differently: adding one for sign, or/and rounding up to the next multiple of some power of two, or/and adding more overhead for headers.

Caveat: RSA1024 might be vulnerable right now to well-funded and competent adversaries. For new applications, it has been deprecated for a decade at least, and RSA2048 is considered OK only till 2020 or 2030, depending on source (see the Keylength website).

Minimum value

Negative $d$ work, but at the price of an extra inversion modulo $N$ at each use, thus have little practical interest. We exclude negative $d$ in the following.

When $e$ is fixed or chosen then $d$ computed (as is modern practice), the lower bound for $d$ is commonly $d>2^{\text{nlen}/2}$ (e.g. in FIPS 186-4), or $d>0$, or just unspecified. In fact, $d$ will typically be few (if any) bit(s) less than $\text{nlen}$, and $d<2^{\text{nlen}-64}$ should seldom occur. $d>2^{\text{nlen}/2}$ is met with overwhelming probability for any sound key generation procedure that computes $d$ without attempt to minimize it, or in other words where:

$d$ is computed from the public exponent $e$ and the prime factors of the public modulus $N$ (these factors are noted $p$ and $q$ is the common case of $N=p\,q$; or more generally $r_i$, with $N=\prod r_i$, and $p=r_1$, $q=r_2$ ).
and $e$ and the $r_i$ are chosen independently of each others, except for meeting the requirements: the $r_i$ are suitably large random primes, $\gcd((r_i-1),e)=1$ (implying $e$ odd), and $e\ge3$.
Exceptions to the above:

Sometime it is additionally checked that the $r_i$ are suitably different from each others. For safely large $r_i$ and good random generator, such check never fails.
From a mathematical standpoint, $e$ can safely be chosen as $N$, in which case it depends on the $r_i$. That is the case in Christopher Cocks's 1973 cryptosystem, see here for bibliography.

In any case, $d$ must be much larger than $N^{0.292}$ in order to avoid an attack by Dan Boneh and Glenn Durfee, Cryptanalysis of RSA with Private Key $d$ Less than $N^{0.292}$, in proceedings of Eurocrypt 1999. A safer lower bound is $d>\sqrt N$, or the aforementioned $d>2^{\text{nlen}/2}$. That consideration is relevant at least when $d$ is chosen, as in in R.L. Rivest, A. Shamir, and L. Adleman's A Method for Obtaining Digital Signatures and Public-Key Cryptosystem (in CACM, 1978).

Maximum value

The upper bound for $d$ depends on context.

From a mathematical standpoint, there is no limit: any $d$ with $\lambda(N)$ dividing $e\,d-1$ is acceptable, where (for distinct $r_i$ ) $\lambda(N)$ is computed as the Least Common Multiple of the $(r_i-1)$. We can add any multiple of $\lambda(N)$ to any valid $d$, and obtain another valid $d$.
In a PKCS#1 context, we must additionally have $0<d<N$, which implies $d<2^{\text{nlen}}$. That leaves at least two possible $d$, sometime more.
Some definitions of RSA state that $d=e^{-1}\bmod\varphi(N)$, where (for distinct $r_i$ ) $\varphi(N)=\prod(r_i-1)$, see Euler's totient. This implies $d<\varphi(N)$, which implies $d<N$ and $d<2^{\text{nlen}}$. For usual RSA with two factors, that method of computing $d$ implies $d<N-2\sqrt N$, thus the upper bound is slightly lower than $d<N$ in PKCS#1.
In a FIPS 186-4 context, it is required that $d=e^{-1}\bmod\lambda(n)$. That is the smallest positive $d$, and it is often markedly lower than with the previous method. We get $d<\lambda(N)$, thus $d<\varphi(N)/2$, thus $d<2^{\text{nlen}-1}$, and for two factors $d<N/2-\sqrt N$.


is there a way to specify the encrypted message length when using private and public keys?

Asymmetric cryptography are never space-efficient.

For example, in multivariate cryptography the public key is often the expanded matrix of coefficients of indeterminates, where as the private key are decomposed transformations allowing efficient decryption/signing. Although you can get ciphertext/signature size not too different from plaintext/hash size in multivariate schemes, the public key size is almost always huge.

The reason I bring up multivariate cryptography is 1) it's secure against quantum computers (as far as we know). 2) it's space efficient with ciphertext and plaintext as you've requested (but not with key sizes). and 3) it's a good illustrative comparison with symmetric-key cryptography.

Remember XSL attack? It fails catastrophically because accumulated rounds of AES permutations expands to high-degree multivariate expression of its inputs.

To summarize: You can specify ciphertext size with multivariate cryptography if you have the right scheme. But you loose the ability to specify public-key size there.

You can keep an eye on NIST PQC standardization, where there are some multivariate contenders. But keep in mind, that these schemes are in their earily stages of development.


Is it safe to store both the AES-related data and the PBKDF2-related data (except passwords) in one file?

All the parameters you've mentioned can be public. Furthermore, only the salt, IV and ciphertext cannot simply be guessed.

The IV is generally easy to retrieve once the key is known, so the making the IV secret doesn't make sense. In CBC mode and many other modes you may just not get the first plaintext block if the IV is completely absent, but the rest of the ciphertext will be available. In CTR mode you would get the IV directly once the key is known and if part of the first plaintext block is known.

So that basically leaves the salt. Now the salt is sometimes kept partially secret. This static, secret part is called a pepper. If you keep this secure then it can be seen as an additional input key that is required to generate the resulting output key. There still should be a random or at least unique salt otherwise identical passwords will result in the same key, which is definitely something you would want to avoid.

TL;DR you could use a pepper which sometimes makes sense if the pepper has different access requirements. All the other information can simply be stored with the ciphertext (but read on).

Note that there certainly is a danger when storing the algorithm with the ciphertext. The problem is that if an attacker can switch the algorithm from GCM to CTR that you suddenly get unauthenticated plaintext. You'd better make sure that an attacker cannot simply change a few parameters to make your protocol less secure.

That would be a lot more dangerous than storing any of these public parameters together with the ciphertext.

If you decide to use authenticated ciphertext then yes, please make all the parameters part of the Additional Authenticated Data (AAD). Note that all AEAD modes already include the IV in the verification, so there is absolutely no reason to include it in the AAD.


Unless otherwise stated, $a$ is any integer representative of an eponymous element of $\mathbb{Z}_p$.
$$\begin{align}
a^3\equiv a\pmod p
&\Longleftrightarrow a^3-a\equiv0\pmod p\\
&\Longleftrightarrow a\cdot(a^2-1)\equiv0\pmod p\\
&\Longleftrightarrow a\cdot(a-1)\cdot(a+1)\equiv0\pmod p\\
&\Longleftrightarrow\begin{cases}
a\equiv0\pmod p&\text{ or}\\
a-1\equiv0\pmod p&\text{ or}\\
a+1\equiv0\pmod p
\end{cases}\end{align}$$
The last step uses that since $p$ is prime, if it divides the product of some integers [here: $a$, $a-1$, and $a+1$ ], then it must divide at least one of these integers. The reverse trivially holds without the hypothesis that $p$ is prime.

Since $p$ is greater than $2$, the three solutions $a\equiv0\pmod p$, $a\equiv1\pmod p$, $a\equiv p-1\pmod p$ are distinct elements of $\mathbb{Z}_p$.

Without the hypothesis that $p$ is prime, there can be additional solutions to $a^3\equiv a\pmod p$; for example, $a^3\equiv a\pmod{15}$ holds for nine out of fiteen elements $a$ of $\mathbb{Z}_{15}$.

Keep in mind that $x\equiv0\pmod p$ means exactly the same as: $p$ divides $x$.

Thanks to CGFoX for having corrected the $a\cdot(a^2-1)$ expression.


Inverse function of RSA and safe prime requirement of DH Key exchange

One possible statement of the Discrete Logarithm Problem modulo prime $p$ (the one used in practice in DSA, and more generally when working in a Schnorr group) goes:

given

large random prime $q$,
very large prime $p$ with $p-1$ a multiple of $q$,
integer $g$ of order $q$ modulo $p$ (equivalently, such that $g^q\bmod p=1$ and $g\bmod p\ne1$ ),
$a$ obtained by taking random integer $x\in[0,q)$ and computing $a\gets g^x\bmod p$

find $x$.

The best known algorithms to solve this on classical computers (including Pollard's rho for logarithms) have cost $O\left(\sqrt q\;\log p\;\log\log p\right)$ when $p$ is suitably large (e.g. 3072-bit $p$ or larger for 256-bit $q$).
Variants exist with the following:

$p=2q+1$ (equivalently, $(p-1)/2$ is prime¹); but then the security bound is much lower for equal $\log q$, because the best algorithm becomes (an extension of) GNFS.
It is asked that $g$ is of order $p-1$ (equivalently, that $g$ is a generator), rather than of order $q$ as in the above. It has at least the virtue of insuring that the order of $g$ is large.
Discussion on $p-1$ being a multiple of a known large $q$ is removed and replaced by hope that's the case, which holds with good probability for random $g$ and very large prime $p$. One problem is, it can get hard to find $q$ and/or ascertain² the order of $g$.

By any of the above definitions of the DLP, the modulus $p$ is prime. That makes it incorrect (or at least, neither proven nor widely conjectured) to state, as the question does:

The hardness of RSA depends on two things: the Integer factorization problem and the DLP.

Also, by any of the above definitions of the DLP, the order of $g$ is a given (it's the given $q$, or $p-1$ in some variants). Even if we extend the definition of the DLP to allow for composite modulus $n$ instead of $p$, and as long as we keep assuming that the order of $g$ is a given in that extended DLP, the above statement remains incorrect (or at least, neither proven nor widely conjectured): we don't know how to break RSA given an hypothetical oracle breaking that extended DLP.
If we further extend the definition of the DLP by not assuming that the order of $g$ is a given, then it can be proven that breaking this further extended DLP allows to factor $n$, thus break RSA. The above statement becomes true, but equivalent to the common wisdom:
The hardness of RSA depends on the Integer factorization problem.
or otherwise said: breaking the integer factorization problem breaks RSA. The converse is an open problem, and sometime conjectured.

What is wrong with choosing a multiple of two primes as modulus in DH Key exchange?

If additionally the order of $g$ is known, we can factor the modulus $n$ as $n=r\,s$ with primes $r,s$. And then, using the Pohling-Hellman algorithm, we can reduce the DLP modulo $n$ to several easier DLP problem modulo $r$ and $s$ (or modulo $r^2$ is $s=r$).
In Diffie-Hellman, we don't need to make the order of $g$ known, thus we could get away with choosing $n$ in a way making it hard to find its factorization, as in RSA. But then security of DH would depend to some degree on integer factorization on top of some variant of the DLP, and that's generally not something wanted. It's done only in some contexts, like RSA accumulators.
Further, in many applications of the DLP to cryptography including Schnorr signature and DSA, the order of $g$ needs to be public. Thus using a composite $n$ would require using a much larger modulus at equivalent security, leading to slower computation for no benefit.

¹ That is, $p$ is a safe prime. That's stated as a requirement for DH key exchange in the question, but it's not: any Schnorr group (as in the first part of the question) will do.
² However, we can still pick $g$ of likely order $p-1$ with low residual odds of the contrary: pick a random $g$ until $g^{p-1}\bmod p=1$, and $g^{(p-1)/r}\bmod p\ne1$ for all primes $r$ dividing $p-1$ and $r$ low enough that we find it with simple factorization methods: trial division to some bound and a few rounds of Pollard's rho for factorization.


Having CBC-MAC of a one block message, forge CBC-MAC of two blocks

Given just $a$ and $M(a)$, you can construct the message $a\,\|\,b$, where $b = a \oplus M(a)$, which gives the same CBC-MAC output $M(a\,\|\,b) = M(a)$ as $a$ itself.

Indeed, we can append the block $b$ to the message as many times as we like without changing the MAC value: $M(a) = M(a\,\|\,b) = M(a\,\|\,b\,\|\,b) = M(a\,\|\,b\,\|\,b\,\|\,b) = \dots$

The reason this works should be apparent by looking at the structure of CBC-MAC:

As the diagram shows, a message like $a\,\|\,b\,\|\,b\,\|\,\dots$ is processed block by block.  In the first step, we encrypt $a \oplus 0 = a$ with the block cipher, and obtain $M(a) = E_k(a)$ as the output.  If the message ended here, this would be the resulting MAC value.  However, if the message continues, the next block $b$ is XORed with the output $M(a)$ of the previous step and encrypted with the block cipher again.  If we choose $b = a \oplus M(a)$, then the input to the block cipher will be $b \oplus M(a) = a \oplus M(a) \oplus M(a) = a \oplus 0 = a$ again, and thus the output will also be $E_k(a) = M(a)$ again.


Yes, TLS supports ECDSA for signing and ECDH for key exchange. You can read about it RFC 4492. Notice you don't get RSA, but you get signing and key exchange which are major functions of TLS.

Related material:
How do I create an ECDSA certificate with the OpenSSL command-line
SSH key-type, rsa, dsa, ecdsa, are there easy answers for which to choose when?

As far as patents go, see this question. I am not aware of any ecc libraries that claim to not violate patents. Bouncy castle says it is up to you to figure that out. Openssl's ecc implementation was supposedly built to avoid patent issues.

Is elliptic curve a DH function or PKI
Neither really. There are elliptic curve variants of ElGamal and RSA. Depends exactly what your definition of PKI is though as you can have ECDSA certificates with a public and private key. You can then start a PKI by signing other certificates, etc.


How random are permutations generated from Feistel networks with a small number of rounds?

The Luby-Rackoff theorem says that a 3-4 round Feistel network is a pseudorandom permutation for some sufficiently large block size.  As this paper by Patarin on Feistel networks with 5 or more rounds puts it:

  We will denote by $k$ the number of rounds and by $n$ the integer such that the Feistel cipher is a permutation of $2^n$ bits → $2^n$ bits. In [3] it was proved that when $k ≥ 3$ these Feistel ciphers are secure against all adaptative chosen plaintext attacks (CPA-2) when the number of queries (i.e. plaintext/ciphertext pairs obtained) is $m \ll 2^{n/2}$. Moreover when $k ≥ 4$ they are secure against all adaptative chosen plaintext and chosen ciphertext attacks (CPCA-2) when the number of queries is $m \ll 2^{n/2}$ (a proof of this second result is given in [9]).

If your domain size is very small, then indeed, your number of queries $m$ can easily exceed the bound.  If I understand your code right, you're doing cycle-walking on a Feistel network with a block size of 4, so by the time you hit $\sqrt{2^4} =$ four queries you've already hit that bound.

Incidentally this is why real-life format preserving encryption modes like those in NIST SP 800-38g use Feistel networks of 8 rounds (FF3) or 10 rounds (FF1).  Note that even then an attack was found against FF3 that required a revision to the mode.


Has a collision ever been found for SHA-1/2/3 when truncated to 128 bits?

I'm not aware of any case where somebody actually searched for such a collision.

However it would certainly be possible as the same workload ($2^{64}$) was already accomplished a few years ago (2002) by this project, having brute-forced RC5-64.

Now assume you'd use the full power of the bitcoin blockchain (300 Peta-Hashes / s = 600 Peta-Hashes /s for single hashing(19th may 2015)) you'd expect a (64-bit-)collision after 30.74 seconds ($=2^{64}/600*10^{15}$).

As noted correctly by poncho there are algorithms that help you overcome the massive amount of memory you calculated. Of particular interest would be a "memoryless" variation of Yuval's birthday attack(book page: 369, pdf page: 50 of the "Handbook of applied Cryptography").
This related question may be helpful.


How to symmetrically encrypt 64bit values?

Are there any existing algorithms that work for this scenario?

Yes, actually, there are a number of 64 bit block ciphers.  The standard wisdom is that they aren't encouraged for general use, because standard block cipher modes tend to start leaking information when you get near the birthday bound (in this case, circa 30 Gbytes); however for your use case, that would not be a concern.

Here are some options:

3DES (aka TDES); this is DES applied three times with three different keys; this has the advantage of being very well studied.
Speck which has parameter sets with 64 bit block ciphers.  This has the advantage of being the fastest alternative, and was designed by people who know that they're doing, and has done through a surprising amount of cryptanalysis.
An FPE cipher (such as FF1, which can handle any arbitrary block size (including 64 bits).  This has the advantage in that they allow the option for a tweak (which is a convenient place to place the "other hidden parameters", should you decide that is an advantage).  It's slower than the alternatives; with FF1, the security comes from the underlying security of AES, plus the provable security of the Feistel structure.

Now, these take keys longer than 64 bits; the common wisdom is that a 64 bit key is just not long enough.

  How hard would it be to crack? I.e., compute values that decrypt to valid indices.

For any of the above, the only practical option an adversary would have would be to randomly guess ciphertexts, and hope to stumble on one that decrypts to a valid index.

  How much does the possession of more samples affect the efficiency of cracking it?

For any of the above, having vast quantities of samples will still make the attack infeasible.

  What's wrong with a naive approach like...

ARX ciphers (actually, any cipher, but especially ARX) are tricky to get right.  ARX ciphers in particular tend not to be great at disrupting differential and linear characteristics (which means any such design would really need to be well studied to make sure that it does).

  What approaches, resources, etc. would you use to both analyze the algorithm, and design a better one?

I'd suggest you go with a design which has already been analyzed; I list three above.


It's the probability that an ECDSA signature (over the Bitcoin curve, secp256k1) will have the corresponding size. In other words, 25% of the secp256k1 ECDSA signatures have 73 bytes, 50% of them have 72 bytes and 25% of them have 71 bytes. Of course, after the signature is generated its size is settled and the probability does not apply anymore.
(The reason is that an ECDSA signature is the ASN.1 encoding of a structure with two integers. Each encoded integer requires a bit to indicate the sign, even though in ECDSA they are always positive. Therefore, if the upper bit of the integer is set, then the encoded integer will require a whole byte to store the sign bit since the integers have 256 bits, a multiple of 8. There is a chance of roughly 50% of an integer in the secp256k1 ECDSA signature having the upper bit set, requiring a whole byte for the sign bit, which creates the 25%/50%/25% split over two integers.)


Possible to detect if a message is PGP encrypted/signed (ciphertext)

The only possible answer to this is to check out the OpenPGP format and see if the message adheres to that format. You may need to build in some mechanisms to filter out tiny mistakes or extensions in the message though.

As Open PGP is, well, open, there should be plenty libraries that perform this parsing for you. Library recommendations are off topic here but you should be able to find one to your liking using a search engine.


Store hashed password using Digest authentication

The server doesn't need the plaintext.  When the password was "saved" the server generated a nonce and concatenated that with the password and then hashed the combination.  The server saves the nonce and the hash, not the password.  Now, when client sends the hashed value to the server all the server does is compare that it against the saved value.


When I learned about SRP we were told it wasn't seeing much deployment due to possibly infringing on EKE patents. Network Computing had this to say in 2002:

  Standards groups have made several attempts to induce Lucent to talk about its EKE patent -- to no avail. Even with Lucent's silence on the topic, few vendors have been willing to use SRP. To further cloud the situation, there's been a new patent issued claiming that it too covers SRP.

The SRP website, however claims

  Since SRP is specifically designed to work around existing patents in the area, it gives everybody access to strong, unencumbered password authentication technology that can be put to a wide variety of uses.

If I had to guess, I'd say patents were part of the original problem and that effect has continued even today. Whether patents are the sole reason for limited deployment or even the major reason is beyond me.