How long would the 100 Year Cryptography Project have secured its data had it been started 100 years ago?

In 1911, there was no computer either. With much more modest goals of security for the next few months, the German army came up with the Enigma, which was broken. Before the 1970s, cryptography was essentially a military-only domain, so there were no "openly collaborating knowledgeable experts". The situation was qualitatively different. So it is a bit unfair, and of limited scientific value, to try to compare cryptographic systems before and after the seventies.

Moore's law was published by Gordon Moore in 1965, and thus was quite well known 10 years later. In 1976, people trying to build a system which would still be safe 100 years later would have accounted for Moore's law, meaning an extra 100 bits for symmetric keys, and 200 bits for hash functions (there are several variants of Moore's law, but one of the most optimistic says that every two years you can put twice as many transistors on a given die and clock them twice faster, leading to a doubling of CPU power every year). Symmetric encryption was beginning to be understood; DES had just been approved as a US standard, so, presumably, people aiming for 100-year security would have proposed something like 5-DES. They might have missed the point about block size: DES has 64-bit blocks, making it unsuitable for securely encrypting more than a few dozen gigabytes with a given key. Even if believing Moore's law, the sheer volume of today's data was not envisioned at that time.

In 1976, there was no hash function worth speaking of. The Merkle-Damgård construction was published in 1978. Even MD2 did not appear until 1989.

Digital signatures may have been a problem. In 1976 there was no efficient digital signature system. When RSA was published in 1978, the article contained an overly optimistic comment about how a 512-bit integer would resist attacks for millions of years (this became breakable in 1999). Also, appropriate padding techniques were not developed until the early 1990s.

So a "100-year cryptographic system" developed in 1976 would have been partially broken by now; but some parts would have kept well (probably symmetric encryption). Also, the system would have become inadequate for our evolving needs, in the same way that even a very fast Enigma machine would still encrypt characters out of a very small set (only letters, no space and no digits !), making it unsuitable for encrypting bytes.

This shows that we tend to get wrong ideas about what the future will hold (we are in 2011, where is my flying car ?). In particular, we do not understand what we will need 40 years from now, and we have relatively little grasp of the threats that will appear at that time. Right now, the trendy fearsome threat is the Quantum Computer.

(This is all an intricate way of saying that your question cannot be answered.)


Is it safe to use a MAC as iv for CTR encoding?

First remark here should be don't roll your own crypto.  That said, your idea seems to be a variant of Synthetic Initialization Vector mode (SIV, RFC 5297), where a pseudorandom function of the plaintext and associated data is used to generate a value that doubles as the message authentication tag and the IV for the cipher.  Your random 3-5 byte value is an optional nonce, which in SIV is just an associated data field.

Note that SIV was designed for deterministic encryption (exceptional cases where it's OK if encrypting the same plaintext twice with the same associated data produces the same ciphertext) and for nonce misuse resistant encryption (cases you don't actually want nonce reuse but you want to minimize the damage if it does happen).  This ties to @EnTaroAdun's answer—the low diversity of random nonce values may be a problem, but if it isn't, then SIV is a well-designed, well-vetted mode that handles your scenario out of the box.  SIV also allows for arbitrary associated data fields, which can help mitigate potential duplication problems by including other contextual data other than the 3-5 random bytes into the synthetic IV computation.

SIV is not a common mode, so there's a good chance you won't find a ready-made implementation for your language.  So apart from a several nasty details (e.g., why not just use truncated HMAC-SHA2 directly?  Are you vulnerable to MAC equality comparison timing attacks?  How are you generating keys for the MAC and cipher?), your idea is neither obviously wrong nor obviously right either.


What is the difference between data compression and compression in cryptographic algorithms?

In data lossless compression we want the data recoverable from the compressed form. This is usually helpful if the entropy is low like text files, so-called zipping.
In data lossy compression like JPEG, we still want to get the image (data) but we don't care about the full quality of the image. This can be considered as the original data can be recovered approximately.
The compression function of hash functions (one-way compression function) takes two inputs and produces one output - the compression ratio doesn't need to be 2:1. The transformation is required to be

one way: i.e. given an output finding the input value should be difficult.
and, have avalanche property: each output bit must depend on all input bits.

Being one way is not a desired property for lossless compression, however, lossy compression is not totally one way but some information is lost. JPEG or similar compression is not a good compression for hash functions.

Avalance property doesn't suit the data compression since that causes a random behavior on the compression. In avalanche property, we want each output bit to have a 50% chance of flip for a bit flip of an input bit.

In short, a single word "compression" should not be used to identify those. Use the "data lossless compression" or "data lossy compression" for data compression and "compression function" for hash functions.


Yeah, of course, your RFC has references:

  PSS Algorithm

  Although there are no known defects with the PKCS #1 v1.5 [P1v1.5]
     signature algorithm, RSASSA-PSS [P1v2.1] was developed in an effort
     to have more mathematically provable security.  PKCS #1 v1.5
     signatures were developed in an ad hoc manner; RSASSA-PSS was
     developed based on mathematical foundations.

If you follow that link you find that it was defined in RFC 3447, which is called the "Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1". So these are the official standards from RSA Laboratories, except in RFC form. There is also v2.2 which just defines a different set of hash functions, of which only SHA-224 is moderately interesting in the given setting.

In full, the algorithm name is RSA (Rivest, Shamir, Adleman, after the team that thought it out), Signature Scheme with Appendix for SSA, and finally Probabilistic Signature Scheme for PSS. Commonly we just call it RSA-PSS or just PSS though.


Am I right?

Yes, with double encryption, if both are functionally correct and at least one is CPA-secure, then the composition is CPA-secure.

  If it is true, why is there no double public-key encryption scheme?

Because you took a scheme that can be reasonably classified to be "unbreakable" and then combined it with an other "unbreakable" one, you have constructed an "unbreakable" one that takes more time to compute than a single "unbreakable" one. There's no practical advantage to such combinators if we're confident in the security of the scheme we're using. If we're not confident either we pick a better one - or if we have also no faith in the better one we do indeed use such combinators. If you want a recent example of this, look no further than the hybrid ECDH / PQ-Crypto key exchanges that are being tested where we don't have faith in the PQ-Crypto yet so use ECDH to secure it against classical adversaries.

  Is $\Pi$ secure both in the sense of $S'$ and $S''$?

To prove this I suggest a simpler approach of checking whether $\pi\circ\operatorname{Enc}\circ\pi'$ is $S'$-secure assuming $\operatorname{Enc}$ is $S'$-secure (coming up with the correct decryption is left as an exercise to the reader) and $\pi,\pi'$ are any permuations applied to the input and the output.


Bitslicing is a technique where computation is:

Reduced to elementary operations (called gates) with a single bit output (typically NOR, XOR, and similar like OR AND NAND NXOR, often with further restriction to two inputs), rather than operations on words or integers spanning several bits.
Executed in parallel, with as many simultaneous instances (on a single CPU) as there are bits in some register kind, performing NOR, XOR.. simultaneously on all bits of such registers.

Doing 1 generates a large number of gates: XOR of two $n$-bit words requires $n$ gates; for $n>1$ their addition modulo $2^n$ requires $5n-6$ gates; each 8-bit S-box lookup in AES SubBytes requires about 128 gates; on the other hand rotations, arbitrary bit shuffling, selection or expansion requires no gate.
Doing 2 implements $w$ gates per instruction manipulating $w$-bit registers, and most of the speedup (if any) comes from that parallelization by a factor of $w$ (caveat: the effective $w$ can't be larger than the number of computations to perform simultaneously). Increasingly many embedded CPUs support $w=32=2^5$, CPUs with AVX instructions even support $w=256=2^8$. Most importantly, bitsliced code is immune to cache-related side channels (including timing). As a bonus, it is extremely linear, that makes efficient scheduling of data accesses easier, and there's no branching delay.
On the downside of bitslicing: Most importantly, making $w$ simultaneous operations do not match all workloads! For a single large file and common modes of operation of a block cipher, only CTR (or the flawed ECB) is fully usable (CBC and CFB are usable for decryption only, OFB is unusable). Also, the code is large and relatively complex; conversion from normal to bitsliced form of arguments (and back for results) requires bit transposition, which adds some significant overhead; lots of intermediary results or state data that would fit in registers or L1 cache in a normal implementation, do not.
In principle, any cryptographic calculation performed on multiple instances can be bitsliced. However many operations natively handled without bitslicing are unlikely to gain any speed benefit; this includes anything too simple (like the proposed XOR), or with grossly inefficient translation to gates (like modular multiplication, or looking up large arbitrary fixed tables, or sizable dynamic tables), or where the execution flow has too many paths. Refer to Ilmari Karonen's answer for a more detailed classification. And again, we need to be in a position to make several computations in parallel!
The archetypal example of a real cipher where bitslicing can have a speed benefit is (3)DES, as pioneered by Eli Biham's A fast new DES implementation in software (in Proceedings of FSE 1997).

Anything much simpler than DES that I could construct to show the benefit of bitslicing would be far from real-life; so I take as example a purely software implementation of (single) DES, with pre-computed subkeys, on a CPU with like a dozen general-purpose 128-bit registers, 128-bit (cache) memory accesses, for encryption of 128 blocks (1024 arbitrary bytes; I ignore optimizations possible in CTR mode).
A traditional (non-bitsliced) implementation goes:

for each of the $w$ blocks

transform the input block into two 32-bit halves L and R per Initial Permutation (IP, a bit transposition)
for round $r$ from 1 to 16

load the 48-bit subkey for round $r$ into a register K
for S-box $s$ from 8 to 1

make an appropriately rotated copy or R
XOR that with K
keep the low 6 bits of that
use that as the index to load the $s$th S-table, consisting of $64=2^6$ values each 32-bit (implementing the S-box and part of permutation P, hence the wide output); that step often dominates the cost and can be the target cache-related side channels
XOR that into L
shift K to the right by 6 bits for the next S-box

exchange R and L

transform the two 32-bit halves R and L into the output block per IP-1

The S-box loop is customarily unrolled (as well as at least two consecutive executions of the round loop, which makes the exchange essentially free), thus cost is dominated by the numbered steps. We can suppress 1 out of 8 steps 1 and 6. So a good approximation of the cost (ignoring IP and IP-1 for now) is $w$ times 16 times: 9 memory loads (8 of which indexed) and about 38 other simple operations.
Bitsliced DES suppresses the outer block loop, replacing it with operations on $w=128$-bit at each step manipulating block-dependent data:

transform the 128 input blocks (each 64-bit) into 64 memory words (each 128-bit) each holding all the bits of the same rank in a block (a bit transposition)
for round $r$ from 1 to 16

load the 48-bit subkey for round $r$ into a register K
for S-box $s$ from 8 to 1

for each of the 6 input bits j of S-box $s$
  a) duplicate the rightmost bit of K into a 128-bit wide register Tj
  b) load the 128-bit memory word holding the appropriate bit of the state
  c) XOR that into Tj
  d) shift K right by one bit
for each of the 4 output bits of S-box $s$
  a) compute that output bit (simultaneously for all the 128 blocks) as a boolean function of T1..T6, into 128-bit register X
  b) load the 128-bit memory word holding the appropriate bit of the state
  c) XOR that with X
  d) store that as the 128-bit memory word holding the appropriate bit of the state

transform the 64 memory words (each 128-bit) into 128 output blocks (each 64-bit) to form the result (a bit transposition reversing the first)

We'll unroll the round loop (if we want fixed addresses for the load/stores other than for the subkeys, we need two versions depending on if $r$ is odd or even). Independently: we can use that 2 out 6 values loaded at step 1a will be reusable for the next (or/and last) S-box, reducing the effective number of loads at step 1b, at the cost of few extra registers.
In step 2a, an S-box is replaced by boolean operations. Using the expressions derived by Matthew Kwan in Reducing the Gate Count of Bitslice DES (ePrint 2000/051), the average cost goes down to 51 boolean operations per S-box, at the cost of requiring some temporary registers, and somewhat undesirable bursts of stores at step 2d.
So a good approximation of the cost (ignoring initial and final transpositions) is 16 times: 65 memory loads and 32 memory writes (none indexed), and about 440 other operations.
Bitslice DES is thus a winner on speed if we ignore the cost of the initial and final transpositions, even if wide operations are somewhat more costly than narrow ones: memory accesses per round are reduced from $9w=1152$ to $97$; other operations from $38w=4864$ to $440$. That tenfold improvement (for $w=128=2^7$) outweighs the extra cost of the transpositions (which anyway is moderately higher than the cost of $w$ times IP and IP-1: in the end, the same amount of data is transposed). With careful coding, bitslice DES might be faster including for $w=32=2^5$.


Building an LSFR Logical bit map using characteristic polynomials

The recipocal $P^*(x)$ of a polynomial $$P(x)= a_0 + a_1x + a_2x^2 + \cdots + a_nx^n$$ is given by;

$$P^*(x) = a_n + a_{n-1}x + \cdots + a_0x^n = x^n P(x^{-1})$$

The feedback polynomial that defines the tap points of LFSR. The characteristic polynomial and is the reciprocal of feedback. Therefore;

Let $P^*(x)= x^4 \cdot P(1/x) = 1 + x + x^4 $ be the feedback polynomial LFSR   calculated by the recipocal of characteristic polynomial $P(x)$. Then the taps of the LFSR as follows;

 xxxxx <--
 ||      |
 ++--- ->|
 01234


Extra attributes in a certificate signing request

From RFC 2985:

  The challengePassword attribute type specifies a password by which an
  entity may request certificate revocation.  The interpretation of
  challenge passwords is intended to be specified by certificate issuers
  etc; no particular interpretation is required.

This has also come up over at Information Security Stackexchange with the TL;DR being it's the password you set during the certificate request to share a revocation password with the CA, this however is rarely to never used in practice, because CAs nowadays have "normal" log-in mechanisms just like any other website and use them control revocation.


Argon2 output length and parameter storage?

You need to consider the weakest link property: a security system is never stronger than its weakest link.  Since Argon2 is a password-based function, the weak link here is going to be the strength of your users' passwords.  Choosing a longer output length doesn't help if the passwords' entropy is lower than that.

Think of it this way: if the hash function is secure, the attacker has two ways to attack the passwords:

Use dumb brute force to try and find a preimage of one user's passwords.
Use knowledge about user habits to guess more likely passwords ahead of less likely ones.

Longer output may make #1 harder, but once you make #1 hard enough then #2 becomes the easy path and attacker will just try that.  So Argon2's authors' recommendation of 128-bit hashes sounds fine, because the only circumstance in which the 128 bit output would be the limiting factor is if your users' passwords were crazy entropic, like:

ASCII printable uniformly random passwords of length 20 or more (6.6 bits/character);
PINs of 40-digit length or more, chosen uniformly at random (3.3 bits/digit);
11-word or longer Diceware passphrases (12.9 bits/word);
12-word or longer XKCD "correct battery horse staple" passwords (2,048 word dictionary, words chosen uniformly at random).

If your users could be counted on to choose passwords that strong, you wouldn't need a specialized password hash function in the first place!

  A second, but a little unrelated question, do you think you should store the parameters (that can change the hash) in the database along with the password & salt. Examples would be opsLimit, memLimit, outputLenght, ect...

Yes, you should store them.  Note for example that the Argon2 command line utility (which is available from the Argon2 repo) produces verification tags that integrate it (the "Encoded" field from this example from the link):

$ echo -n "password" | ./argon2 somesalt -t 2 -m 16 -p 4 -l 24
Type:           Argon2i
Iterations:     2
Memory:         65536 KiB
Parallelism:    4
Hash:           45d7ac72e76f242b20b77b9bf9bf9d5915894e669a24e6c6
Encoded:        $argon2i$v=19$m=65536,t=2,p=4$c29tZXNhbHQ$RdescudvJCsgt3ub+b+dWRWJTmaaJObG
0.188 seconds
Verification ok

Thinking about this some more, I think I understand why I'd be confused if I was in your position.  If the default 128-bit length is fine, and making it longer doesn't really offer more security, why does the function allow me to choose a longer output length?

Well, the reason is that Argon2 has two distinct uses:

Password verification
Key derivation

Long outputs are of no use in password verification, as I explained above, but of great use in the key derivation case.  An example situation where you want something like that is password-based encryption where you're doing something like encrypting a file with AES-256 but, instead of making the user manage raw AES keys, you try to be friendlier and let them use passwords instead.  This is, for example, how GnuPG's symmetric encryption mode works (albeit it doesn't use Argon2).

In this case, since your cipher needs 256-bit keys then you need the ability to generate 256-bit keys from your users' passwords.  So the selectable output length allows you to match the requirement.

Note that the weakest link property still applies here, so in that scenario even though you'd be using 256-bit encryption, the password would still be the weakest link.  What the longer output length allows you to do is to match a technical requirement imposed by the 256-bit cipher, and offers your users the option of choosing passphrases that are effective up to that security level—which very few will do (e.g., a 40 character random ASCII password!).


It's trivial to calculate collisions because the message blocks M1..Mn can be interchanged without issue. So EK(M1 XOR M2) = EK(M1' XOR M2') where M1' = M2 and M2' = M1. Different messages should obviously not calculate to the same MAC authentication tag.


Does any $x < p$ satisfy the curve equation of X25519?

If you have an elliptic curve given by the equation $y^2 = f(x) \bmod p$, then for each $x$, either $f(x)$ is a square modulo $p$, and there exists a square root $y$ such that $(x,y)$ and $(x,-y)$ satisfy the curve equation. If $f(x)$ is not a square modulo $p$, then this value $x$ does not correspond to a point on the curve, but to a point on the quadratic twist of the curve.

Therefore knowing only $x$, we know it corresponds to a point on the curve or its quadratic twist. The thing is that many standardized curves have a weak quadratic twist (see this page on SafeCurves so it is mandatory to check the point is on the curve, and if we use only the $x$-coordinate, we still need to check it is not on the quadratic twist to avoid invalid curve attacks.

Dan Bernstein designed X25519 as a Diffie-Hellman function using Curve25519 in its Montgomery form. On this curve, the Montgomery ladder scalar multiplication is efficient and uses only the $x$-coordinate of the points. Then, manipulated points lie on the curve or its quadratic twist which is as secure as the original curve. Then any $x$ is valid, but does not necessarily correspond to a point on the curve.


What is the purpose of multiple key addition layers in AES?

Suppose you remove the key addition layer. What happens then?

(Mouse over to see the answer. Try figuring out yourself first!)

   Denote AES without the key addition layer by $\operatorname{f}$. Suppose an adversary has $\operatorname{f}(x)$. They can recover $x$ by applying $\operatorname{f}^{-1}(x)$. If there is no secret information (the key), then anyone can perform the permutation/inverse permutation at will. You cannot have confidentiality without a secret decryption key.

Edit in response to modified question

If the key is only applied once, then given a ciphertext an adversary can apply the inverse permutation on the ciphertext until they end up with $m' \oplus k$. This allows them to recover $k$ via exclusive-or with $m'$, where $m'$ is the result of $f'(x)$ and $f'$ is the first steps of AES up to the key addition layer.


Ignoring the TAG of the AEAD-SIV encryption

Short answer: AEAD is completely the wrong tool for the job. You need a MAC, or perhaps a hash.
Here are two important facts about cryptography:

Details matter. You can't just take a good, secure construction and modify it and expect it to remain secure.
Cryptography is not limited to encryption.

from my side because i dont need to decrypt the ciphertext after encryption

If you don't decrypt, why would you encrypt? The whole point of encryption is that it can be decrypted if you have the key.
If you want to transform private identifiers into pseudonymous identifiers, a basic tool is a hash function. (More precisely, a cryptographic hash function: hash functions are also used outside cryptography. In a cryptographic context, "hash" means a cryptographic one.) Hash functions have the property that given y = H(x) but not x itself, the only way to recover $x$ is to guess it. This is probably not good enough in your case because anyone could just get a list of player IDs, or guess them, and calculate their hashes.
You can throw a secret key into the mix. With a MAC function M and a secret key k, given y = M(k, x) but not x or k, it's impossible to find x (or even to determine whether there is a valid x at all). Furthermore, given x and y but not k, it's still impossible to determine (or even make a good guess) whether y corresponds to this x. So you can use a MAC with a secret key, and only people with the secret key can associate player IDs with pseudonymous IDs in either direction.
Given the key k and a pseudonymous ID y, it's at the very least possible to guess x and verify whether M(k, x) = y. If you can't figure out x by guessing, it may still be possible to use the knowledge of k and y to get candidate x. Whether this is possible depends on the nature of the MAC. A popular class of MAC functions, HMAC, has the property that even with the key, it's impossible to find x other than by guessing, similar to the property of hash functions. (And for the same underlying reasons: HMAC leverages a hash function to build a MAC function.) HMAC is a good choice of MAC regardless of whether you care about this property.
Given your problem statement, I think HMAC matches your requirements. However, I am unsure whether your technical requirements match your expectations on privacy. I would recommend that you consult with an expert on privacy.

AEAD by definition creates a ciphertxt and a tag

Not necessarily. In general, AEAD encryption creates a ciphertext and decryption takes this ciphertext as input, plus the key, nonce and additional data, and either returns the plaintext or a decryption failure report. It is true for many AEAD mechanisms, including SIV, that the ciphertext can be broken up into a tag which is necessary to determine whether the ciphertext is authentic and a ciphertext-without-tag which is sufficient to recover the plaintext if the ciphertext is authentic. But this decomposition is not an intrinsic requirement of AEAD and is not a useful way to process AEAD functionally.

no one can decrypt the ciphertext except when providing the tag

This is wrong (for AEAD modes that do have a distinctive tag, which includes SIV and most others). Without the tag, it's still possible to decrypt the ciphertext, in the sense that it's possible to find the original plaintext. It's just not possible to determine whether the plaintext is authentic.

Does it decrease the level of security of the encryption if we do not store the tag?

Not as such. If you don't store a part of the ciphertext, it can reduce the security of authentication (you lose part of your ability to verify that the data is genuine), but not the security of encryption (erasing some information doesn't reduce the confidentiality of data).
However, not verifying the tag can reduce the security of the encryption – see next paragraph.

Also, In some cases am specifying a fixed padding in order to not have ciphertexts with different lengh. Does this process affect the level of security of the encryption?

Maybe: padding can allow padding oracle attacks. The gist of a padding oracle attack is that an attacker makes up some fake ciphertexts and asks you to decrypt them. You decrypt, and verify the padding. If the response reveals something about the validity of the padding, this can allow the attacker to decrypt arbitrary ciphertexts, or perhaps only ciphertexts in a certain format. This happens if there's some way to present part of the plaintext as padding, which there usually is since the point of padding is to be in the place where some plaintext would be if it was longer. The details depend on the nature of the padding and the encryption.
AEAD is invulnerable to padding oracle attacks because the attacker can't make up valid ciphertexts. (Also, most common AEAD modes don't have padding – but even if they did, the authentication would protect them.) That, of course, goes for AEAD used as such. If you take an AEAD construction and throw some parts out, all bets are off.

Is AEAD-SIV still considered a standard for deterministic encryption?

Yes, if you needed deterministic authenticated encryption, then SIV would be a good choice.


Will reading "Elementary Number Theory" by David M. Burton be useful for Cryptography?

It's better to study cryptography and refer to number theory (and other fields) when it's needed.

Nevertheless, Math is very important, if you want to be something better than 'press any key' cryptographer. Mostly, you will need Group Theory, Linear Algebra, Graph Theory, Automata Theory, Complexity, Number Theory, some bits of Functional/Mathematical analysis, a bit of Complex analysis, some knowledge about polynomials, and of course, Probability Theory.

Before obtaining a degree in Security I got Masters in Math and, looking back, it helped me a lot, compared to other students. And yes, your approach will be useful.


Why, or when, to use an Initialization Vector?

AES (as any block cipher) strifes to be indistinguishable from a random permutation, so any property like $C_1 \oplus C_2 = P_1 \oplus P_2$ would be quite bad.

This property (with $K$ as the "key stream bits") is valid for synchronous stream ciphers, including the one time pad and stream cipher modes of block ciphers (CTR, OFB, and for the first block also CFB), but not for those modes of operation who actually put the plaintext through the cipher, like CBC.

This is why you should never reuse the same key with the same initialization vector for stream ciphers (or reuse the same key at all for stream ciphers which don't have an initialization vector).

For CBC, the effect of such a misuse is just that identical plaintexts (or actually identical starting plaintext blocks) give identical ciphertexts (identical starting ciphertext blocks). This is still something one doesn't want, so you should use a fresh random IV for each message even for CBC mode.

If you can't do this, encrypting a random block before the real data has the same effect.

But we have a similar property if we take the initialization vector into account.

CBC mode works (for the first block) like this:

$$C = Enc_k(IV \oplus P)$$

So, if we don't fix the initialization vector, but chose it according to the plain text (or chose the plain text according to the IV), we can get two $(IV, P)$ pairs which will give the same ciphertext.

Or the other way around:
If we have two Pairs $(IV, P)$ and $(IV', P')$ such that $C = C'$, then we know that $IV \oplus P = IV' \oplus P'$. Written differently, $IV \oplus IV' = P \oplus P'$ and also $P = IV \oplus IV' \oplus P'$ (assuming $P$ was the original, unknown plaintext, and $(IV', P')$ were a later, crafted pair).

This is the basis of the BEAST chosen plaintext attack against CBC, when the next initialization vector is known before the attacker choses his plaintext block. (Note that this attack can be extended to all blocks, not just the first one.)

So make sure you create your random IV only after you did get (at least the first block of) the actual message to encrypt, if you are implementing an online encryption protocol like TLS. (With a random IV, the chance that the XOR with any plaintext block is the same as something encrypted before is neglible.)

The "one block CBC with zero initialization vector" version is the same as ECB, and has the same problems: identical plaintexts give identical ciphertexts. Normally you don't want this, as it is not semantically secure.


Rabin-Williams, blinding and size of Integer r?

Blinding is usually applied on the whole modulus, and I see no incentive to do otherwise; random is cheap.

In RSA, blinding is not always applied as described in the question and article, for efficiency and security reasons: the technique described requires computing $r^d\bmod N$, which is just as costly as the $m^d\bmod N$ operation being protected, and involves the private key, which could be a security issue. Rather, the archetypal (external) blinding goes:

draw random $r$;
compute $\hat r=r^e\bmod N$, the blinding factor (since $e$ is typically short compared to $d$, this is much less costly than computing $r^d\bmod N\;$; further, only the public key is involved in computing $r^e\bmod N$, therefore a successful side-channel attack here can't directly endanger the private key);
compute $\hat m=m\cdot \hat r\bmod N$, the blinded message (or signature);
compute $\hat c=\hat m^d\bmod N$, the blinded result;
compute $r'=r^{-1}\bmod N$, the unblinding factor;
compute $c=\hat c\cdot r'\bmod N$, the result.

If $r$ was reduced from the width of $N$ to say $256$-bit:

it would be proportionally less trouble to generate, but that's almost a non-issue in modern security environments, where random is relatively cheap (precisely to enable blinding and masking techniques);
there would be a problem with very small $e$ like $3$, where $\hat r$ would not have all its bits random; we'd have at least a worry making a convincing argument that this is not a problem w.r.t. power analysis and timing attacks;
when there's not this problem, the saving in step 2 would be marginal at best; in any case, step 4 dominates all the others for common $e$ like $e\le2^{16}+1$, or even random $e$ as sometime practiced (typically $e<2^{(2^k)}$ with $k\in\{5,6,7,8\}$; see footnote for unusually large $e$);
we'd save in step 5, significantly relative to step 5, but overall negligibly;
we'd have at least a worry making a convincing argument that $r'$ is unpredictable enough for our blinding purposes.

So all in all there's no appreciable saving reducing the width of $r$, it can only make attacks even so slightly easier, so why bother?

Footnote following comment: computing $r^d\bmod N$ for narrow $r$, rather than wide $r$, can indeed make a difference (like a saving of $1/3$ on this operation) if we use left-to-right scanning of the binary expression of the exponent; because then, while computing $r^d\bmod N$, about one in three modular multiplications is by $r$ (other faster modular exponentiation techniques do not allow so much saving). If we indeed use this exponentiation method and compute $r^d\bmod N$ (or compute $r^e\bmod N$ for unusually large $e$), narrow $r$ would be a saving worth consideration, saving up to about $1/6$ of the overall execution time for large size of $N$, and I do not immediately see that it would cause a security issue.


Where to apply Montgomery Multiplication in GF(2^n)

The usual motivation for using Montgomery multiplication is that it significantly reduces the cost of modular reduction by changing the representation of elements. In the Montgomery ring the polynomial $A(x)$ is instead represented by $a(x)=A(x)r(x)\pmod{n(x)}$ where $r(x)$ is a fixed element of the same degree as $n(x)$, but for which division is very efficient (e.g. $x^k$). If likewise we have $B(x)$ represented by $b(x)=B(x)r(x)$ then $a(x)b(x)r^{-1}(x)\equiv A(x)B(x)r(x)\pmod{n(x)}$ which is the representation that we would choose for $A(x)B(x)$ and so your algorithm is way of implementing modular multiplication of polynomials in this representation without having to do a modular reduction. Addition and subtraction do not need new algorithms. If you have an algorithm involving many modular multiplies, it can be worthwhile converting to Montgomery ring representation, using Montgomery arithmetic and then converting back.
To convert $a(x)$ back to $A(x)$ we need to multiply by $r^{-1}(x)$, so it can be useful to precompute and save $r^{-1}(x)\pmod{n(x)}$. I don't know of any way to avoid modular reduction in this final conversion.
Evaluating using the Montgomery representation is possible, but requires a little extra work: to evaluate $A(x)\pmod{n(x)}$ given its representation $a(x)$ we have to evaluate $a(x)\pmod{n(x)}$ and $r^{-1}(x)\pmod{n(x)}$ and multiply the two answers together. However, if many evaluations are needed for the same input $m$, the value $r^{-1}(m)$ can be reused and the overhead is not as great.


Does many:1 mean two different inputs would have the same hash outputs?

Yes. This is a consequence of the pidgeonhole principle: as MD5 has a much larger number of potential inputs ($2^{2^{64}}$ or so) than outputs ($2^{128}$), some inputs must lead to the same output, i.e. collide.

Cryptographic hashes all have this "limitation", because they have a constant output size and allow much larger inputs. However, with good cryptographic hashes (MD5 is very broken in this sense), you have no way of finding those collisions. This is called collision resistance and is one of the properties we require of hashes.


Is there a symmetric cipher that is explicitly designed to be slow?

A memory hard PBKDF (or password hash, same thing, different name) without memory hardness is basically just a repetition of a hash or cipher.  In that case you might was well be the repeated application of a block cipher (with an alterated key if needed) or - indeed - increase the number of rounds.

The issue with increasing the number of rounds is that you also need to extend the key schedule. But since you're not trying to achieve more security, you could simply repeat previously calculated keys (if the key schedule itself cannot be easily extended).

Note that bcrypt is a password hash that uses a block cipher rather than a hash function. You could check if that suits your needs.


What is the best mode of operation for file encryption with Threefish512?

You should use an authenticated encryption mode.

My personal current favorite is SIV mode, originally introduced by Rogaway & Shrimpton (2006) and standardized (for use with AES) in RFC 5297.

The major advantage of modes based on the SIV construction (such as SIV mode itself, as well as e.g. GCM-SIV) is that, unlike most other encryption modes, their security will not fail catastrophically even if the nonce/IV is accidentally reused.  This eliminates one of the few remaining "weak points" of modern authenticated encryption modes.  CBC mode also has this property to a limited extent, which I believe is the main reason why Schneier's book recommends it, but SIV is much better in that regard, and, as an authenticated encryption mode, also resistant to a much wider range of attacks.

The main disadvantage of SIV mode is that it's a two-pass mode: encryption requires first computing a MAC over the plaintext, and then using that MAC output as a "synthetic IV" to encrypt the data.  If you want to encrypt large files, you may wish to use a "chunked SIV" mode.  There is, as far as I know, (unfortunately) no standard for that, but the basic idea is to:

Split your file into chunks of, say, 1 MB.
Encrypt each chunk using SIV mode, and concatenate the resulting ciphertexts.
For each chunk, include any relevant parameters such as the total size of the file, the chunk size used, the number of the current chunk and, importantly, the "synthetic IV" of the previous chunk as associated data.  (At a minimum, if you don't know the size of the file in advance, each chunk should have as associated data its number, the previous chunk's synthetic IV and a flag indicating whether or not this is the last chunk.)

This "SIV chaining" should ensure that, if every chunk of the encrypted file can be successfully decrypted, this not only guarantees the integrity of the individual chunks, but also of the entire file (i.e. that no chunks have been added, removed or switched around).


Smallest 256-bit security hash-based OTS?

I will just assume you mean 256-bit classical security as 256-bit post-quantum would be ridiculous. Then it would most likely be WOTS+ in the multi-target secure version described in this paper. The signature size depends on the value you choose for the Winternitz parameter $w$. For $w=16$ a signature contains 67 hash values (each of which should be 256bits in your case). As public key you can take the hash of all the chain ends (and the public seed) as done in the SPHINCS+ specification. Then your public key is two hashes (512 bit in your case). Key generation in this case costs ~67*16 short hashes and one hash over 67 hash values. Sign and verify for a given message add up to key generation time, i.e., they are both strictly upper bounded by these 67*16 + 1 hashes.

In theory, there is another scheme bei Bleichenbacher and Maurer which is slightly more efficient but according to current knowledge requires collision resistance and hence needs a bigger hash function output length.


Need help with NFC Tags and cryptography

Preliminary caveat: the un-clonability of your NFC tags is relative. A mobile phone with NFC is all it takes to read one, perhaps surreptitiously. Then a number of devices like proxmark3 can emulate it. A static digital signature would not prevent that.

  Can I use a digital signature in order to tell if a given NFC-Tag belongs to my devices and if the parameters haven't been changed by an evil user?

No, a digital signature can't authenticate the data in that size-constrained tag: more memory is required that the tag allows.

All digital signatures schemes add at the very least $2b$-bit of data for $b$-bit security, so for 80-bit security (which is NOT safe enough by modern standards) we are talking 20 bytes, more than the question quotes. And that's for some BLS signature schemes pushing things to the max, which (although reportedly used with great success) have not their security strongly vetted. The industry standard is $b=128$-bit security with $4b$-bit signature, thus 64 bytes (e.g. Ed25519). I know nothing well-seasoned below $3b$-bit overhead for small signed data, or $2b$-bit for larger data (above about 220 bytes).

  I'm using an 8-bit microcontroller with very limited resources on the NFC-Reader side for the verification process. Therefore the verification step should be as easy as possible (signing the tags can be done on a powerful PC). Which Algorithm would you use for this application?

Among common signature schemes, only RSA and Rabin signature have fast verification (seconds) on 8-bit microcontrollers, but unfortunately their minimal data requirement is like 2048-bit (256 bytes) for modern security. Thus you'd need 256 bytes of memory in the tag for the signature (in addition to the UUID; the rest may come for free, see below).

With RSA/Rabin per ISO/IEC 9796-2 using SHA-256, it is possible to embed payload data into the signature (e.g. up to 222 bytes for 256-byte signature), and this payload becomes available as a byproduct of signature verification, which is fast. That's RSA/Rabin signature with message recovery. It essentially achieves $2b$-bit size overhead for $b$-bit security, for a payload at least a certain size.

All common signature schemes requiring less memory are considerably slower for signature verification, in the order of a minute for 128-bit security given the low-end CPU.

Feasible options include (not exclusive, not limitative)

Using a Message Authentication Code rather than a digital signature. That solves the size and speed issues (8 bytes and a tenth of second is ample), but unfortunately a verification device contains the secret key that also allows to compute a MAC that makes a tag working. If an adversary can get hold of a verification device, these might need to be tamper-proof, thus slightly more expensive. And it can't be entirely ruled out that a verification device is successfully attacked and its secret key extracted (though that can be made extremely hard, even certified so).
Going online: the UUID can be used as index in a server, knowing if the tag is registered or not. The server can digitally sign that it vets the tag with that UUID as OK, and it can use a system with lightweight signature verification. That has the advantage of allowing a dynamic black/whitelist.


It is easy to find preimages for the hash function you designed. Remember, to break the scheme it is enough to find any preimage. It is not necessary to find the one used to compute the image. Now, you got public integers $a,b,c,d,$ and $f,g$ as well as a modulo $M$. An $n$-th image is
$$P(n) = a*x(n) + c*y(n) \mod M$$
$$Q(n) = b*x(n) + d*y(n) \mod M$$
with
$$x(n)= (f * P(n-1) ) + n$$
$$y(n)= (g * Q(n-1) ) + 1$$
hence
$$P(n) = afP(n-1) + an + cgQ(n-1) + c \mod M$$
$$Q(n) = bfP(n-1) + bn + dgQ(n-1) + d \mod M$$
leading
$$P(n) - an - c = afP(n-1) + cgQ(n-1) \mod M$$
$$Q(n) - bn - d = bfP(n-1) + dgQ(n-1) \mod M.$$
Lets rename to get some more readability. For an attacker knowing an image $y_1 = P(n) - an - c \in\mathbb{Z}_M$, $y_2 = Q(n) - bn - d \in\mathbb{Z}_M$, $a_{1,1}=af$, $a_{1,2}=cg$, $a_{2,1}=bf$, $a_{2,2}=dg$ are all known integers mod $M$. The two unknowns are the primage parts $x_1 = P(n-1)$, $x_2 = Q(n-1)$. Rewriting the system gives
$$a_{1,1}x_1 + a_{1,2}x_2 = y_1 \mod M$$
$$a_{2,1}x_1 + a_{2,2}x_2 = y_2 \mod M.$$
I guess from here on you know yourself how to determine $x_1, x_2$. This is one more example why you should not try to cook up something yourself when it comes to crypto.


How is it possible that these two encryption functions yield the same result?

This is a problem created by the library. Either the HMAC algorithm is skipped entirely, or - more likely - the HMAC authentication tag is generated and then forgotten. The reason is likely the spotty to non-existent handing of authenticated ciphers in the OpenSSL command line and (likely) higher-level functions. The string is recognized by the cipher classes, but the authentication tag output is simply ignored.
The output is 64 Base64 characters without padding chars, corresponding to a $(64 / 4) * 3 = 48$ ciphertext in binary. The plaintext is 43 characters/bytes. There is no way that the ciphertext includes the authentication tag of 32 bytes (256 bits, the output size of SHA-256). No, the plaintext is just padded with an additional 5 bytes using PKCS#7 compatible padding and then encrypted... and that's it.
So sorry, no crypto magic happening here, just a bad implementation of a cryptographic library. To any OpenSSL devs out there: this should not be that hard to fix, right? Just whitelist the strings that you have tested, please.


To simplify your definition:

$$
s = \operatorname{sign}(k, m) = h(G\ h(m)\ k)\\
\operatorname{verify}(Gk, m, s)\iff s \overset{?}{=} h(Gk\ h(m))
$$

This is obviously insecure because I can forge "signatures"!

$$s' = \operatorname{forge}(Gk, m') = h(Gk\ h(m'))$$

ECDH is not a signature scheme. Schnorr is amazing and is much more interesting than ECDSA! Including but not limited to: threshold k-of-n distributed identities, n-of-n multisig aggregation, batch verification, public key recovery, implicit certificates, and much more!


What are the requirements of a key schedule?

Desirable Properties

There are a few papers and resources related to key schedule design out there.

From this paper from 2012  we can highlight some of the following points:

Key bits should be uniformly used
All subkeys should be "equally good"
It is "hard" to find any remaining key bits from any known key bits.
Hard to invert
If possible  every  key  bit  should  affect  nearly  every  round  in  different  ways
No equivalent keys
Collision-freedom (standard hash function properties)
No dead spots
Equally powerful effect of every key bit on the subkeys.
Low implementation cost
Minimal mutual information between  all  subkey  bits  and  master  key  bits

Which the paper then basically summarizes with:

  First, key schedules should have no bit leakage in the level
  of "round", or of the whole key schedule. The former means they only consider
  leakage between different rounds of subkeys, or between some rounds of subkeys
  and master keys. When an recursive key schedule is invertible or when subkeys
  are  direct  transformation  from  master  key,  above  leakage  cannot  be  avoided.
  The latter means that no subkey bits can be derived easily whatever key knowledge is obtained

They then go on to define terms and techniques which are more in depth in relation to cryptanalysis of key schedules.

This paper appears to build on the work of the previous one, but I cannot access it.[1]

This paper concludes mostly the same things:

Maximize  avalanche  in  the  subkeys  and  avoid  linear
key  schedules.

Though the authors note: "As an open question, we note that the DES key schedule is linear,
and wonder why it appears to resist related-key attacks"

Every key bit should affect nearly every round, if possible, but
not in exactly the same way
The key schedule should be designed to resist
differential  attacks.

Key Schedule Classification

This last paper had some different material that is also interesting. They classify the key schedules of algorithms into two types, with subclasses of those types. The types are defined by whether or not knowledge of round key bits reveals knowledge of any other round key bits, or the master key.

A Type 1 key schedule allows recovery of other round key/master key information if some round key information is known
A type 2 key schedule does not allow recovery of other round key/master key information if some round key information is known

They further go on to define sub types, A, B, and C.

A Category 1, Type A cipher (1A) is one in which all bits of the master key are used in each round, and hence knowledge of a round subkey yields all bits of the master key and all other round subkeys. The cipher NDS [3] is such an example.
A 1B cipher is one where knowledge of a round subkey gives some, but not all bits of the master key or other round subkeys. DES is an example.
A 1C cipher is one in which knowledge of a round subkey yields bits of other round subkeys or the master key after some simple arithmetic operations or function inversions. SAFER K-64 [6 ] is an example.
A 2A cipher is one in which not all bits of the master key are used to create each round subkey . In these ciphers, certain master keys are guaranteed to produce at least two identical round keys. A cipher such as CAST-128 [7] is an example. In other words, the entropy of the round subkeys is not maximised.
A 2B cipher is one in which all master key bits are used in the determination of all round subkeys, thus maximising the entropy of the subkeys. An example is Blowfish [8].
The most secure schedule classification is 2C. However, this may lead to unmanageably large master keys for ciphers whose security cannot hope to match what is naively suggested by the key length. Further, export restrictions on cryptographic materials often limit the size of the key. For these reasons, the best we can hope for is to mimic 2C schedules as closely as possible, with the next strongest classification, 2B.

Efficiency with embedded devices

While one way functions are recommended as part of a key schedule, there is a downside if they are used a certain way. If only noninvertible functions are used in deriving round keys, then decryption will require the algorithm to generate all its key material at the beginning. On a general purpose computer this is not really a concern, however, on embedded devices with limited gate counts/surface areas, the excess storage can become problematic. The storage requirement will increase by the round key size per round. This will lead to a higher unit cost.

The best solution I am aware of is to split the key schedule into two parts, an invertible part, and an uninvertible part. The invertible part is used to generate round key material in a way that is friendly to on the fly processing, while the uninvertible part of applied just before usage of the round key. This maintains the best of both worlds, in that embedded devices can decrypt with an on-the-fly key schedule and the cipher can have the protection a non invertible key schedule offers. This is potentially a small change that will improve the applicability of the cipher towards smartcards and the like.

[1] Free version added.


Is HMAC-MD5 collision-resistant if the key is unknown?

Yes, HMAC-MD5 with the key secret is still considered practically secure against all attacks, including collisions. We are about in the situation considered in Mihir Bellare's New Proofs for NMAC and HMAC: Security without Collision-Resistance (extended abstract in proceedings of Crytpto 2006).

But as the saying attributed to the NSA goes: attacks only get better; they never get worse.


Is only one shared secret generated by ECDH per key pair?

It sounds like you are thinking of performing static-static Diffie-Hellman. If that is performed naively then it will indeed derive the same secret time and time again. At least one of the key pairs needs to be non-static or ephemeral, or an additional variable (nonce) should be introduced.

For instance in NIST SP 800-56A there is section 6.2.1: "Initiator Has a Static Key Pair and Generates an Ephemeral Key Pair; Responder Has a Static Key Pair, C(1, 2)" for the former and section 6.3: "6.3 Scheme Using No Ephemeral Key Pairs, C(0, 2)" for the latter.

Usually however both key pairs are ephemeral and DH is mainly used for key agreement, relying on another primitive (such as ECDSA or RSA signatures) to add the authentication. If one of the key pairs is newly generated then the resulting keys should be indistinguishable from random (especially if the secret is put through a Key Derivation Function or KDF).

So yes, you have this right, but only for a naive implementation with two static key pairs. The underlying techniques explained above are valid for both Diffie-Hellman (DH) as for Elliptic Curve Diffie-Hellman (ECDH).


What is the simplest post-quantum asymmetric cryptographic algorithm for key exchange?

There is only one paper I know of which explains a post-quantum key exchange algorithm in such a way that a beginner could understand it, and that is for SIDH (Supersingular Isogeny Diffie-Hellman key exchange). The paper is called Supersingular isogeny key exchange for beginners.

Abstract. This is an informal tutorial on the supersingular isogeny Diffie-Hellman protocol aimed at non-isogenists.

If you don't care whether or not it is actually usable, then there's pqRSA which is essentially just regular RSA with (completely impractical) parameters that make it post-quantum secure.


How to determine the next number from java's Random method

In Java, if you do not seed the Random object, then it will seed itself. According to that same documentation, it uses a "linear congruential PRNG"...

This means it will easily be cracked if you have two values.

Such a PRNG will have an "internal state", which will change after each generation of a "random" number by applying the following linear process:

$$X_{n+1} = \left( a X_n + c \right)~~\bmod~~m$$
where we call $X_n$ the state at the step $n$, $a$ is the "multiplier", $c$ is the "increment" and $m$ is the "modulus".

Now, Wikipedia tells us that Java is using 25214903917 as multiplier and 11 as an increment and has a modulus equal to $2^{48}$.

Finally you need to know that java.util.Random won't spit all of its internal state into your random numbers: 32 bits only of the internal state are revealed by a call to nextInt().

So, we just one value, it would be hard, but since you have 2 different values, you can easily bruteforce the seed used and thus find the next value by calling nextInt with that seed.

Here is a snippet of code, which produces the correct result (I believe... This is only my fourth time trying out Java), I didn't felt like bruteforcing the bitwise AND operation to reverse it to the actual initial state, I let this as an exercise to a motivated fellow:

import java.util.Random;

public class lol {
    // implemented after https://docs.oracle.com/javase/7/docs/api/java/util/Random.html
    public static int next(long seed) {
        int bits=32;
        long seed2 = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
        return (int)(seed2 >>> (48 - bits));
    }

    public static void main(String[] args) {
        System.out.println("Starting");
        long i1 = -1952542633L;
        long i2 = -284611532L;
        long seed =0;
        for (int i = 0; i < 65536; i++) {
            seed = i1 *65536 + i;
            if (next(seed) == i2) {
                System.out.println("Seed found: " + seed);
               break;
            }
        }
        Random random = new Random((seed ^ 0x5DEECE66DL) & ((1L << 48) - 1));
        int o1 = random.nextInt();
        int o2 = random.nextInt();
        System.out.println("So we have that nextInt is: "+o1+" and the third one is: "+o2+" with seed: "+seed);

    }
}

Which produces the following output:

Starting
Seed found: -127961833934689
So we have that nextInt is: -284611532 and the third one is: -1527300283 with seed: -127961833934689

And so I think your third integer would be $-1527300283$.


Unfortunately, most of the reasons that e-voting is not popular have  nothing to do with the integrity of the underlying mathematics.  This makes the question slight moot on a cryptography forum, but the following un-cryptographic answer still entirely relevant.  Unless you solve the following (non exhaustive) problems:-

It's a  requirement of law enforcement (and thus oddly necessary for the protection of democracy) that you have to be able to check how people voted. Just proving that someone voted once is insufficient. Zero knowledge by definition can't be evidence in a proceeding.
Ella points out the conundrum that if point 1 is satisfied and voter behaviours can be verified, it can encourage more vote fraud by people selling their votes which can then be machine verified as bought by the orchestrator. Could this lead to an alt-Trustpilot system emerging of "quality" voters ranked by cost and reliability?
You also have to be able to prove who hasn't voted so that they can be prosecuted in certain jurisdictions /Australia. This is probably easier to solve than point 1, but clearly the issue of tokens does not guarantee a cast ballot. But such proof gets complicated again if run in parallel with traditional paper schemes.
Your requirement for ID is a H U G E problem.  25% of African-American voting-age citizens lack a US issued photo ID. My mum and dad don't have any either. Ginswich points out that several of these points share the common theme of  voter identification /authentication. This speaks to the broader issue of whether we want a society where everyone must carry "papers".
Can I spoil my vote?  I reserve the right to draw a squirrel on my voting slip or have an option for non of the above.  This must be the easiest to solve with the addition of a dummy candidate.
The bad guys will just hack the phones. So the Merkle tree remains intact collating the votes, it's just that you can set the app to vote for Hillary all the time whilst swearing to you that it registered a vote for the other one. Or play a tune instead on the central collation point.
What are these apps you mention?  I'm blind so I can't easily use a phone and therefore automatically technologically disenfranchised.  Although progress on accessibility is being made, how would the blind and /or deaf interact with a QR code?
And if I don't have a phone (my granny doesn't) can I borrow someone else's to vote with legally? Can multiple vote tokens be issued to the same device if sharing?
My daughter has three phones.
What is the relationship between the contents of the Merkle tree and any cast/spoiled paper ballots, or do you plan to go 100% paperless? That would be quite a societal change.

Before the deluge of up votes, please consider that some cryptography is fine academically on a black board, but it often has to operate in the real political and social world.  A broader view has to be taken of cryptography and it's role in   society.

Update:

Regarding voter anonymity in parts #1 and #3, and comments. The following is the back of the current UK Parliamentary Election ballot paper. You may spot the unique bar and QR codes. The bar code is over 70mm long so it's not really a secret.   It's not a problem as long as the voting remains paper based.


Are there any cryptographic flaws in my webhook signing process?

I do not recommend inventing your own protocol for this.

Instead, I recommend using TLS client certificates.  They solve exactly your problem, and solve it well.  The TLS folks thought a lot about the security challenges involved in designing such a protocol, so you wouldn't have to.

You mention that you perceive the complexity of client certificates to be significant.  My sense is that the complexity of rolling your own is actually higher than just using an existing TLS library's support for client certs; and the chances of making a subtle security mistake are significantly higher when rolling your own.   Therefore, I do not recommend the direction you are taking of trying to design your own protocol: I recommend using a well-vetted existing mechanism (like TLS client certs) whenever you possibly can.


What cryptographic protocol or algorithm I can use to encrypt/decrypt a subset of columns of a database table for each user?

A solution using attribute-based encryption

You could solve the problem you pose relatively elegant using attribute-based encryption (ABE; cf. [1]). For example, using a ciphertext-policy ABE you could do the following. Let {col1, col2, ..., col50} be the universe of attributes and, for each user, assign a key with respect to the attributes she is allowed to access. To take your example user1 would get a key with respect to {col15, col17}. Each column is then encrypted with respect to its column attribute so that every user who is in possession of a key with the respective attribute can decrypt the column.

An alternative solution

Since it seems that the number of columns you want to encrypt is rather small you could also use an alternative approach known as hybrid encryption: you choose a symmetric encryption scheme and encrypt each column under a separate key. Additionally you use an asymmetric encryption scheme which is used to encrypt the respective symmetric keys for the users who have access to a certain column. Let $k_1, \dots, k_{50}$ be the symmetric keys used to encrypt column 1 to column 50, then - again taking your example - you would encrypt $k_{15}$ and $k_{17}$ under the public encryption key for the asymmetric encryption scheme of user 1.

Scalability requirements

Since the number of columns is relatively small (< 1000), I think that both solutions above should perform well. Note that for the second solution the size of the ciphertexts which are handed to the users are of linear size in the number of columns. Using the ABE approach you will be able to get constant size ciphertexts (depending on the used ABE), but this will come at the cost of more expensive encryption and decryption. So choosing one of those two approaches can be viewed as choosing a trade off between ciphertext size and efficiency.

References

[1] What is Attribute Based Encryption?


what is the difference between IBE and ABE schemes

With IBE the public key is a public bitstring as your email. A Key-authority issues a secret key that is tied with this public key.The owner of the secret key can only decrypt.

ABE entails more complex access control on decryption operation such as:"Only the owner of the secret key that corresponds to: Area:=Italy AND Age:<30 and Business:=Researcher" can decrypt. The last predicates are called the attributes


Rephrasing fkraiem's comment as an answer:

  Hint:   $$a^{2x}=(a^x)^2$$

which also holds $\bmod p$.


Is an android encrypted SDcard readable/decryptable easily by a desktop machine?

The Android developers page on Full Disk Encryption seems like it has all the info you want, and more! It talks about encryption on the main internal disk (/data), I will assume that it uses the same mechanism for encrypting the external SD Card.

In a nutshell:

When your turn Android Disk Encryption on, it generates an AES-128 key which it uses to encrypt the drive (called the master key). It then takes your Pattern / PIN / Password and uses that to derive a second AES-128 key which it uses to encrypt and store the master key on disk. You know how the first thing Android does during boot-up is ask for your PIN / Password? That's because it needs it to decrypt the master key so that it can decrypt and mount the main filesystem. The reason for having two AES-128 keys is that if you change your Pattern / PIN / Password, it just has to re-encrypt the master key file, not the whole disk.

Is it decryptable on a desktop?

Theoretically, yes.

The location of the master key file is no secret, so if you know the PIN / Password, and you know which key stretching function Android uses to turn this into an AES-128 key then you should be able to decrypt the master key, and then dercrypt the disk. Whether there is freely-available desktop software to do this, or you would have to write your own, I have no idea.

(One possible hitch is that I don't know if it stores a copy of the master key file on the external SD Card, or if there is just one copy on the internal flash memory chip. Finding a way to access the internal flash memory on the dead phone might prove to be the hard part here. You could probably check pretty easily if there's a key file on the encrypted SD Card by popping it into your laptop and looking.)


How would you explain stateful encryption?

Stateful encryption aims at reducing the number and/or volume of data exchanges and/or computational burden in recurrent communications between entities, compared to what would occur if, at the beginning of each communication chunk, everything was redone as for the first chunk. This is obtained by sharing some data, called the state, from chunk to chunk. Depending on context, "chunk" can be a block of information of some small fixed size, a packet, a session for some communication protocol like TCP/IP or HTTP...

Perhaps the simplest stateful encryption is CBC encryption with a block cipher $E$ (though that predates the term stateful encryption, which is not used for CBC). The stateless version of CBC would, for each plaintext block $P_i$, draw a random $\text{IV}_i$ and send cryptogram $(\text{IV}_i,C_i=E(\text{IV}_i\oplus P_i))$; this is secure from a confidentiality standpoint, but overall cause the ciphertext to be twice the size of the plaintext. While CBC encryption draws a single random $\text{IV}$, sends $(\text{IV},C_0=E(\text{IV}\oplus P_0))$ for the first packet, and $(C_i=E(C_{i-1}\oplus P_i))$ for all the next ones, thus reducing communication overhead to a single block. Here chunk is a block, and the state is simply the last block encrypted, initially $\text{IV}$.

The term stateful encryption has been used for similar techniques to reduce the overhead in direct encryption with asymmetric ciphers like ElGamal; but practice is to use hybrid encryption instead, since that's much more efficient computationally.

Transport Layer Security Session Resumption is a practically used form of stateful encryption. As an utter oversimplification of that, when resuming a TLS connection that got broken for some reason, one side proposes to reuse the previous session key, and if the other agrees, that saves the authenticated Diffie-Helmann key exchange (or similar) for the negotiation of that session key.


Multi Authority Attribute Based Encryption Library

Charm crypto, a Python framework, contains three multi-authority schemes. Two of them were contributed by me: 1 & 2 and another one was already included.

Yannis Rouselakis also has a MA-ABE implementation in Charm on his site.


Why does OpenSSL differentiate between PSS and non-PSS for private key generation?

If you reuse the same key material for different algorithms, you rely not on the security of any one algorithm individually, but on the security of the composition of the two algorithms simultaneously.

For a particularly egregious example, if you use the same RSA public key for RSASSA-PKCS1-v1_5 and for HMAC-SHA256, the results might be entertaining.

It may turn out that while we have high confidence in the security of RSASSA-PSS assuming the RSA problem is hard, and reasonable confidence in the security of RSASSA-PKCS1-v1_5 because after decades nobody's made progress on it, the combination of the two with the same key material could have catastrophic results.

The theory behind these tags is presumably that associating such metadata with the key may serve to reduce the danger of accidentally reusing the same key material for different cryptosystems.


Basic encryption question: Why does 128/256 bit encryption have set length keys?

The first  thing that you really need to understand is that cryptographic keys are not the same thing as passwords.  Many newcomers to cryptography are familiar with passwords, and identify keys as an analogous concept—which it is, but the differences are very important:

Passwords are generally chosen by humans; cryptographic keys are randomly generated with a good source of randomness (dice are good, brains are not);
Passwords are generally memorized by humans; but no strong cryptographic key can be memorable.  Keys are instead stored in secure hardware.
Passwords are text that humans can read and type easily; keys are binary data and not generally printable in their raw form.  You need to format them as hexadecimal, Base64 or similar for display.  (Actually, you really shouldn't display them at all, since they're not memorable anyway!)

If your AES key is something like PASSWORDPASSWORD (which I've actually seen ), somebody has likely made a terrible mistake.  A 128-bit key should be 128 randomly chosen bits!

With that out of the way, now we can say: practical cryptographic systems are built by assembling together well-studied primitives (e.g., AES, SHA-2, RSA, etc.), into complete protocols (e.g., SSL, SSH, OpenPGP) for achieving the users' goals.  And given this sort of architecture:

Fixed key sizes generally make the primitive simpler to design, implement and evaluate.
If arbitrary-length key sizes are needed, this can generally be accomplished at the protocol level.  For example, the AES-CMAC-PRF-128 function is based on AES-128 but uses variable-length keys.  So part of the function's definition is a method for converting the arbitrary-length key into an AES-128 key.
There's no earth-shattering advantage to supporting arbitrary-length keys, so most protocols don't bother with it.
For cryptographic systems that work with passwords, there's an area known as password-based cryptography—cryptographic constructions and protocols for generating cryptographic keys out of human-supplied passwords.  A protocol for encrypting files based on user-supplied passwords works this way—it uses a password-based key derivation function like PBKDF2 to convert the password to a key, and then uses that key to encrypt and decrypt files.  So this is another example of cryptographic modularity—the primitives support only fixed-size keys, but their combination supports arbitrary-length passwords.


Short answer: just truncate, it's fine.

Long answer: you want a Key Derivation Function. A KDF turns an arbitrary-sized input (the shared secret obtained from SRP) into a configurable sequence of bytes, which you can split into as many sub-sequences as you need for symmetric cryptography. For instance, SSL/TLS defines a KDF (it calls it "PRF"; see section 5) so that it can extend the "master secret" (the shared secret obtained from whatever key exchange mechanism has been used) into six elements (an encryption key, a MAC key, and an IV, for each tunnel direction).

If you have a "reasonable" hash function such as SHA-256, and your secret data needs an amount of at most the hash output length, then a simple truncation will be an appropriate KDF. (Theoretically, being a good KDF after truncation is not implied by the hash function being appropriately resistant to collisions and preimages, but in practice you will not get any trouble with SHA-256 or SHA-512.)


Hash for use in embedded HMAC application

As cheaper alternatives to HMAC with modest security goals, consider:

SipHash—cheaper than MD5 because you don't have to pay for collision resistance; security is limited by the 64-bit output size
Maybe a Gimli-based PRF—Gimli is a new compact design
Derive a fresh key for each message, and use a one-time authenticator like a polynomial evaluation universal hash family such as Poly1305 or GHASH—extremely cheap to evaluate
Conceal a universal hash family output with a short-input, short-output PRF—faster than evaluating a generic long-input PRF

Of course, whether these actually provide security for your application depends on a lot more than the formal unforgeability properties of the cryptography.  No cryptography can prevent physical interference with the GNSS signals, for example!  With all of these systems, anyone who can verify log messages can also forge them—to separate the ability to verify from the ability to forge, you need public-key signatures, which are tremendously costlier.

To be clear: I don't suggest that you go out and invent new compositions of primitives right now along the lines I sketched above.  Rather, I suggest you spend effort now articulating your security model, so that you can focus your effort on implementing a design that confidently provides the security you're hoping for, rather than spend weeks micro-optimizing Poly1305 and SipHash for your AVR microcontroller, only to find that you actually need signatures, not authenticators.


Does SpongeWrap (from the Keccak team) absorb ciphertext or plaintext?

The authenticated encryption mode devised by the Keccak team is the SpongeWrap method, and is first described in this paper — the paper you cite is an amalgamation of all their major sponge papers. The encryption method wrap is described in Algorithm 3, on page 10. In particular, lines 14–18 absorb-squeeze with respect to the ciphertext.

In practice it is probably simpler to think of it in the following way:

To implement this in terms of absorbing and squeezing, we have to use the squeezed output from the previous iteration (here called $s_r$, called $z$ in their algorithm) and xor this with the message, before absorbing in the message as part of the next call. In my mind absorbing / squeezing is a much less clear way of describing the process, but mathematically it is important since it clearly shows the object to be an instance of a Duplex Object, which is itself a series of sponges, and thus allows us to use their security proofs.

I do not know of any test vectors for SpongeWrap.


If a private key decrypts what its public key encrypts, can the public key conversely decrypt what its private key encrypts?

You are right if you feel that this is nonsense; it is, fundamentally, a category error.  However, it is an unfortunately popular confusion of ideas that public-key signature is ‘just encryption with the private key’.

There is a tempting grain of truth to this notion—deep in the underbelly of the mathematics of one family of cryptosystems, with no practical consequences whatsoever, and not only is it completely useless to a practitioner but it is likely to get you into deep trouble if you try to act on this idea in any meaningful way.

Here's the tempting grain of truth.  RSA-based encryption schemes and signature schemes involve computing $e^{\mathit{th}}$ powers modulo a large composite $n$ with large prime factors as part of the public operation (encrypting, verifying), and computing $e^{\mathit{th}}$ roots modulo $n$ for the private operation (signing, decrypting).  And there the resemblance ends—there is no resemblance in the rest of the details of how you actually build encryption and signature of messages out of this.

Not only does the resemblance end there, but this tempting grain of truth is limited to RSA-based cryptosystems—while most of the world today has moved on to elliptic-curve cryptography for almost all new applications, in which signature and encryption schemes are completely different, and is preparing in the NIST PQCRYPTO competition to adopt a new lattice- or isogeny- or hash- or MQV- or somethingcrazy-based cryptosystem that will resist all current known methods of quantum cryptanalysis.


What are the correct order of operations for One Time Pad Cipher?

There is no difference.  In fact, any quasigroup operation will do.

Specifically, the only property we really need is that, for every ciphertext symbol $C$ and every plaintext symbol $P$, there exists one (and only one) key symbol $K$ such that encrypting $P$ with $K$ yields $C$.  This implies that, as long as the actual key symbols are chosen uniformly at random (so that each of them is equally likely to be correct), knowing the ciphertext symbol $C$ does not reveal any information about the plaintext symbol $P$ (since each $K$, and therefore each $P$, is equally likely).

In fact, we can generalize further and allow several key symbols to produce the same encryption, as long as the number of key symbols that yield $C$ is the same for every plaintext symbol $P$.

There are several common operations that can satisfy this property.  For example, we can use modular addition for encryption, and modular subtraction for decryption, or vice versa.  Or we could use e.g. bitwise XOR, which is its own inverse, and can thus be used for both encryption and decryption in the same system.  Or, if we wanted, we could use e.g. multiplication in a Galois field for encryption, and multiplication by the group inverse for decryption (or, again, vice versa).


Does encrypting twice using the same block cipher produce a security weakness?

Well, I don't know where you read that.  However, depending on what they meant by that, that's either nonsense, or an appropriate cautionary tale.

What is known is that encrypting again cannot make the cipher weaker, as long as the keys you chose to encrypt a second time are independent of the keys you use the first time.  The logic behind this is straight-forward; the attacker is assumed to know everything about the cipher except the keys.  If he has some ciphertext that he wants to attack, there's nothing preventing him from picking his own "second time key", and then encrypting the ciphertext to form a doubly-encrypted ciphertext.  If double-encrypting was inherently weaker, then he could attack that (and hence single-encryption would be equally weak).

On the other hand, if the two keys you use during the first and the second use are the same, this logic does not apply.  And, in fact, there are ciphers where this encrypting twice with the same key is a Bad Idea.  For example, some ciphers will, if you run the ciphertext through a second time with the same key, will generate a 'doubly-encrypted ciphertext' that is exactly the same as the plaintext; this is obviously weaker than the 'singly-encrypted ciphertext'


Is a changing public truecrypt container secure?

The truecrypt folks seem to have done a pretty good job with their crypto, so I'm going to say the answer is no, it would not get easier for them to find the password for any practical sense of the word "easier". They even have a write up on Sharing over Network which seems pertinent.

Typically in a cryptanalytical attack, however, the more information the analyst has, the easier their job. So I guess in that sense, theoretically the answer would be yes, their job is easier since they have extra information. But I personally wouldn't be worried about it as to gain any real-world advantage the analyst would probably need petabytes (if not more) of information for any attack to be practical. By the time they gather that much information, they probably could have guessed your password.


Is it possible to retrieve the original hash of a digital signature using a public key?

Yes, this is usually possible. You can use the RSA public key to:

perform modular exponentiation using the public exponent and modulus (raw RSA, sometimes you can use raw RSA decrypt with the public key for this);
interpret the result as unsigned big endian integer (usually this is already the case);
perform the unpadding (usually this just means finding the hash within the padding).

Note that there are multiple RSA schemes possible, e.g. PKCS#1 v1.5 padding or PSS padding. It depends on the signature generation which one is used. For an insecure 512 bit key you would generally bet on PKCS#1 v1.5 padding.
You can find both schemes in the relatively readable PKCS#1 RFC which includes the full description of above steps. However, it ends with creating the padding from an existing hash instead and compare, you need to reverse the padding creation instead - this isn't hard for PKCS#1, but you would not be able to do it for PSS as the hashed (mHash) value is hashed again (to get a hash value H).
For PKCS#1 v1.5 padding the hash value is just the hLen bytes that are right before the last byte, where hLen is the hash size in octets / bytes. Of course you'd still have to validate the rest of the padding as well to perform full signature verification.

If you are very lucky then decryption with the public key while choosing the PKCS#1 decryption scheme will directly give you the hash. But note that decryption generally requires the private key and a different unpadding scheme (also generally referred to as PKCS#1 padding, but the padding for encryption is still different than that for signature generation). However, it may just choose the signature unpadding instead for compatibility reasons.


Algorithm for factoring a number $n$ of a specific form given $n$ and $\varphi(n)$

The (in my opinion) simplest way to proceed about this is:
First compute the square root $m:=\sqrt n$ of $n$ in $\mathbb N$; this can, for instance, be done in time $\mathcal O(\log^3n)$ using a binary search.

The next step is to compute $\varphi(m)$ from $\varphi(n)$: by the properties of $\varphi$ we have
$$\varphi(n) = (p-1)p(q-1)q=\varphi(m)\cdot m \text,$$
hence $\varphi(m)=\varphi(n)/m$.

Now you can apply the standard method to compute $p$ and $q$ from $m$ and $\varphi(m)$, as described in Dan Boneh's paper (proof of fact 1). Note that in the linked paper, one is assumed to be given a tuple $(m,e,d)$ with $ed\equiv1\pmod{\varphi(m)}$, but that's not actually necessary: choosing $k$ as any non-zero multiple of $\varphi(m)$ is sufficient.


How to factorize the group order in Pohlig-Hellman algorithm

I will mostly talk about the Elliptic Curve since here the field size is around $2^{255}, 2^{448},2^{512}$ for secure curves. With Hasse's bound $$|N - (q+1)| \le 2 \sqrt{q}$$ the number of points is not too far away from the field size. With this, we can compare with the factoring records.
The current record achieved in 2020, CADO-NFS has factored an 828-bit $n$ with "roughly 2700 core-years, using Intel Xeon Gold 6130 CPUs as a reference (2.1GHz)". For the history see this detailed answer
If you set up a curve that has no big prime order on the order of the safe curves, it is not hard to factor for a dedicated attacker then use the Pohlig-Hellman algorithm for the discrete logarithm. Don't set up such a curve.
Actually, the parameters are never meant to be hiding see in SafeCurves, no security by obscurity. This more about don't propose a curve that doesn't have a large factor.
Having one large and a few small is fine like Curve255 has 8 as cofactor. The cofactor ($h = \#E(k)/n$) of the curve Curve25519 is $h=8$ which means that there are small subgroups of Curve25519. The order of the subgroups is $2,4,8,n,2n,4n,8n$.
Small groups are also vulnerable to small-subgroup attacks ( Lim–Lee active small-subgroup attacks), so we don't want them for this reason, too. Curve255 has no problem with either the curve itself or its twist.

Multiplicative discrete logarithm, on the other hand, dead for characteristic 2 ($GF(2^m)$) and almost dead for characteristic 3, ($GF(3^m)$). To be secure you need to a big field that the Pohlig-Hellman is your least problem (see on the keylength.com). Anyway, there are not to be kept secret either.


Can there be a need for 1024-bit (symmetric) encryption?

In order to answer this question, we need to understand the basis behind all of modern cryptography, which is computational hardness. Today, we believe that we know how to construct block ciphers that are secure, except for brute force search (or almost that secure). However, we don't really know this. We also think that factoring is hard, and so on. All of these are just assumptions since we don't know how to prove significant algorithmic lower bounds for problems like this. In particular, we don't even know how to prove that $P \neq NP$, and if $P=NP$ then no block cipher will be secure. Note, by the way, that even if $P\neq NP$, this doesn't suffice for crypto (we need one-way functions, which as an assumption is equivalent to pseudorandom functions/permutations).

Coming back to your question: assume that in 100 years it has been proven that $P\neq NP$ and even that one-way functions exist. However, assume also that all problems in $NP$ can be solved in time $2^{\sqrt n}$ where $n$ is the input length. (Note that it is strongly conjectured that $NP$-hard problems cannot be solved in sub-exponential time, but this is also an assumption.) In this case, if we want security against machines running in time $2^{128}$ then we will need keys of size 16384.  Another more likely possibility (but who knows) is that all $NP$ is solvable in time $2^{n/10}$. This would require keys of size $1280$.

Is this a likely event? Do I believe that this is the case? No, I don't! But, if you are asking: will such key lengths ever be needed? Well, no one really knows and the future will tell.

Currently we set key lengths by what we know. RSA needs 2048 bit keys due to the best factoring algorithms, and likewise discrete log and DDH over $\mathbb{Z}_p^*$; ECC needs 256-bit keys since the best algorithms known take time that is a square-root of the group size; symmetric keys need to be 128 bits since the best known attacks are brute force (and when better attacks are known then we phase out the algorithm).


How can I generate key scheduling for AES 256 bit key

I agree with @poncho, you have to read FIPS 197 (https://nvlpubs.nist.gov/nistpubs/fips/nist.fips.197.pdf). You should look on paragraph 5.2 Key Expansion. This one have a pseudo code. Also you can look on implementation in Go's runtime (https://github.com/golang/go/blob/master/src/crypto/aes/block.go).


Are HAIFA-construction based hash functions (e.g. Argon2) resistant to length-extension attacks?

Yes.

The HAIFA construct as introduced in A Framework for Iterative Hash Functions - HAIFA by Eli Biham and Orr Dunkelman is proposed with the explicit goal of eliminating various pitfalls of the classic Merkle-Damgaard construct.


obscuring timing attacks in vulnerable libraries

Let's talk with an example, RSA modular exponentiation where the timing of square $T_s \approx x$ and square and multiply is $T_{sm} \approx 2x$. Assume that we have $n$ operation that can be square or square and multiply.

Here we assume that the attacker knows everything about the random sleep;

Let the random values named $y_i; \; 1 \leq i \leq n$. If the $y_i < x$, then the timing attack will work. So, first rule;  $ \text{upper bound of  } y_i > x$.
Let $ 0 \leq y_i \leq 2x$. Clearly, any timing value greater then $3x$ is a square and multiply. If the attacker, capture the timings for the same key more than once, due to the randomization, it will reveal more square and multiply.
Let $ 0 \leq y_i \leq  (t \gg x)$. Here the randomization much bigger than $x$. It does not much differ from the previous, same idea. Only the attacker will need to capture more timings.

The result, direct randomization doesn't help.

If needed, one can talk about the required timing captures with probability.

What about an interesting one; that is adding a random wait according to average timings.

Let $ x \leq R_s < 2x $ be random delay for square and $ 0 \leq R_{sm} < x $ be random delay for square and multiply. So the randomized timings are $ 2x \leq R_s + T_s \leq 3x$ and  $2x \leq R_{sm} + T_{sm} \leq 3x$

This method prevents the attacker from distinguishing the timings.

Update: Actually, The last method may fail,too, since the random delay won't use any cpu at all ( There is an issue about C++ delay it is not supporting microseconds, POSIX does.).


How are these keys agreed upon/distributed? Practically speaking is asymmetric crypto a requirement to "bootstrap" and distribute keys?

The answers to those questions are beyond the scope of the RFC. So, it depends on the context in which HMAC is being used. The keys can be agreed upon/distributed in any secure manner. The RFC doesn't care. It could be via asymmetric crypto, it could be in person, it could be via carrier pigeon (if that is considered secure in your threat model).


Difference between cryptanalysis and brute force attacks

That's a matter of terminology, but generally cryptanalysis and brute force attack are mutually exclusive. Cryptanalysis means attacking a cryptographic system by looking for something clever that the designers of the system didn't think of, for example finding a mathematical relation that makes some computation fasters. A brute force attack is one that doesn't use any intelligence and enumerates all possibilities; cryptography is always vulnerable to brute force attacks, but if properly designed it makes them practically impossible by arranging for the probability of success to be utterly negligible.


Key confirmation and other benefits of double ratchet

This is convenient because each new key is used one-time and depends on the root key and message, so you do not need to constantly announce the next new key and wait for confirmation.  If Bob reads the encrypted message, he knows the encryption key and can decrypt the next message.  Since by exchanging messages that need to be decrypted, you get the opportunity to know how to decrypt the next message.  This is what is called “future” encryption in the article.  Thus, we have only one root key and constantly changing ephemeral keys, which are obtained from the messages themselves.  This allows you to simply communicate while being sure that the protection is very reliable.  I recommend reading the source code for this article from 2013.  Maybe this can clarify the principle.  A potential attacker, even if he intercepts the original message and all subsequent ones, will not be able to push off from something to start the attack, because he will have messages that are always encrypted with different keys and depend on encrypted messages that need to be decrypted.


Data is encrypted with Data Encryption Key. Each slot encrypts the DEK using a Key Encryption Key derived from a passphrase. Access to the DEK gets you the data. Access to any of the KEKs will give you access to the DEK. Clearing a passphrase slot, changing the passphrase, etc. does not change the DEK.

Whoever had access to the volume and a working passphrase could have extracted and saved the DEK, and that means they can use the DEK to decrypt the data in the future, when the slot with the passphrase they knew has been deleted. It also means they can decrypt any of the clones of the volume, even those for which the passphrase they knew was never valid.

If you really need to give different people access to a copy of the volume and be able to revoke access from other copies or from data added to the volume after their access was revoked, you have to change the DEK - reencrypt the volume or create a new encrypted volume (with possibly same passphrases protecting the new DEK) and copy all the data.

See https://crypto.stackexchange.com/a/24024

See https://security.stackexchange.com/a/205190/70830


When attacking keyed algorithms, how is it known when the output is correct?

Usually, the brute-force attack is performed with known-plaintext where a message $m$ and its ciphertext $c = \operatorname{XTEA}(k,m)$ is available. Indeed, one may need more than one to exactly found the key since a key selects permutation and at the point $m$ there can be more than one permutation selected by different keys that maps to the same ciphertext.
In ciphertext only attack, you may need some additional information to test the outcome, the candidate plaintext. Options are;

The encoding : for example in ASCII encoding the MSB is usually 0.

The padding : Block cipher if not used in streaming mode like the CTR mode, then a padding is needed. The padding can be used to identify the correctness. The padding can be  PKCS#5 as in the RSA DES challenge which was a known plaintext attack and bruteforced.

The language : if the target language is known than the current plaintext during the search can be tested for words like the string command in the Linux

Each of the options can increase your change. Having more ciphertext messages can eliminate more false candidate. Keep in mind that, however, if an option is not 100% correct, that can cause to find the key.
If there is no options, there is no test a validity of a candidate key.
In academical history, T.Siegenthaler use ASCII to break combined LFSR with a ciphertext only attack.

Decrypting a Class of Stream Ciphers Using Ciphertext Only

Is brute-forcing such a large space truly the only option?

If there is no weakness in the algorithm, the above is the only way. For the attacks in XTEA, listed from the Wikipeida

In 2004, Ko et al. presented a related-key differential attack on 27 out of 64 rounds of XTEA, requiring $2^{20.5}$ chosen plaintexts and a time complexity of $2^{115.15}$ (Ko et al., 2004).
In 2009, Lu presented a related-key rectangle attack on 36 rounds of XTEA, breaking more rounds than any previously published cryptanalytic results for XTEA. The paper presents two attacks, one without and with a weak key assumption, which corresponds to $2^{64.98}$ bytes of data and $2^{126.44}$ operations, and $2^{63.83}$ bytes of data and $2^{104.33}$ operations respectively.

Those require much more than one known-plaintext to execute an attack, and this is common if you are executing a brute force attack.
And, final note
If a cryptographic algorithm or scheme is breakable with ciphertext only attack,  turn back an run.
We need at least CPA secure ciphers in modern cryptography.


Is encrypting a public key with a symmetric key safe?

Is there any chance of finding symmetric key from encrypted public key?

The answer is no, assuming the symmetric key has sufficient entropy and a secure encryption algorithm and mode is used correctly.

Modern ciphers like AES with proper secret keys are not vulnerable to known plaintext attacks.

Why?

This has been answered in an earlier question: Why is AES resistant to known-plaintext attacks?

However:

  Is it ok to encrypt (full/partial) public key (of RSA, ECC) with shared symmetric key?

Definitely it is OK, but this is operation that is not often needed, though. In hybrid cryptosystems, it is common that the long-term secrets are private keys and public keys and those are used to establish per session symmetric keys. Doing it the other way around (having symmetric key and transporting public key) is somewhat less common.

Also, most usually public keys need some sort of authenticity or integrity protection, it rarely makes sense to try to encrypt them (confidentiality protection).

  symmetric key (password)

This sounds suspect. It is rare for a password to contain sufficient entropy for this purpose. If a password is weak or it is used improperly to create a symmetric key, then it is possible that an attacker can indeed find the secret key (e.g. via a form of dictionary attack).

Do the peers share symmetric key or password?

  want to share his ephemeral/long-term public key with intended receiver only

This is usually not possible. If the public key is ever used, somebody eavesdropping the communication will learn the public key. It is not possible to have only intended recipient knowing the public key.


Count the functions that have an entry with a specific structure

If you want the function to have the property for one input, say $x$, which is fixed ahead of time, you just focus on that output vector
$$
f(x)=f(x_1,\ldots,x_n)=(z_1,\ldots,z_{2n})
$$
and the condition $z_i=z_{i+n}$ holds with probability

$$P(given ~row ~is ~good)=\frac{2^{n}}{2^{2n}}=2^{-n},$$
since in this case you don't care what is happening in the other rows.

If you want this property to hold only for your selected input, this happens with probability

$$P(given~ row ~is ~good) (1-P(given ~row ~is ~good))^{2^n-1}=2^{-n}[1-2^{-n}]^{2^{n}-1}$$
 which can be estimated for large $n$ from above and below by using
$$
1-k\varepsilon+\frac{k(k-1)}{2}<[1-\varepsilon]^k<1-k\varepsilon
$$
where $\varepsilon$ is small and positive.


Does it take brute force to find a pair of plaintext and ciphertext that each follow a certain condition, given an AES encryption key?

Well, it's moderately difficult; you couldn't use that as a security assumption; however, it would be too difficult to expect someone to solve during an active protocol.  There's no nonobvious trick to it; the two methods at your disposal would be:

Select random plaintexts with the first 32 bits as $S_1$; encrypt them with key $K$, and check to see if the last 32 bits of the ciphertext happen to be $S_2$
Select random ciphertexts with the last 32 bits as $S_2$; decrypt them with key $K$, and check to see if the first 32 bits of the plaintext happen to be $S_1$

Either approach will take an expected $2^{32}$ random trials before success; at 1 $\mu$sec per AES operation (quite conservative; modern CPUs typically can do several times as fast as that), we're looking at perhaps an hour or two.

Perhaps you were hoping there was some clever way to take advantage of the partly known plaintext/ciphertext; it doesn't work out.  For example, you might be hoping to translate the AES cipher into a large series of boolean operations (with the known key, and known 32 bits of plaintext and ciphertexts), and solve the resulting set of equations.  However, AES has a fairly quick 'avalanche'; very quickly (within two rounds), all the internal bits will depend on all the unknown bits in subtle ways; the resulting set of equations will not have an easier solution than just trying various combinations of the 96 bits on one side (which is effectively what the straight-forward solutions do)


Text encryption algorithms that can be used and are secure

Generally we first encode the text to binary and then do the encryption. Then we can decrypt and decode to text again. If that suits your need then you can use any secure cipher. The conversion of a textual message to binary is called character encoding. UTF-8 is probably the most used encoding as it supports all Unicode characters & code points, keeps text relatively small and it is compatible with US ASCII. So there is generally no need for specialized text encryption algorithms.

If the ciphertext also needs to be text then you can perform an additional binary to text encoding. Before decryption you need to decode the encoding-specific text to binary again. Base 64 is probably the most used, as it is relatively efficient (6 bits per character) and ASCII (and thus UTF-8) compatible.