how to compute IV with AES CTR if key, plaintext and ciphertext are known?

Correct.

Note that normally we use the term nonce rather than IV, because the only requirement for the nonce is that it never be repeated, while an IV (e.g., for CBC) must additionally be unpredictable in advance.  Also usually you encrypt multiple 128-blocks in a single message by using E(nonce || 0, K), E(nonce || 1, K), E(nonce || 2, K), etc., as the pad, so you might get a nonce and a block counter.


How do you break encryption on a message?

As mentioned this is a very broad question, so please forgive me for not going into any great depth on each point.

There are a few ways to beat encryption. One way is to attack the actual math of the cryptography: for PGP that would involve cracking RSA, which would involve finding a way to solve the discrete log problem. This is the hardest method, but also the most complete. The second way is to attack particular implementations: a specific implementation might leak key information through how long encryption and decryption operations take, might leave secret data in memory for an attacker to find, etc. This is often combined with hacking the target's computer, possibly getting access to the plaintext and circumventing the encryption. "Extraordinary rendition" (kidnapping) and "enhanced interrogation" (torture) are other popular techniques for the US intelligence agencies to break encryption. Just torture the target until they give you a valid key.

There generally isn't a hash of a key transmitted. I'm not sure where you got this idea.

Breaking passwords is easy because people chose bad passwords. It's done via trying the most common passwords and seeing which ones hash to the matched hash. Encrypting things based directly on a password would be a terrible idea, key derivation algorithms are used to try to make breaking passwords harder, but they still rely on the user choosing a good password. Also note that hashes and encryption are very different things. They're both part of cryptography, but they serve very different purposes.

In general, there is no easy way to decrypt an encrypted message, so long as the encryption was done with a good algorithm and good implementation. If there IS an easy way to decrypt an encrypted message then the encryption system used is by definition broken.


Is a 256 bit HMAC-SHA256 key compromised if the tail is used for identification?

This won't seriously impact the security of the key. HMAC is pretty resilient and changing the last part of the hash won't allow attacks on the a hash such as SHA-256.

Note that you only select 4 characters, of which the last one only encodes 4 bits (as it is at the end). That means you've got a check value the size of 2^22 encoded bits, i.e. a chance of 1 / 4194304 that you match a key that you didn't mean to match. If you generate a whole lot of keys you can certainly not use this to select one key from a set because of the birthday problem.

The security of HMAC is diminished with 22 bits as well, leaving you with 256 - 22 = 234 bits maximum security. Halve this for a usual setting of HMAC, so with a bit of handwaving, you're left with 117 bits.

Generally you take bytes from binary data before encoding to base 64. If you need base 64 you can separately encode the bytes afterwards.

Possible without significant reduction in quality: yes.

Advisable? Absolutely not, there doesn't seem any good reason to do this. Use a KBKDF (key based key derivation mechanism) instead to create a key fingerprint. You may use the HMAC using the normal key and an unlikely string for data for this.


Is a PBKDF2-derived master key easier cracked if very many Data Protection Keys are derived from it?

Answering your three questions in order:

  "If I have a lot (more than $2^{32}$) of files to be encrypted, each file is encrypted using newly generated DPK. Will it somehow cause the MK to be easily found? or easier to find?"

It's not going to make it harder.  But no, as long as the KDF you're using lives up to its security claims, in practice it should not be feasible to construct the master key from the derived keys even if you have a lot of them.

If you want to be sure, check the standards and/or white papers defining your KDF and see if the security claims come with any restrictions like "assuming that at most $2^{64}$ bits of key material are derived from a single master key".

  "The document does not specify which KDF to be used when generating DPK. Can I use back the PBKDF2 again?"

In practice, yes, you could use PBKDF2 also for the second-stage KDF.  Since your input has already been key-stretched by the first application of PBKDF2, I'd suggest using an iteration count of 1 for the second stage to improve performance.  In fact, I'd recommend doing this whenever you want to derive more than one hash output block's worth of key material using PBKDF2, since it reduces the attacker's work advantage.

To conform with NIST SP 800-132, your second-stage KDF needs to be "approved".  Specifically, it needs to be (section 3.1):

  "Approved: FIPS-approved and/or NIST-recommended. An algorithm or technique that is 1) specified in a FIPS or NIST Recommendation; or 2) adopted in a FIPS or NIST Recommendation; or 3) specified in a list of NIST-approved security functions."

There are several NIST Special Publications describing key derivation functions.  SP 800-132 specifically references NIST SP 800-108, "Recommendation for Key Derivation Using Pseudorandom Functions", which specifies a set of approved methods for constructing a KDF from an approved pseudorandom function (HMAC or CMAC).  Then there's also NIST SP 800-135 rev. 1, "Recommendation for Existing Application-Specific Key Derivation Functions" and NIST SP 800-56C, "Recommendation for Key Derivation through Extraction-then-Expansion".  In particular, SP 800-56C specifically mentions HKDF (RFC 5869) as an instance of the general construction described therein, which I believe makes it approved, at least as long as it's instantiated with an approved hash function, such as SHA-2 or SHA-3.

As for PBKDF2, I'm not quite sure whether it should be counted as an "approved KDF" for this purpose or not.  Certainly it has been approved by NIST for password-based key derivation, and one could (and I certainly would) argue that key-based key derivation is merely a subset of that, but I'm not sure if that argument is actually explicitly supported by any official NIST publication.  In particular, I'm not sure if the use of PBKDF2 with an iteration count of 1 as a KBKDF is really sanctioned by any NIST publication.

In any case, HKDF isn't too different from PBKDF2 (they're both based on HMAC), and should be a simple and safe choice for a second-stage KDF.

  "Should I generate new random salt for each DPK? Or should I use something related (timestamp or file name) for the salt?"

The important requirement for the salt is that it should be globally unique.  A sufficiently long random string (at least 128 bits, preferably 256) is certainly one way to satisfy that requirement, but there are other options too.

For example, in the KDFs described in SP 800-108, the "salt" is, in effect, specified as the concatenation of two strings, Label and Context (separated by a null byte), defined as:

  "3) Label – A string that identifies the purpose for the derived keying material, which
  is encoded as a binary string. The encoding method for the Label is defined in a
  larger context, for example, in the protocol that uses a KDF.

  4) Context – A binary string containing the information related to the derived keying
  material. It may include identities of parties who are deriving and/or using the
  derived keying material and, optionally, a nonce known by the parties who derive
  the keys."

For your use case, the Label could include a number or file name identifying the DPK you want to derive, while Context could include a user identifier, and perhaps a fixed application identifier.

Similarly, HKDF takes both a "salt", used in the compression step, and an "info" string used in the expansion step, defined as:

  "salt: optional salt value (a non-secret random value); if not provided, it is set to a string of HashLen zeros."

and

  "info: optional context and application specific information (can be a zero-length string)"

The "salt" in the HKDF compression stage is basically the same as the salt for PBKDF2.  Indeed, HKDF allows omitting the compression stage entirely if the input is already a cryptographically strong key, such as the output of PBKDF2, so one could basically replace the compression stage of HKDF with PBKDF2.

The "info" string, however, is part of the second (expansion) stage, and can, among other things, be used to allow several different keys to be derived from the same compressed master key (PRK in the HKDF terminology).  For example, in your use case the "info" string could consist of a file number / name, a user ID and perhaps an application ID, plus whatever other information might be relevant.  The important part is that it should be globally unique for each DPK.


i guess that encrypted instruction set is an encrypted instruction commands for cpu that will only work for encrypted programs.you can steal the program but can't execute it on your normal computer,or you can't hack to that computer because that computer can't run normal standard program unless it switch to normal instruction or translate the program.


A key is derived from the password using a Password Based Key Derivation Function, in this case PBKDF2:

Key = PBKDF2(HMAC−SHA1, passphrase, ssid, 4096, 256)

PBKDF2 in turn is described by PKCS#5. These RSA cryptographic standards in turn are made available through RFC's nowadays, in this case RFC 2898: PKCS #5: Password-Based Cryptography Specification Version 2.0.

In this case the password needs to be 8 to 63 characters in size. The characters are converted to binary using ASCII so you can only use characters in the (printable) character range of ASCII.

In PBKDF2 the binary password is used as key to the HMAC function. The salt is the SSID of the Wi-Fi connection. The salt + a counter value is used as the initial input to the HMAC function. After that the previous HMAC output is used as input, until 4096 HMAC rounds is reached. Unfortunately it seems that it outputs 256 bits while SHA-1 only output 160 bits. This means that you have to increase the counter once and do all the rounds all over again.

The output of the PBKDF2 function is the pre-shared key or PSK. The PSK is used directly as PMK (pairwise master key) in the 4-way handshake.

This is also described in section H.4 : Suggested pass-phrase-to-PSK mapping of IEEE 802.11i (2004) which is available for download from the IEEE web site.


Is an IV useless for encrypting database IDs?

The mode of operation does not just matter; it defines the properties of the IV! The mode of operation is the part that specifies the size of the IV, the contents of the IV as well as the impact of abusing the IV. AES is a block cipher; by itself it only allows the key and a single message block as input; AES itself doesn't specify or know about any IV.

For instance, CBC mode requires an unpredictable (read: randomized) IV of the same size as the block size for common cryptographic purposes. If you fail to provide it then an adversary can detect identical ciphertext blocks and retrieve information on the plaintext blocks at the same location - very likely including IDs.

GCM mode on the other hand defaults to a 12 byte IV (although other sizes are possible). The IV is actually just a (binary) nonce: a number used once; you would be fine as long as it never repeats for the same key. However, if it fails then you can XOR ciphertext together to retrieve the XOR of two different plaintexts - which would quickly lead to a complete break of confidentiality for most types of plaintext.

Quite often IV's are simply prepended to the ciphertext. Most modes of operation have a statically sized IV (and if they haven't you can standardize the IV size for your specific protocol). Using a cryptographically secure, random IV is a well-established practice which you could use for your specific problem, as long as your DB is able to store the expanded ciphertext.

If you also want the IDs to be integrity protected you might also need storage space for an authentication tag. A mode such as GCM is often used for this; authentication tags are generally 8 to 16 bytes (with 16 bytes giving most protection of course). HMAC could also be used for integrity protection, in which case the IV should be included in the calculation.

Which brings us to the static IV (SIV) mode of operation. With SIV the IV doubles as an authentication tag. For SIV mode the uniqueness of the plaintext assures the uniqueness of the IV. It has storage advantages over IV + authentication tag, and it doesn't require any separate random input or state machine (for a nonce / counter). Although it does expand the ciphertext size it seems otherwise perfect for encrypting ID values - as long as they don't repeat for multiple users.

There is also AES-GCM-SIV which brings the efficiency of AES-GCM to SIV mode. The original SIV uses AES-CMAC as an authentication mechanism.

If IDs are unique and fit inside a single block then you could simply use a single block encrypt to store ID's. Beware that this is brittle; if somebody decides to expand the ID size then the scheme may well break. You can use ECB mode for this if the block cipher is not directly available. CBC mode with a zero IV would perform the same operation for the first block. Using ECB or CBC makes the scheme even more brittle of course; using two blocks or more could introduce vulnerabilities.

And finally, if you need to store the IDs within the same amount of data then you may have a look at Format-Preserving Encryption (FPE). This is a less efficient mode with a higher learning curve and limited support. Like SIV mode it depends on the uniqueness of the input to achieve confidentiality. Its main advantage is that it doesn't expand the ciphertext over the plaintext size, regardless of how much data is occupied by the plaintext. It isn't limited by the block size, in other words.

Notes:

It is also fine to store the random IV's somewhere else in the DB, e.g. in a separate row.
Adding an authentication tag only provides limited protection against active attacks, for instance an attacker swapping encrypted ID's of different users. Generally DB is about securing data at rest, providing confidentiality of the ID's in case the DB gets stolen for instance. It's up to you to decide if the additional space required for the authentication tag is worth the cost.
Beware that messages / IDs may also be repeated in time. Relying on the uniqueness of the ID may e.g. still allow an adversary to track the ID for a specific user. If this is an attack vector or not depends on the specific use case.


Smallest Guaranteed hash collision cycle length

In a uniform random function, which is a mostly reasonable model for SHA-256, you are not guaranteed that any particular element lies in a cycle: it could go $A \mapsto B \mapsto C \mapsto B$ and therefore never return to $A$.

In fact, only a tiny minority of elements are likely on cycles at all—the expected number of elements on cycles in a uniform function of $n$ elements grows with $\frac 1 2 \sqrt{2\pi n}$; for SHA-256, this is about $2^{128}$ of $2^{256}$ possible 256-bitstrings, i.e. the probability that any particular element is on a SHA-256 cycle is about $2^{-128}$.

However, if you just want to know how long you must pursue a hash chain before it cycles somewhere—not necessarily back to where you started ($A$), but somewhere you started going in circles lost in the desert trying to follow your own tracks like a pair of Belgian detectives ($B$)—the length of that chain turns out to have the same distribution as the number of elements on a cycle, with expectation $\frac 1 2 \sqrt{2\pi n}$, and the expected length of the cycle itself is $\frac 1 4 \sqrt{2\pi n}$.

So on average you'd have to follow $2^{128}$ elements before you ever come back upon your footsteps somewhere in a SHA-256 hash chain, and the average cycle length is about $2^{127}$, so you'd skip half your footsteps when you cycle back.

Here's an illustration that I stole from fgrieu of a 7-bit hash function—the vast majority of points, the grey dots, are not on cycles at all; only the red dots are on cycles:

Of course, in principle it could turn out that SHA-256 is actually a permutation of $\{0,1\}^{256}$ and is a single giant cycle, in which case you would actually have to tread $2^{256}$ steps—this, rather than the much larger $2^{256}!$, is the maximum number of steps before you are 100% guaranteed to have cycled back upon your footsteps.  But it is exceedingly unlikely that SHA-256 is a permutation, let alone a cyclic permutation—this would be an astonishing development if proven.

See Harris 1960 (paywall-free) for everything you need to know about statistics of uniform random functions, permutations, and derangements.


A doubt about Diffie-Hellman Key Exchange

What exactly do you doubt about the CDH or DDH problems?

  Is it possible to send a message to someone using only the Diffie–Hellman key exchange?

You cannot "send" a message using DHKE but you may use its resulting shared secret as a one-time-pad (by multiplication; not XOR) to "encrypt" a message encoded as a group element. When the sender uses a unique key per message, this is called ElGamal.

To encrypt a larger message we'll step back to Diffie-Hellman and use the hash of its shared secret as our key for a symmetric stream cipher. This is called hybrid encryption.

However neither scheme above authenticates our messages, thus an active adversary may tamper with our messages and depending on our application may recover our messages. Along the symmetric route we just need to replace encryption with authenticated encryption.

Instead of reinventing the wheel, this function is known to libsodium as crypto_seal_box. If you want to send many messages, you may prefer one handshake per session and use streams.

You probably don't want to use a single DHKE, but perhaps two or three. Two if you need forward secrecy and three if you want forward secrecy and mutual authentication. The Noise protocol elaborates on many variations and Signal uses an extension of triple-DH. All of these options require the receiver to send the sender at least one message per handshake.


Why is RSA usually limited to messages up to 1 block

We do not really know how to do RSA encryption of messages which span multiple blocks. At least not securely. The problem is already hard for block ciphers (see all the defined modes of operation).

Also, the worst performance issue with arithmetic cryptography like RSA is not about CPU, but about size. When you encrypt a piece of data with RSA, you get some overhead. E.g. with a 1024-bit RSA key, you can encrypt at most 117 bytes at a time, but this yields 128 bytes. When transmitting a long message, a fixed overhead of a few hundred bytes is much more tolerable than a +10% size increase.

CPU efficiency is often quoted as the reason we do hybrid encryption, but it is rarely as compelling as the two problems explained above.

(Additional point: since proper RSA encryption needs randomness, you must have a cryptographically strong PRNG -- also known as "a stream cipher". So even non-hybrid encryption does not avoid using symmetric primitives.)


What are the practical differences between 256-bit, 192-bit, and 128-bit AES encryption?

For practical purposes, 128-bit keys are sufficient to ensure security. The larger key sizes exist mostly to satisfy some US military regulations which call for the existence of several distinct "security levels", regardless of whether breaking the lowest level is already far beyond existing technology.

The larger key sizes imply some CPU overhead (+20% for a 192-bit key, +40% for a 256-bit key: internally, the AES is a sequence of "rounds" and the AES standard says that there shall be 10, 12 or 14 rounds, for a 128-bit, 192-bit or 256-bit key, respectively). So there is some rational reason not to use a larger than necessary key.

A larger key size also resists better to large quantum computer attacks: Using Grover's algorithm, a brute-force attack on any k-bit key block cipher would only take $O(2^{k/2})$ steps, so a 256-bit key would still give 128-bit security, while a 128-bit key could be cracked in 2^64 operations, which is doable. But as far as I know, the threat of QC was an ulterior rationalization; also, it does not explain the 192-bit key size.
(And quantum computers of this size are not yet in sight for the next some years.)


In ECDSA, how many field operations are used for signature verification?

Usually, the interleaving of wNAFs is faster than Shamir's trick for simultaneous point multiplication.
Using interleaving with window sizes 5 (fixed) and 4 (random), the total number of operations is roughly (taken from Hankerson et al's Guide to ECC)

$(0.37t +  3)A + (t + 1)D$

where t is the bitlength of the scalars (which should be the same as the bitlength of the field size for standard curves), A is a mixed point addition (projective + affine) and D is a point doubling.

For standard prime curves with $a=-3$, using Jacobian coordinates, we have (from the EFD):

$A = 7M + 4S$,

$D = 3M + 5S$,

where $M$ is a field multiplication and $S$ is a field squaring. Therefore,

$M = (5.59t + 24)$,

$S = (6.48t + 17)$.

For the 128-bit level of security, if I got everything right, $t=256, M = 1455, S = 1675$.


How much data does a session/data key typically encrypt?

The most common encryption protocol is probably TLS, as used in HTTPS. AES (with a 128-bit block size) is probably the most common encryption algorithm. Therefore the maximum amount of data that can be sent safely is $2^{128/2}=2^{64} blocks = 256EiB$.

Typical sessions end when the user closes the web page, and so send significantly less data. Even binge-watching an entire season of a TV show on a streaming site will only use a few GiB for a session.

Of course some users rarely close their browser tabs, but the most common PC OS is Windows which updates requiring a reboot at least once a month. Thus the longest duration of a session is likely to be around a month.

This answer has ignored session resumption, because it isn't that widely used. Even where it is used most protocols (including TLS) provide a way to re-negotiate keys.

TLS 1.2 recommends that sessions last no longer than 24 hours (section F.1.4).


Security in mixnets usually means two things. Anonymity and integrity.

For anonymity a single honest mix server suffices. Even if all other mix servers cooperate by releasing their permutations a message cannot be tracked, since the honest one does not publish his permutation. As a result it is lost when it reaches it.

For integrity zero knowledge proofs can be used.

Imagine you have a 2x2 reencryption mixnet with inputs:  $C_1 = Enc(m_1,r_1)$ and $C_2 = Enc(m_2,r_2)$.

The mixnet reencrypts the inputs and computes ${C'}_1 = Reenc(C_1)=Enc(m_1,r_1+r_1')$ and ${C'}_2 = Reenc(C_2)=Enc(m_2,r_2+r_2')$.

Then it selects a random bit $b$ and outputs $({C'}_1, {C'}_2)$ if $b=0$ and $({C'}_2, {C'}_1)$ if $b=1$.

In order to prove integrity one must prove that the output is a reencryption of the input without revealing the value of $b$. More specifically the statement $(C'_1 = Reenc(C_1) \wedge C'_2 = Reenc(C_2)) \bigvee (C'_1 = Reenc(C_2) \wedge C'_2 = Reenc(C_1))$ must be proved in zero knowledge.

This can be done using composition of the Chaum - Pedersen Protocol for DLOG equality.

For more details you can check Rivest's course in http://courses.csail.mit.edu/6.897/spring04/materials.html


How to calculate random factor in Paillier cryptosystem?

Let $C$ be the ciphertext and let $N$ be the public key. Thus, $C=(1+N)^m \cdot r^N \bmod N^2$ for some message $m$. We want to recover $r$ given the private key $\phi(N)$. This can be achieved by first computing $C'$ as an encryption of 0. To do this, decrypt to get $P$ and then take $C'=C\cdot (1-P\cdot N)\bmod N^2$ (this is scalar subtraction). Next, compute $M = N^{-1}\bmod \phi(N)$ and finally we have $r = {C'}^M\bmod N$. This works since ${C'}^M = r^{N\cdot M} = r^{1+k\cdot\phi(N)} = r \cdot (r^{\phi(N)})^k= r \bmod N$ since the order of $\mathbb{Z}_N^*$ is $\phi(N)$.

Regarding your second question, if you give someone $P$ and $r$ then they can just re-encrypt using $r$ and compare to $C$. This would prove that decryption is correct, but is not zero-knowledge. In case zero-knowledge is needed, this is also possible (and very efficient) in Paillier.


Where x509 signature validation is concerned, what does the error "x509 certificate chain incomplete of leaf TP not found" mean?

No TLS impact.

Any thoughts on what the impact is for a TLS connection?

None, because you are verifying an XML document and not establishing a TLS connection at all.

"x509 certificate chain incomplete of leaf TP not found"

This means that you receive a certificate, but because you are missing one or more certificates in your trust store, the certificate itself cannot be verified.
If you cannot verify the certificate then anybody could have created the certificate and send you the signature. So even if the signature verifies against the certificate, the result is meaningless.
Now there are two things that can be wrong:

you didn't establish any secure certificate to use with the sender of the XML document;
the signature or trust store is missing one or more intermediate certificates.

The best generic solution is to make sure all intermediate certificates (up to the trust point) are included in the XML signature and make sure you trust the root certificate in your particular trust store.


Is the first version of the Message-Digest algorithm by Ronald Rivest publically available?

Since I have not received any reply from Mr. Rivest's office after bugging them with a total of four emails in four weeks, I have no other option than to give up on hoping I ever receive a reply from his office.

After spending 6 weeks hunting down information all over the internet (and not receiving any reply to my emails), I am currently suspecting that MD1 has indeed never been published. I base this on the fact that another algorithm — MD3 — never made it beyond the experimental status either… due to problems with its algorithm. It could well be MD1 faced similar issues and also never made it beyond the lab. Another reason for suspecting this is that all RFCs were published in April 1992. If there had been any "beyond lab" MD1, I'm pretty sure it would have been published together with the other MD papers. My best guess is that MD2 was born out of failed MD1 experiments.

Yet, my suspicions might also be completely wrong. As said: I was not able to find any papers or hard facts in relation to MD1. Should you ever find reliable information about MD1, please post it as an answer. I will gladly unaccept my own answer to accept any answer that's able to present verifiable information and/or a publication/paper/book/whatever related to MD1.


Why should symmetric block cyphers be efficient?

Slowing block ciphers by increasing the number of rounds is an idea that does not catch because

Compared to 15 years ago, the volume of data routinely enciphered by a computer has grown much more than the frequency of its CPU (even multiplied by number of cores and IPC improvements). Hence speed of ciphers is more important than it ever was. Correspondingly, we see AES implemented in hardware (giving a huge speedup) or faster ciphers (like Chacha) increasingly used.
Increasing the number of rounds would only give the equivalent of a few bits more key in term of resistance to brute force; so if we want more resistance to brute force, we just use a wider key, and avoid a huge performance drop. For illustration: 4096 rounds instead of the regular 32 in Serpent makes brute force about 128 times harder, that's the equivalent of 7 extra bits of key (since 128 is 27); these few bits are negligible when AES candidates came in 128, 192 and 256-bit key size variants (going from 128 to 192 bits is an extra 64 bits, that is about 16 million million million times harder by brute force).

There are applications for slow cryptography: in particular password-based encryption, where a password is used as key of a cipher. In that application, we need something slow to mitigate the risk of brute force password search. But using a block cipher with many rounds would be very misguided, because for legitimate use one needs to make all the rounds for each block encrypted, when the attacker only needs to make all the rounds for the first block during most of the attack. Instead, what works best is making many rounds in an initial transformation from password to key (key streching), then using a regular (fast) cipher.

Rant: Sadly, many programs implement that poorly. For example, 7zip's AES encryption uses a fixed 1000 iterations of hashing (line 27 of WzAes.cpp there), leaving it needlessly vulnerable to brute force password search. Even GPG 1.x comes out of the box with insufficient settings for passphrase-to-key transformation as used to protect private keys at rest, and the following arcane settings beefing it up to the max are not entirely satisfying:

s2k-mode 3               # iterated hashing (that's the default)
s2k-count 65011712       # maximum supported number of iterations
s2k-digest-algo SHA512   # one of the slowest/widest hash supported
s2k-cipher-algo AES256   # no incentive to use a narrower key


Exploitability of AES in CBC Mode For Recovery of Plain Text

No, in this situation, CBC mode doesn't pose any security with a 256-bit uniform random AES key.
At data on rest, the AES-CBC has Ind-CPA security.
There is a padding oracle attack on the CBC mode due to PKCS#7 padding, however, that is not applying here since there is no server to query the padding.
There are multi-target attacks and quantum attacks on the AES, however, they are not possible on AES-256 which is the reason that it is the golden standard around.
The only problem that can occur on the user's side,

User has a weak password that can be found, severe!
User-machine has been hacked, severe!


Can a Password be Derived from a AES key?

Given an AES key, lets say an AES-256 key which is derived from a user password, is there any way to analyze the key and reverse engineer the password used to generate the key?

This is really the same problem as password cracking, where the simple strategy of trying statistically likely passwords at very high speed with specialized, massively parallel hardware (e.g., GPUs) has proven to be very fruitful.  This doesn't involve any sort of cryptanalytic attack to reverse the key derivation function, rather just relying on (a) the predictability of real-world passwords and (b) the fitness of GPUs for this sort of task.

If you're not familiar with this topic, this article and the enclosed video are a good primer.


Symmetric vs. Asymmetric cryptographic approaches to data security

The simple answer to "why are asymmetric algorithms more costly than symmetric algorithms" is because we have more requirements for asymmetric algorithms, and those additional requirements cost something to satisfy.

The requirement for (say) a symmetric encryption algorithm is "if you encrypt a message with the key, then someone without the key cannot infer anything about the message (apart from the length), but someone with the key can recover the exact message".

Now, asymmetric algorithms also meet this requirement. If we replace "key" with "the public and private keys", then we can encrypt messages (with the public key portion), and no one without the private key portion can deduce anything about the encrypted message.

On the other hand, we place additional requirements on asymmetric algorithms; someone with the public key still cannot decrypt messages, even though they can encrypt.  This implies that the public key and the private key must be related (because they are, in some sense, inverses of each other), but it can't be in an obvious way.

This means that the efficient constructions we use for symmetric algorithms (xor'ing in a keystream, Feistel networks, or SP-networks) just won't work, because those are easily invertable (given the key) by construction.  For symmetric operations, we can pick operations rather arbitrary, limited only by their efficiency, and how well they are disguised by a secret key.  Instead, we also need to limit ourselves to operations which have nonobvious relationships; these mathematical constructions (which is where we find this nonobviousness) are considerably less efficient.

As for when asymmetric operations "trump" asymmetric ones; the rule is simple: if you need the additional properties that asymmetric operations provide, they're better; if you don't, then they're not needed.


Hash coordinates (back-end) without the client (front-end) knowing the coordinates, but to be able to guess them

You should not send salt to the front end. Send only the hash. After the "game" completed, e.g. after the front end has done 20 attempts you named, you should present the right answer and the salt. Thus every participant can check that the hash you presented at the beginning really matches the message and the salt.
And the cryptographic properties of SHA-256 guarantee that you cannot deny the right answer, because there is no easy way to find another message (coordinates in your case) and another salt, that produce the same hash. In your example, if you publish hash sZv6eqPT9bqGiXbjvO8yrb4wuFjl0Z1CwSHdnIgGqEI=, then everyone can be sure that you cannot find any other salt and any other message (coordinates) that produce the same hash.


Is that required that $G$ and $H$ are two different generators of the same group?

Yes. Pedersen commitment uses random public generators $G$ and $H$ of a suitable large group where the Discrete Logarithm is hard, thus $G$ and $H$ can safely be assumed distinct. Also, that condition implies no integer $w$ such that $G=w\,H$ can be found by anyone. These facts are assumed or stated.

  $C=a\,G+b\,H$ is a point on the curve

Yes, though at some implementation level, it is a bitstring describing a point on the curve.

  How do I know that $b\,H$ is generated by $H$ without revealing $b$?

Anyone given a bitstring alleged to describe a point generated by $H$ can check that assertion, simply by checking that the bitstring indeed describes a point on the curve (which is feasible since the curve's equation and bitstring convention is public). Being generated by $H$ follows, since all points on the curve are generated by any generator (by definition of a generator), and $H$ is a generator.

Also: since the first-person locutor in this question cares about not revealing $b$, s/he knows $b$, thus can compute $b\,H$, which by construction is generated by $H$. If s/he makes that computation privately, that's an alternate way of making the verification without disclosing $b$.

  How do I know that $b\,H$ is not generated by $G$?

Point $b\,H$ is generated by $G$, even though it may not have been obtained by computation of $x\,G$ for some integer $x$. Obtaining integer $x$ such that $x\,G=b\,H$ not knowing random $b$ would be as hard as the discrete logarithm problem for $G$.

My guess is that the intended question 3 is:

  How do I know that the alleged $C=b\,H$ was obtained by computation of $b\,H$ without being revealed $b$?

As a verifier in a Pedersen commitment, you don't know that the alleged $C=b\,H$ was obtained by computation of $b\,H$ until being given $b$ by the prover, which is how s/he demonstrates $a=0$.

As rightly pointed in an other answer, there are different interactive protocols (when Pedersen commitment is not) allowing a prover to demonstrate knowledge of integer $b$ such that $b\,H$ is a certain public point, without revealing $b$. Schnorr protocol does so, as:

prover generates random integer $r$, computes and sends point $T\gets r\,H$
verifier generates and sends random integer $i$
prover computes and sends integer $s\gets i\,b+r\bmod n$, where $n$ is the (public) order of the curve
verifier knowing point $b\,H$ computes point $i\,(b\,H)$, then point $i\,(b\,H)+T$; computes point $s\,H$; and ensures $i\,(b\,H)+T=s\,H$.


How to generate a public key from a private ECDSA key?

The write up on Wikipedia is pretty good. I won't go into all the detail that they do there, but your private key is a randomly selected integer $d_A$ selected from $[1,n-1]$ where $n$ is the order of the group. The public key is $Q_A=d_AG$ where $G$ is the base point on the curve defined in the publicly agreed upon parameters.


How much entropy do you need for a secure certificate generation?

The answer to "how much entropy" is always "128 bits".

The tricky point is that the term "entropy" is very often misused. In general terms, the situation is the following:

A computer is a deterministic machine. From knowledge of its complete state (contents of disk, RAM and CPU registers) at a time $T$, one can compute its behaviour and state at any time $T' > T$, as long as no new unknown information is injected. Conceptually, this is about simulating the machine.
The attacker's goal is to try to recover the state at the time of key generation, in order to be able to simulate the key generation process and thus obtain the private key. However, the attacker does not know everything about the state, so he will have to "guess", i.e. to try possible values for the information he lacks. This is known as "brute force".
"That which the attacker does not know" can be quantified into the notion of "entropy": we will say that the state has an entropy of $n$ bits if the best possible brute force strategy will require, on average, $2^{n-1}$ tries before hitting the right one.

Note that this notion does not require that the unknown information is exactly a sequence of uniformly random bits. The definition is such that if the attacker knows everything except $n$ bits, which are (from the point of view of the attacker) exactly random, uniform, and independent of each other, then the entropy is $n$ bits. In a more practical setup, the "entropy bits" come from measures of physical events (e.g. precise timing of interrupts originating from the hardware); these measure will be encoded over a lot more than $n$ bits. This is not that much a problem since we can always somehow "concentrate" entropy bits by hashing all them together.

If the attacker-unknown data is a single byte, then the attacker will just have to try at most $256$ possible values (and on average $128$) to recover the private key. This is the same as saying that 8 bits cannot contain more than 8 bits of entropy (and may contain less if the attacker has some partial knowledge of the byte, e.g. he knows whether some values are more probable than other).

The amount of needed entropy is basically: "enough to make brute force stupidly expensive". "128 bits" are the traditional value for "way too much" (it's the new tradition; twenty years ago, we would have used 80 bits, but the relentless advances in technology and economics make an $2^{80}$ computation task less ludicrous than what it used to be). If your private key is generated with a cryptographically secure PRNG which is itself seeded with attacker-unknown data that cumulate at least 128 bits of entropy, then, by definition, brute-forcing that entropy is unfeasible (the attacker won't be able to try more than a negligibly small fraction of the space of possible values), and the job is done.

Note that an attacker gets to choose between trying to brute-force the generation seed, and trying to unravel the private key from the public key using its mathematical structure (e.g. trying to factorize the modulus, in the case of RSA keys). He will use the strategy that is easiest for him. In that sense, you "just" need enough entropy to make mathematical breaks easier than PRNG seed brute-force. In practice you inject enough entropy to make brute-forcing unfeasible, and you use asymmetric keys such that mathematically breaking them is not feasible either (e.g. with RSA, use 2048 bits or more).

Some people argue that if quantum computers ever come to fruition, then, in some sense (and with a lot of usually unspoken caveats), an attacker with a quantum computer could quantum-brute-force an $n$-bit PRNG seed with cost $2^{n/2}$ only (with a variant of Grover's algorithm); thus, "256 bits" would be needed to protect against that. On the other hand, a working quantum computer would break through the mathematics of a RSA, DSA, DH or elliptic curve key with extreme efficiency, making the point moot: as long as you use RSA, you are making the bet that quantum computers do not exist (and, for now, this is not that bad a bet).


What is the time complexity of computing a cryptographic hash function/random oracle?

Most hash functions are designed with an initialization stage (with a fixed performance overhead), a compression function and state update function that process the input in blocks (with a fixed per-block performance overhead), and a finalization stage (with a fixed performance overhead).

Typically that means you can consider initialization and finalization as a single constant when evaluating computational complexity of a hash function, and the per-block compression and state update can likewise be considered as a single constant.

You could approximate this as $\mathcal{O}(c+xn)$, where $n$ is the number of blocks required to fit the input (accounting for padding), $x$ is the constant for per-block overhead, and $c$ is the constant for initialization and finalization.

For longer messages of arbitrary length, it would typically be simplified as just $\mathcal{O}(n)$ where $n$ is the length.

In many cases, this complexity is insignificant compared to other elements of a larger algorithm involving hashes, and might therefore not even be counted in the complexity analysis.

Also, when input sizes are fixed you may simply assume a constant value, which essentially means rounding to $\mathcal{O}(1)$.

In the case of variable width outputs (technically not a hash, but still the same family of symmetric functions) like SHA3 SHAKE256, a XOF (extensible output function), the computational complexity is approximately equivalent to combining a hash with a stream cipher. In this case, you have $n_1$ for the input size and $n_2$ for the output size, and the complexity would approximately be $\mathcal{O}(c+x n_1+y n_2)$ where $x$ is the overhead per input block and $y$ is the overhead for the bit stream output per output block. This may be simplified as $\mathcal{O}(n_1+n_2)$.

Again, when both sizes are fixed (such as if you use the XOF for a fixed purpose in a protocol, like hashing a key to produce a bitmask for a digital signature function, like in some RSA implementations), it can be approximated as $\mathcal{O}(1)$.


Actual RSA encryption & decryption of strings?

Practically, when RSA is used to encrypt strings, what is the $x$ in $x^e\bmod n$?

That depends on the variant of RSA. Among the most common:

Toy-sized textbook RSA, where the public modulus $n$ is small: it is customary to encrypt letter by letter (or pair of letters, as in the original RSA article's small example) and concatenate the RSA cryptograms. Thus $x$ is the rank of the letters in the encoding used (or $x=x_0\,b+x_1$ where $x_0$ and $x_1$ are the ranks of two letters, with $b$ a public constant greater than the maximum value of $x_i$, e.g. $b=100$ in said article). There is no security for small $n$: a toy hammer won't actually nail. Small $n$ is anything up to like a hundred decimal digits. That can be factored quickly, which allows decryption. See this for records.

Textbook RSA with large $n$: it is customary to transform the string into bytes (e.g. per UTF-8, the modern compatible superset of ASCII), then from bytestring to integer $x$ (usually per OS2IP). In Python
int.from_bytes(bytes('François wears a !', 'UTF-8'), byteorder='big', signed=False)

There is a size limitation to $k-1$ bytes, where $2^{8(k-1)}<n<2^{8k}$, which insures $0\le x<n$. On decryption, leading zero bytes are ignored/removed (due to the simplistic conversion from string to bytestring). Variations abound (some encoding of size to allow any bytestring, padding on the right so that $x$ is large even for small strings, endianness…).
Caution: Textbook RSA in not secure under Choosen Plaintext Attack:

An attacker can trivially verify a guess of the plaintext: just encrypt the guess and check against the cryptogram. That attack is devastating for names on the class roll, credit card number…
When short strings encode to small integers $x$, several other attacks apply, including

when $x$ happens to we writable as $x=x_a\cdot x_b$ for integers $x_a$ and $x_b$ small enough to be found by enumeration, there's a meet-in-the-middle attack
when $e<\log_2(N)/\log_2(x)$, it stands $x^e\bmod N\,=\,x^e$, and thus it's trivial to find $x$ by $e\text{th}$ root extraction.

RSAES-PKCS1-v1_5: similar to 2 plus random padding, and means to remove it on decryption. $x$ is a combination of the string to encode, 3 constant bytes, and at least 8 random (non-zero) bytes. The string is thus limited to $k-11$ bytes (per §7.2.1 step 1). This method is better, but still has serious defects:

Implementations of decryption are difficult to protect against side-channel attacks. The first was Daniel Bleichenbacher's Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1, in proceedings of Crypto 1998, and there are many variations.
Unless we lower the $k-11$ limit, encryption is inherently vulnerable to an attack under CPA costing $2^{63}$ encryptions.

For these reasons, RSAES-PKCS1-v1_5 should not be used in any new design.

RSAES-OAEP: this is a major improvement of the above, using a hash. The string is transformed by the padding process into integer $x$ that is sort of random with $0\le x<2^{8(k-1)}$, and that's undone in decryption. Secure implementations of decryption are easier than for RSAES-PKCS1-v1_5. Security is theoretically reducible to that of the hash and of the RSA problem (finding a random $x$ given $x^e\bmod n$). The size limitation becomes $k-2h-2$ bytes (per §7.1.1 step 1.b) where $h$ is the size of the hash (e.g. $h=32$ bytes for SHA-256).

Hybrid encryption, e.g. RSA-KEM. A random value $x$ with $0\le x<N$ is RSA-encrypted with no padding, a symmetric encryption key is derived from that, and that key is used to encrypt(-and-MAC) the string to encrypt. Some avenues of implementation mistakes on decryption that still exist in RSAES-OAEP are gone. Security is theoretically reducible to that of the encryption and the RSA problem, with a simpler proof and/or quantitatively better assurance than for RSAES-OAEP. There is no size limitation. However the size of the cryptogram is slightly increased, and we need a Key Derivation Function and an authenticated cipher, when that's built into RSAES-OAEP.


The authentication tag is the output parameter, like in AES-GCM, which is generated by the symmetric key to authenticate the message.

$$(c,tag) = \operatorname{AES-GCM-Enc}(key,m,IV,AD)$$

Where $A$ is the Associated Data. The tag is verified by the same key, IV, and AD.

$$(\{T,F\},m?) = \operatorname{AES-GCM-Dec}(key,c,IV,tag,AD)$$ The tag verification must be performed before using the plaintext.

A signature, digital signature, is created by using the asymmetric encryption mechanisms using the private key. Such as DSA, ECDSA, EdDSA, or RSA signatures. The digital signature can only be created by the private key owner, and it can be verified by anyone who knows your public key. The secure hashing mechanism is an integral part of secure signatures not due to signing small messages.

$$\text{signature} = \operatorname{Sign}(k_{prv}, m)$$

$$ \{T,F\}\stackrel{?}{=} \operatorname{Verify}(\text{signature},k_{pub},m)$$

So the distinction is; the tag is generated by the symmetric key and the signature is generated by private-key.


Cryptanalysis and weaknesses of SEED cipher

A fault injection attack is based on the fact that you have a healthy black box on which you can do queries, but you can mess with the black box, for example flipping random bits.

In real life this could for example be a RFID chip which can be messed with using strong electronic fields. Attacks like these are generally:

Very sophisticated in theory and equipment.
Only apply to "black box models"; you have a side channel into the crypto device, but can't actually access the key.

Other than that, I'm not aware of any successful cryptanalysis against full-round SEED. So my suggestion is to warn your client of the hardware side-channel attacks (but since the question is about SSL I don't think it's applicable), but also make sure their software implementation is side-channel free.


What is standard email encryption practice?

Step 1: Generate your key pair
First you would generate your OpenPGP key pair e.g. with gnupg. The key generation format of pgp keys is complex, but you should know that the key pair consists of a public key, which is used by the sender to encrypt for the recipient(you) and the private key, which is used by the recipient to decrypt the message.
Step 2: Share your public key and collect public keys
In the next step a sender needs the public key of every recipient. To do this step, you can give your public key to the other person using an usb stick or you upload it to a public key server.
You also collect the public keys of users you want to send encrypted mails to.
Step 3: Encrypt and send message
You write your message and encrypt it for the recipients.
You might also sign the message, which guarantees that the recipient can verify that the message has been created by you. After the encryption you send the message to the recipients.
Step 4: Decrypt message and verify signature
If you recieve a message you decrypt it and if the message is signed, you verify the signature to be sure the message is sent by the sender to whom you have the public key.
Overview: Encryption process
If you encrypt a symmetric session key is generated. With this session key your message is encrypted. After the message encryption is completed you encrypt the session key with the public key of the recipient. After that you can optionally create a hash of the encrypted message and sign this hash with your private key, this is called a signature.
After these things are done the message gets saved in the OpenPGP format.
Notes:
This is a simplified answer, which does not exactly match all details of openPGP e.g. there is an encryption key pair and a signing keykey pair, but it should give you a general overview about how hybrid encryption works and openPGP works.


What do you mean "AES is not recommended for highly-redundant images"?

Perhaps you're referring to "ECB mode is not recommended for highly-redundant images" (and yes, AES can be used for ECB mode).

Yes, AES in ECB mode is not recommended for highly-redundant images, because it doesn't disguise when two 128 bit plaintext blocks are exactly the same.  Here is a famous example of a drawing of the Linux penguin encrypted using ECB mode:

As you can see, you can make out significant details of the original image.

AES in other modes (CBC, CFB, Ctr, GCM) doesn't have this weakness, and so are strongly preferred.


How to compute the storage cost of encrypted data

Your question is too broad in this form.

There are plenty of different symmetric encryption algorithms. Most of them produce 1MB output for 1MB input. Most of them are block-based, so they round up the input size to a multiple of a block-size. If you choose a specific algorithm, you can check the exact details yourselves. You should not choose encryption algorithm based on the overhead though, but rather choose one based on security and performance.

Also, it is usual to compress data before encrypting it, because it is impossible to do so after encryption.


Is that possible to prove that 'I do not know something' (i.e, the private key for a Bitcoin wallet) using cryptography?

You are asking for some cryptographic function whose output changes based on whether or not your mind holds a particular piece of information. There is no function which is capable of knowing what is in your mind. You can cryptographically prove ownership, but you cannot do the opposite.


Any generation will consume CPU, but it is rather unlikely that you will find that it slows down a modern smart phone.
Of the known algorithms - barring post-quantum cryptography - common two-prime RSA has the most CPU intense generation technique as it needs to find two large primes. However, RSA key pairs are normally used as long term, static key pairs. So generally applications only create them once in a while. And barring client authentication, they aren't required for setting up e.g. TLS connections.
Symmetric key pair generation is limited to random number generation. As long as the secure RNG doesn't block it is extremely unlikely that you'd notice any slowdowns for normal use cases with just a few keys. And if it does block it won't affect the CPU; it will only affect the application that requires the keys. (EC)DH key pair generation is relatively fast as well.
Finally, it is always possible to botch an implementation. You could try and create a random number generator that uses a lot of CPU or memory access to retrieve enough entropy. This could e.g. be used by programmers that use an API that lacks access to the normal cryptographic operations, e.g. when using a cross compatible, high level runtime.


How can I implement the "Multiplication Modulo" and "Addition Modulo" operations in IDEA?

Addition modulo $2^{16}$ just means, add the two numbers as you normally would, and subtract $2^{16}$ from the result until the sum is less than $2^{16}$. So suppose you wanted to add, say, 51995 and 29291 modulo $2^{16}$:

51995 + 29291 = 81286

Subtract 2^16 = 65536, you get 81286 - 65536 = 15750

This is less than 65536, so 51995 + 29291 = 15750 modulo 2^16.

Multiplication modulo $2^{16} + 1$ is exactly the same, except you multiply the two numbers instead of adding and you subtract $2^{16} + 1 = 65537$ repeatedly instead of $2^{16}$. And note the extra condition required by IDEA to prevent entropy destruction, that if one of the operands is zero, it is replaced by $2^{16}$ (this is not part of the definition of modular multiplication, but it is required to ensure reversibility - can you see why?).

This is a bit long-winded, fortunately there is a modulo operation available in most programming languages, usually called "mod" or "%", which you can use. Finite data types also have an implicit $2^n$ modulo operation where $n$ is the data type's bit width, through overflow (for instance, if you have a 1-byte variable set to 255, and increment it by one, it'll become zero), unless they are explicitly designed to saturate. There are also bitwise shortcuts you can use for IDEA to make it much faster since multiplication is slow, but I guess you don't really need those.

For a more detailed explanation, please see this link.


Doubt about the possible attacks on HMAC

The standard attack model for a MAC is that the attacker, not knowing the key, is allowed to ask the MAC for any messages s/he wants, and succeeds if later exhibiting a different message and its MAC that have probability sizably better than $2^{-n}$ to be correct.

Studying the birthday problem tells that that after $2^{\frac{n}{2}+1}$ random messages, probability is good (better than 86%) that two messages have the same MAC. But, for an ideal MAC, this is of no help to the attacker, because s/he has no clue about which messages collide before having asked the MAC of both, which invalidates these message as contributing to a successful attack. We have proof that this applies to HMAC, if the underlying hash function has suitable properties; see Mihir Bellare, New Proofs for NMAC and HMAC: Security without Collision Resistance, in Journal of Cryptology, 2015 (originally in proceedings Crypto 2006).

With the key, attacking any MAC is trivial: it's only a matter of computing the right MAC.

If for some reason we change the attack model and consider than the adversary wants to exhibit distinct messages with the same (H)MAC, knowledge of the key helps doubly:

The attacker no longer needs to ask MACs; s/he can compute them, presumably at a higher rate and without raising suspicion.
In the particular case of HMAC, that is likely to allow exploiting weaknesses (if any) of the underlying hash $\operatorname H$; specifically, with knowledge of the key $K$, it might be possible to find $M$ and $M'\ne M$ with $\operatorname H\big((K\oplus\text{ipad})\|M\big)=\operatorname H\big((K\oplus\text{ipad})\|M'\big)$, and it will follow that $\operatorname{HMAC-H}(K,M)=\operatorname{HMAC-H}(K,M')$. That would be trivial for $\operatorname H=\operatorname{MD5}$, and possible for $\operatorname H=\operatorname{SHA-1}$, given the weaknesses of these hashes (which include allowing to find colliding messages starting with any known prefix, very quickly for $\operatorname{MD5}$, feasibly for $\operatorname{SHA-1}$).


Is AES restricted to only 64 characters for the key/password?

Key sizes for AES are 128-bit, 192-bit and 256-bit. Depending on how you pack characters into bits, will determine how many characters that makes up. For example, you could pack 1000 characters into a 128-bit encryption key using something like PBKDF2 or scrypt.

That said, I wasn't aware that Truecrypt only supports 64 character passwords. Assuming that is correct (and I have no reason to doubt you yet), you could always use a keyfile with Truecrypt if you need a longer password, but keep in mind that a randomly chosen, 64 character password is surely infeasible to break any time soon.


A standard extension of ECIES for multiple recipients (broadcast / multiparty)?

When I do ECIES, can I omit the MAC $d$? An attacker doesn't gain
  anything by tampering with the session key, since that just causes the
  inner decryption or MAC check to fail.

I wouldn't rely on that property. Please don't do this.

  Can I use the same ephemeral EC pair $R=rG$ for all recipients?

Yes, you can do this. NaCl in principle does the same thing, but uses your own (static) private key for the key-agreement, while you make the $r$ temporarily your private key (for this message).

  Can I use the same IV for all invocations of the symmetric cipher
  (once per recipient in ECIES, plus once for the message itself)?

Yes you can do this, guaranteed that you always have distinct keys. The DH-style key agreements will guarentee the different symmetric keys for each recipient. The encapsulated symmetric message key will also be distinct so it's safe to re-use IVs here. An alternative suggestion would be to re-use the IV, but add some small value (like 0 for the actual message, 1 for the first recipient in the list, etc.) Generally you shouldn't re-use IVs if you're not sure whether all keys are unique.

  If the total length of my session keys is the same as the length of my
  $KDF()$ output, then can I get rid of the symmetric cipher $E(k_E;m)$ used
  within ECIES entirely, and replace it with $k_E\oplus m$?

I'm surprised you don't already do this. You can let your KDF generate a stream of key bytes (KDFs can output arbitrary length keys) and use them as stream cipher. This is an acknowledged variant of ECIES and is actually standardized and implemented for example in Crypto++ and BouncyCastle.


Proof of number of logins in last N days without saving login times

I'm not sure cryptography is the way to go. A day level counter could suffice, possibly aggregated later to coarser resolution and deleting any old information you no longer need.
If you want accurate counting for last N days with a certain resolution of last N days the information on what you did N days ago must be kept. It can be inferred by querying count and querying it again after a short while. But you could perhaps do things more fuzzy, maybe store some users data together and inactivate a user group if together they didn't meet the threshold and replace which users are grouped together periodically.


As owlstead wrote in the comments, you don't need a real public key infrastructure to use public key signatures for this. You can have A create a key-pair, then distribute the public key to B and C in advance, before any communications start.

A symmetric setup isn't much more complex either. You need two secrets, one between A and B, one between A and C. Calculate two MACs for each file, with either key. B can verify one, C the other. Even if E gets the secret key from C modifies a file, they can only calculate one of the MACs for modified messages.


Decently safe amount of AES key derivation?

VeraCrypt tries each hash and cipher combination with your supplied password if PKCS5-PRF is set to auto-detection on the enter password screen, i.e. it will try all. It will work until one of them work. It can do this in parallel. In the end, if none is working it will inform you that your password is incorrect.

Change it to the PKCS5-PRF that you selected during the setting the volume, it will not test the others. That will decrease the time.

In the attacker's eye, this will slow them, since they have to try all for each candidate passwords during brute-forcing possible passwords.

Also, the 500,000 derivations is important against the password crackers. The higher the better and it will affect the attacker's time linearly. In recent years their capabilities are highly increased.


Attacking Double DES (OFB Mode) given the initialization vector and not much else?

Read up on weak keys on Wikipedia.

The weak keys are the ones that result in the left and right key halves at the output of the Permuted Choice function being either all 1's or all 0's. So you can test all possibilities for weak keys to break the OFB mode.

What is more, if weak keys are used DES becomes idempotent, thus double encryption gives the plaintext back. This, however, would normally only work in ECB mode.


Logical OR operation in a homomorphic additive cryptosystem

Well, the problem is with logical OR and subtraction (which Pallier can also do), you've got FHE; that is, you can compute any combinatorial function of encrypted (binary) inputs.

Here's how it works, you can construct the NAND function:

$NAND(x, y) = (Enc(1) - x)\  OR\  (Enc(1) - y)$

If we limit $x$ and $y$ to being either encrypted 0, or encrypted 1, then the result of this is an encrypted 1 unless $x$ and $y$ are both an encrypted 1; in that case, the result will be an encrypted 0.

The $NAND$ function is complete; that is, we can create any combinatorial circuit using enough of them.


What is the relation between computational security and provable security?

‘Provable security’ just means there is a theorem.  It is a misleading term of art that should be carefully restricted to the literature if used at all, because it gives people false confidence: a system can have ‘provable security’ in the sense that there is a theorem, and could be completely breakable.  There are different kinds of theorems, but let's focus on whether there is a theorem or not and walk through some examples of provable vs. conjectured security.

Why do we think it is difficult to find $x$ given $y = x^3 \bmod{pq}$ when $p$ and $q$ are independent uniform random 1024-bit primes and $x$ is a uniform random nonnegative integer below $pq$?

Some of the smartest cryptanalysts on the planet have been banging their heads against this problem for nearly half a century, and have only a consistent track record of failure to show for it.  Maybe tomorrow someone will find a way to do it: we haven't ruled it out.  For example, if they found a way to factor $pq$, they could easily compute $y^d \bmod{pq}$ where $d$ solves $$3d \equiv 1 \pmod{\operatorname{lcm}(p - 1, q - 1)}.$$  Indeed, with unlimited budget or a quantum computer they could do this easily.
This is the RSA problem, with computational conjectured security.  Of course, this system is not directly useful for applications, because most applications don't naturally deal in random 1024-bit primes or uniform random ‘messages’ modulo a product of 1024-bit primes.  It is primarily a building block for practical cryptosystems.

Why do we think it is difficult to find $m$ given $m + p$ for $m, p \in \operatorname{GF}(2^t)$, when the distribution on $p$ has statistical distance $\varepsilon$ from uniform and $m$ has any distribution?

There is a theorem that the distinguishing advantage of any decision algorithm, that is the probability beyond 1/2 of guessing uniform random $b$ given $m_b + p$ for any choice of $m_0, m_1$, is bounded by $\varepsilon$.  No breakthroughs in cryptanalysis can change the result—any failure of security is guaranteed to be a consequence of pad reuse or poor pad generation.
This is a formulation of the one-time pad theorem, with information-theoretic provable security.  Of course, this system is not directly useful for applications, because you need a method to choose $p$ from a space as large as your space of possible messages, and do it independently for every message.  It is primarily a building block for practical cryptosystems.

Why do we think it is difficult to find $m$ given $(x^3 \bmod{pq}, m + H(x))$ where $x$ is a uniform random secret, $p$ and $q$ are uniform random secret 1024-bit primes, and $H$ is a uniform random public function?

There is a theorem, using the one-time pad theorem in (2) as a lemma, that if there is a decision algorithm with distinguishing advantage $\varepsilon$ against this system, then there is an algorithm that recovers $x$ from $x^3 \bmod{pq}$ with high probability; in other words, if the RSA problem of (1) is hard, then decrypting $(x^3 \bmod{pq}, m + H(x))$ to recover $m$ is hard.  As in (1), breakthroughs in cryptanalysis could lead to factoring $pq$ to break this; similarly, since we're using the random oracle model breakthroughs in cryptanalysis of the specific hash function we choose for $H$ could break this.
This is a weaker version of RSA-KEM/DEM, with computational provable security.  The if/then structure of this theorem, using the one-time pad lemma to prove it, enables cryptanalysts to focus their effort on the RSA problem, rather than dividing effort between the $(x^3 \bmod{pq}, m + H(x))$ problem, the RSASSA-PSS problem, the RSA-KEM problem, etc.  Of course, this system is not actually secure in a practical sense; you want a real DEM, which $m + H(x)$ is not—if you used this system, you would set yourself up for EFAILure.  And if anyone solved the RSA problem, this would still have computational provable security; the theorem would just be vacuous!

Why do we think it is difficult, given a message $m \in x\cdot\mathbb F_q[x] \setminus \{0\}$ and its authenticator $a = m(r) + s$ for uniform random $r, s \in \mathbb F_q$ and $q$ a prime power, to find another message/authenticator pair $(m', a')$ also satisfying $a' = m'(r) + s$?  (Here we are interpreting a message as a polynomial over the field $\mathbb F_q$ with zero constant term, e.g. by breaking it into $({\leq}\log_2 q)$-bit chunks and injecting them into $\mathbb F_q$ as coefficients.)

There is a theorem that $$\Pr[a' = m'(r) + s \mid a = m(r) + s] \leq \ell/q,$$ where $\ell$ is the maximum length of a message.  In other words, the one-time forgery probability is bounded by $\ell/q$.  As with the one-time pad theorem in (1), no breakthroughs in cryptanalysis will change this theorem.
This is a universal hashing one-time authenticator, with information-theoretic provable security.  Of course, this works only for a single message, so this is mainly useful as a building block for practical cryptosystems like crypto_secretbox_xsalsa20poly1305 or AES-GCM.  And, of course, the security depends on the choice of parameters: the theorem is still true when $q = 2$, but a forgery probability bound of 1/2 is not very secure!


Same certificate for server authentication and authorizatoin in other system

What I did in the end was to use DN/UID (OID: 0.9.2342.19200300.100.1.1) to store this value, exactly as it is suggested in an answer to this question.


Would adding more rounds to AES increase security?

Not really.

The cheapest known attacks on AES today are essentially generic key searches.  That is, they don't really depend on the details of AES itself.  If you increased the number of rounds, that would slightly raise the cost of testing each key, but it would also raise the cost of using your AES variant.  Raising the number of rounds doesn't meaningfully affect the cost of generic key searches.

With fewer rounds, there may be shortcuts to attacking AES that do depend on the details of AES itself.  But the number of rounds we settled on two decades ago seems to have held up quite well.  If someone suddenly came up with a new brilliant idea for a cheaper-than-generic attack on AES that eluded the world's best crypanalysts for two decades, maybe more rounds would thwart that, but that's all.

  As a bit more, would increasing rounds, keys, blocksize, or almost everything increase security?

In principle, assuming no specialized attacks, increasing the key and block size does increase security in the following senses:

The cost of an attack on AES-128 can be much less than $2^{128}$ AES evaluations—specifically, an adversary attacking a batch of $t$ different AES keys need only spend cost proportional to $2^{128}\!/t$ to find the first key.

That's why you should use AES-256, not AES-128, for a ‘128-bit security level’ against all adversaries (including quantum adversaries).  This one is an easy choice for you to make.

(If AES-256 is too costly in software, maybe you should use Salsa20 or ChaCha instead, and really an authenticated cipher like crypto_secretbox_xsalsa20poly1305 or ChaCha/Poly1305, which as a bonus avoids timing side channels that plague software implementations of AES.  But you should also measure measure measure.)
The block size of a permutation like AES affects the birthday bound for protocols, which is why Sweet32 hurts 64-bit block ciphers much more than 128-bit block ciphers no matter what the key size is—an adversary's advantage at breaking an application that handles $q$ blocks of data of $b$ bits apiece is usually around $q^2\!/2^b$.  A 128-bit block size makes Sweet32-type attacks much harder to pull off.  But the birthday bound of around $2^{64}$ blocks is still within the realm of feasibility—for example, the Bitcoin network today computes more than $2^{64}$ SHA-256 hashes every second.

If AES had a 256-bit block size, then the birthday bound would be around $2^{128}$, which is so large you never have to worry about it.  But it doesn't.  The original Rijndael proposal supported 256-bit blocks, but they weren't included in AES as adopted by NIST.  There's no easy choice you can make here without using a nonstandard AES variant that has received relatively little scrutiny—which means it is more likely to have specialized attacks cheaper than generic key searches that we don't know about.

(Again, maybe consider using crypto_secretbox_xsalsa20poly1305 or ChaCha/Poly1305 so that you don't have to worry about the AES block size either!)


Are there new secure hand or pen-and-paper ciphers in 2020?

Not that I know for the modern definition of "cipher", which implies a short key reusable for multiple messages. It's difficult to make such cipher convenient and secure.
The closest match in the open literature may be Bruce Schneier's Solitaire, aka Pontifex. It's a stream cipher (barely) doable by hand with a deck of cards, but theoretically broken in the modern meaning of that: a sizable bias in the keystream was found by Paul Crowley (circa 1999). And there's further Analysis of Solitaire by Daniel Shiu, arXiv (2019). Yet according to Schneier's assessment of Solitaire in light of that:

for the short message lengths you’re likely to use a manual cipher for, it’s still secure and will likely remain secure.

Note: Shiu has outlined proposed modifications to improve Solitaire, but they make it even less practical.
If we relax what a cipher is, we can use the One Time Pad: it is very doable by hand and remains secure as long as the pad remains confidential and not reused. If the encryption is error-free and the plaintext natural language, humans doing decryption can manage to recover from their own errors or small alterations in ciphertext. Tamper-evident opaque envelopes provides some protection of the pad against xerox copy during transfer. Some paper allows dissolving used pages in hot water.
Problem is that carrying a sheet of paper with random characters, such as the pad, could get one a bullet in the head, or worse. So we might want to use an ordinary-looking book as a substitute. Say, the starting page number, line, and offset are chosen at random with the additional condition that no material in the book gets reused, and is coded in the first characters. Alphabetical characters starting from there are grouped by blocks of 5, only the last character in such block is used, and the sum modulo 26 of 6 such characters yields the pad character, near uniformly random and independent of others. Nowadays it's economical to print a single copy of a book, and plausible randomized variants of an existing novel can be AI-generated, so that computer-assisted cryptanalysis will fail even if it tries the original as the pad, and the printing will pass casual scrutiny by an observer. Legal draft have an advantage over novels: adversaries fall asleep.


Doing further research accross multiple scientific portals and cryptography-related forums, it turns out that no formal specification exists… at all.

HChaCha20 can be constructed exactly the same way as HSalsa20, but has not really been specified or analysed to the full extend we usually expect cryptographic designs to be specified and analysed.

In this relation, it seems to make sense to also quote what CodesInChaos commented:

  I don't think such a spec exists. For the security, you can just directly transfer the "if Salsa20 is secure so is HSalsa20" proof to "if ChaCha is secure, so is HChaCha". Related: Can I use the ChaCha core as a 256-bit to 256-bit one-way function?

The same conclusion can be drawn from postings to the Cfrg mailing list (example):

  …
  The proof for XSalsa20/HSalsa20 should work for XChaCha20/HChaCha20 too
  afaics. (http://cr.yp.to/snuffle/xsalsa-20110204.pdf
  on http://cr.yp.to/snuffle.html)
  …


Calculating ciphersize of Paillier, SSE and OPE

How to know how much space to reserve?  There are two ways:

Take an implementation of the scheme, encrypt a 32-bit plaintext, and see how long the resulting ciphertext is. This is the simplest approach.
Understand the scheme at a conceptual level, and then use your understanding of the algorithm to predict how long the ciphertext will be.

Since it sounds like you don't understand the schemes at a conceptual level, my recommendation is that you use the first approach.

Note that your question does not provide enough information to answer your question completely. Here's what I can tell you, given the information in your question:

Paillier. Suppose you want security equivalent to that of 2048-bit RSA (a reasonable level of security; anything much shorter won't be very secure). Then Paillier ciphertexts will be 4096 bits wide: twice the length of the length of $n$. That's because a Paillier ciphertext is a number $c$ modulo $n^2$ (i.e., $c$ is between $1$ and $n^2-1$).  Even if you just want to encrypt a 32-bit plaintext, the ciphertext will still be 4096 bits long.  I know, that is a downside, but that's just the way it is.
OPE. Order-Preserving Encryption (OPE) is not a single scheme; it is a goal for a scheme.  It's like the difference between "RSA" vs "public-key encryption"; the former is a scheme, the latter is a goal.  OPE is analogous to "public-key encryption", not to "RSA".  Therefore, I can't tell you how long the ciphertexts will be if you use OPE, because the length of the ciphertexts will depend which OPE scheme you use, and there are many proposed schemes for OPE.
SSE. I don't know what the acronym SSE refers to.  If SSE refers to Searchable Symmetric Encryption, then there's a similar situation: we can't tell you how long the ciphertext will be, because there are many SSE schemes out there, and without knowing which of those schemes you are intending to use, we can't tell you how long the ciphertexts will be.


Hash functions in XEdDSA and VXEdDSA Signature Schemes

The hash functions are indexed to achieve domain separation. See, for example, Section 2.2.

The big idea is that if you have a secure underlying function (namely, the $hash$ function), for little cost, you can create a family of secure functions (the $hash_i$) with different outputs for a particular input $X$.

As an example of use of these indexed functions, if my input is DEAFBEAD,

hash_0(0xDEAFBEAD) == sha512(0xFF || 0xDEAFBEAD) == 9758ed9f853fabb2e963dc81ba617ea7dadbd802a82acdced8dc7813e908d1dfdd571b02f690487b1e1b5c7ac1938501cb0ccd00fac086a803758b5d92d811c9
hash_1(0xDEAFBEAD) == sha512(0xFE || 0xDEAFBEAD) == e8897c024462b42136308fbc975cebec5dcc83ae748047dd6cfa8d5a0806cb40fc1967932d605b6bb577cc1679e37fb94cba0af47ce32f5d6b56153e09f34a24
etc.

So throughout the document, you see $hash_1$ getting used in xeddsa_sign, $hash_2$ getting used in hash_to_point, and so on.

Each of the $hash_i$ now "does its own thing". For example, $hash_5$ may get used for signing only and $hash_6$ may get used for verification only.

The $hash_i$ are all equivalent to $hash$ in terms of security, so to my knowledge it doesn't matter which of the $hash_i$ you use for which purpose (except for $hash_0$, which is not to be used here). But this way, you get several independent secure functions derived from a single secure function.


How much entropy do I need to add to passwords if they are NOT used in conjunction with logins

Summarizing the question:

  I can have up to $v$ valid tokens at any point in time in the system, how much more entropy do my tokens need to have compared to "regular" password systems?

In addition to regular password entropy, $\log_2(v)$ bit extra is enough if the number of online attempts $a$ that an attacker can make is unchanged. That amount of additional entropy is necessary if you want no increase in the probability $\epsilon$ that $a$ online attempts succeed to find a working token, compared to the probability of logging into any account assuming the list of accounts is large and known to the attacker¹. Less extra entropy may be needed to maintain the probability that an adversary logs into a particular account², but how much depends on the distribution of passwords assumed in calculating password entropy.

Caution: Except when the system (rather than users) assign uniformly random password values, password entropy has almost nothing to do with the base-2 logarithm of the number of possible passwords. It varies widely with the restrictions put by the system on the choice of password, and with how dearly users care for the security of the data protected by the password. Also, that a certain password entropy is used is no proof that it is enough! And, the hypothesis of constant $a$ might not apply³.

Therefore, you can and should compute directly (without reference to a password-based system) how much entropy is needed in a token: that's $\log_2(v)+\log_2(1/\epsilon)+\log_2(a)$ bit⁴. The simplest and best is that the token is this many bits chosen independently and uniformly at random. That's assuming no information leak beyond correct/incorrect token, like getting an answer faster when the beginning of a token is correct, as notoriously occurs for comparisons using memcmp.

One may choose $\log_2(1/\epsilon)=20$ (slightly less that one chance in a million) and $a$ the number of possible attempts in a day given countermeasures³ to limit this in the server, or the sheer server capacity or link bandwidth absent such countermeasure. The estimation of $a$ should account for the possibility of concurrent attacks ($a$ is independent of network lag).

¹ Making the best attack strategy to test all accounts for the most likely password (or the few most likely ones starting from the most likely).

² Making the best attack strategy to test the account targeted for passwords approximately in decreasing order of likelihood.

³ Countermeasures to lower $a$ are easier with passwords and small user lists (or user lists assumed not to leak), because we can limit the number of login attempts per day/hour/minute and per user, something that might be impossible in the token context. Limiting the total number of attempts per second for the whole server opens to Denial of Service attacks, and limiting per attacker based on IP address is both difficult and uncertain: attackers may use multiple IP addresses using botnets, generate IPv6 addresses on the fly, or maybe spoof IP addresses if acting deep enough in the network infrastructure.

⁴ Proof for that formula: there are $k$ possible tokens, and $v$ of them are assigned uniformly at random and independently (except for being distinct). Attackers make $a$ attempts to log in by submitting a token, different at each time which maximizes their chances. Each attempt has the same probability $1/k$ to hit a particular token irrespective of the index of the attempt (for the same reason that the order in picking straws is immaterial to the probability one has to pick the shortest straw). Since these $a$ events are exclusive, the probability to hit any particular token in $a$ attempts is $a/k$. By the union bound, the probability $\epsilon$ to hit at least one of the $v$ tokens is at most $v$ times larger, that is $\epsilon\le v\,a/k$, and close to that for the low $\epsilon$ that we want in practice. Thus we want $k\ge v\,a/\epsilon$, and that only errs slightly, always on the safe side. Taking the base-2 logarithm, that gives $\log_2 k\ge\log_2(v)+\log_2(1/\epsilon)+\log_2(a)$.


Is 256 a reasonable length for a Diffie-Hellman safe prime?

I'm guessing whoever made the program was confused about key lengths. A 256-bit DH modulus will not give 256-bits of security. It will provide far less.

If you're reading http://www.keylength.com, the value here corresponds to the "discrete logarithm group". These days you really want a minimum of 2048 bits.


Signing an exchanged symmetric key that is asymmetrically encrypted

Your scenario seems overly simplified but anyway:

Just have Bob sign the key that he uploads.

You're assuming that people know each other's public keys anyway. So everybody can verify that the key has been signed by Bob.

If you want to keep your one-to-one trust structure the people adding new team members could also sign the key again or just sign that they trust Bob.


Randomized stream cipher using multivariant quadratic equations

Summary. This scheme is insecure.  It can be cryptanalyzed using standard methods from the cryptanalytic literature.  It also has poor performance.

Your algorithm. To summarize your scheme, in your algorithm a one-bit message $m \in GF(2)$ is encrypted by picking a random quadratic polynomial $p(x_1,\dots,x_{128})$ in $GF(2)[x_1,\dots,x_{128}]$, setting $c = m \oplus p(k)$, and transmitting $p(x_1,\dots,x_{128})$ and $c$.  Here $k \in GF(2)^{128}$ is the key, and $k$ remains fixed for all messages (while in contrast $p$ is chosen afresh for each message).

Performance.  This scheme expands the length of the message by a huge amount: by a factor of 16384 or so.  That's an enormous overhead.  Existing schemes don't have that problem.  Also, I expect that it would be very slow (compared to state-of-the-art stream ciphers), since for each bit encrypted, you have to pick 16384 pseudorandom bits and then evaluate the polynomial.

Algorithmic background: solving multivariate equations. There has been a lot of work in the cryptographic literature on the hardness of solving a system of multivariate equations.  One of the fundamental techniques is relinearization.

If you have $n^2$ systems of equations, where each equation is of degree $\le 2$ (i.e., a multivariate quadratic equation) and where you have $n$ unknowns, then relinearization can solve the system of equations in polynomial time (approx. $O(n^6)$ time or less).

Actually, you don't even need relinearization to solve this problem: simple linearization is sufficient.  In particular, if $x_1,\dots,x_n$ denote the unknowns, then for each pair $x_i,x_j$ of unknowns, you introduce a new variable $y_{i,j} = x_i x_j$.  Now we treat the $y_{i,j}$'s as additional unknowns.  With these additional unknowns, each equation is now a linear equation (in the $x_i$'s and $y_{i,j}$'s).  How many unknowns are there now?  Well, there are about $n^2/2$ of the $y_{i,j}$'s, and another $n$ of the $x_i$'s.  Consequently, we have $n^2$ linear equations in $\approx 0.5 n^2$ unknowns.  Since there are more equations than unknowns, we can use standard linear algebra to solve these linear equations.  The answer provides a solution to our original system of quadratic equations.

Relinearization is a generalization of this idea that works with a smaller number of equations, at some cost in running time.

For more on this subject, see the following research paper:

Cryptanalysis of the HFE Public Key Cryptosystem.  Aviad Kipnis and Adi Shamir.  CRYPTO 1999.

Cryptanalysis. With this background, it then becomes easy to see how to cryptanalyze your system.  Each bit of ciphertext reveals one quadratic equation on 128 unknowns, where the unknowns are the bits of the key $k$.  If we're given 16384 bits of known plaintext, then we have $16384 = 128^2$ quadratic equations in 128 unknowns.  Now we can apply linearization to recover the key.  (With relinearization, we could reduce the amount of known-plaintext required, but 16384 bits of known plaintext is already a very modest requirement, so the simple linearization attack is already devastating.)

Therefore, this algorithm falls to a simple known-plaintext attack.  For that reason, it does not meet the standard security requirements and is not suitable for use.


How many low-order bits of an RSA modulus can we safely fix to 1?

Consider the similar RSA key generation process:
Select a random odd value $z$ between 1 and $2^\ell - 1$; choose $p$ as usual, fix the lower $\ell$ bits of $q$ to $z p^{-1} \bmod 2^\ell$ and chose $q$ with this constraint.
Now, this generates RSA keys with the same asymptotic [1] distribution as the standard RSA key generation process.
Now, the only difference between this procedure and yours is that you use a fixed $z = 2^\ell -1$, rather than a random one.  However, the attacker can determine the value $z$ used, and so us telling him which $z$ we picked doesn't give him any additional information.
So, the only question is "does a specific value of $z$ yield a weakness?".  I do not know of any factoring method that is applicable to a specific $z$ value.

[1]: I say asymptotic, as the demonstration assumes that the lower $\ell$ bits of primes are evenly distributed over odd values; this has been proven to be true asymptopicly (for fixed $\ell$), it is a reasonable (but unproven) assumption for smaller primes.


When is the Random Oracle model (not) necessary?

A hash's security in the Random Oracle Model implies its collision-resistance, first-preimage resistance, and second-preimage resistance. In addition, security in the ROM implies that the hash's output is indistinguishable from random for an adversary without knowledge of the input, and that the hash is resistant to length-extension attack, neither of which is implied by collision-resistance, first-preimage resistance, or second-preimage resistance. So when randomness or length-extension matters, a hash secure in the ROM is useful in practice, and therefore in formal proofs.

Rigorous formal proofs of protocols often are easier with a hash secure in the ROM than with some weaker hypothesis. I pass at characterizing exactly when the ROM is indispensable, and if that's related to observability and/or programmability of the random oracle.


How does wNAF work with prime finite fields?

The scalar is a scalar, it is not uncommon to view it in $\mathbb{Z}$ instead of in a field defined by the order of the curve/point (note:it does never make sense to view it in a binary field).

So $d\mod2$ becomes the least significant bit of $d$ and $\frac{d}{2}$ becomes the same thing as $floor(\frac{d}{2})$ which is the same thing as a right shift by 1.


By looking the encryption procedure, you will see that we use a different sum of the vectors $\vec a_i$'s at each encryption. Thus, every ciphertext has the form
$$(\vec a, ~\vec a\cdot \vec s + e + \frac{p}{2} \cdot m)$$
with different terms $\vec a \in \mathbb{Z}_p^n$ and $e \in \mathbb{Z}$.
Notice that the probability that two ciphertexts have the same term $\vec a$ is already around $1/p^n$ (exponentially small), and the chance that you will see ciphertexts with the same pair $(\vec a, e)$ is even smaller.
Therefore, your attack does not work.
About the relation with LWE
You said that you are "not trying to break LWE", but this scheme is CPA-secure under the assumption that the LWE problem is hard. Thus, even if you are not trying to solve the LWE problem directly, your attack would provides us with an algorithm for the LWE problem (because your attack satisfies the CPA-security game, since you are only using an encryption oracle). This is basically what Lemma 5.4 of this paper is saying:

[...] if there exists a polynomial time algorithm $W$ that distinguishes between encryptions of 0 and 1 then there exists a distinguisher $Z$ that distinguishes between $A_{\vec s,\chi}$ [the LWE distribution] and $U$ [the uniform distribution] [...]


The SIV that you describe is the way that it is often specified specifically for key wrap. However, you always want to have an IV since encryption of the same message twice should yield different ciphertexts. If you only derive the IV from the message and key, then it will always be the same for the same message. By deriving the effective IV from the input IV, message and key, you guarantee that different messages and different IVs always give different ciphertexts, and the only "flaw" is when the same message is encrypted twice with the same IV (and in this case, only that fact is revealed). This is optimal nonce-reuse resistance.
Note that an IV is input to AES-GCM-SIV, but it is used to derive an "effective" IV from the tag, that is actually used to encrypt the message. The continuation in the RFC that you quoted is "The encrypted plaintext is produced by using AES, with the message-
encryption key, in counter mode (see [SP800-38A], Section 6.5) on the
unpadded plaintext.  The initial counter block is the tag with the
most significant bit of the last byte set to one." (Note that the initial counter block is the tag...)
AES-GCM-SIV also does continual key derivation from the input IV in order to get better security bounds. However, that is an orthogonal issue.


You won't be able to use a stream cipher with VOIP, because packet loss will prevent you from properly decrypting data that follows the missing chunks.

It may be possible to work around this issue, if you can figure out the size of the missing data, and assuming your chosen stream cipher does not have feedback, fast-forward to cipher to the start of the next block, all at the cost of wasted computation.

The correct approach that I am aware of, is to use a block cipher in CTR mode of operation, where the counter is based on the sequence numbers stamped in the packet headers. Essentially, you need to use a cipher that supports seeking within the data, without needing to decrypt all blocks prior to the block of interest.


What happens at this part in the key schedule of a Speck...?

For example, in the key schedule in the link, the result of the binary addition is being XOR d with 0?

It's very simple: In the key schedule, the exclusive-or step after the addition is done with the round counter, and the round counter starts at $0$ rather than $1$.

So for round number $0$, the first exclusive-or is done with the value $0$. In the next round, the exclusive-or is done with the value $1$, and so forth.

The supplied reference code might be easier to read than the block diagram, depending on your programming skills.


Using a Caesar Cipher with a key higher than 26?

The Caesar cipher doesn't just add a value to the character value. What it does is the following (per character in the plaintext):

it converts the character to the index of the character in the alphabet, say 0..25 for uppercase characters;
it performs modular addition of the value, using the size of the alphabet as the modulus;
it converts the resulting index back into a character.

For example you add the key 3 to the 'Z' character, then you:

convert the 'Z' character to the index 25 (index starting with 0, so 26 - 1);
add 3 and perform mod 26: $25 + 3 = 28$, $28 \bmod 26 = 2$;
convert the index 2 to the alphabet, 'C' (as 2 means the third character).

In human language, once you're past 'Z', you start with 'A' again.

Decryption is identical, but it uses subtraction of the key instead of addition.

Great, so what if the key is 26 or higher?

Well, because we use modular addition you can simply do the following: $c = p + k (\mod 26) = p + k - n \times 26 (\mod 26)$. In other words, you can subtract 26 as many times as you want until you get in the index range 0..25 again.

In the example above, using a key of 29 is identical to a key valued $29 - 26 = 3$.

A quick mind also notes that $-3 \bmod 26 = 23$. Which means that decryption with key 3 is identical to encryption with key 23. So basically you only have to create an encryption routine.

You'll also notice that a key that is a multiple of 26 (0, 26, 52 will map the index (and thus the character) back onto itself. So those keys are weak keys and should not be used. A key of 13 will make decryption identical to encryption (as 26 - 13 = 13 again).

Now above explains what you do if you keep to an alphabet size of 26 characters. If you have an alphabet of 26 characters. You can also extend the alphabet, e.g. using the "alphabet":

abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ.,0123456789

In that case you can perform modular addition / subtraction with a modulus of $26 + 26 + 2 + 10 = 64$.

To view a good implementation in Python you can have a look here


What should be used as a source for entropy?

If you need an entropy source, that's the TRNG, kind of by definition. A TRNG provides unpredictable output by physical means. An entropy source is one that provides unpredictable output; the entropy is a measure of how unpredictable.

Hardware entropy sources are rarely uniform, so they should never be used as an RNG, but as a seed to a CSPRNG, i.e. a deterministic algorithm that “smoothen” all correlations between bits.

So if you really need an entropy source, use the TRNG. But if what you're doing is anything other than seeding a CSPRNG, then what you really need is a random source; for that, use the CSPRNG seeded by the TRNG.

Having a 160-bit output makes me fear that your CSPRNG is based on SHA-1. SHA-1 is deprecated, but not broken yet. If you're using SHA-1, you should plan to replace it by SHA-256, but it isn't very urgent. What matters is primarily that you use a good CSPRNG algorithm on top of whatever hash or other cryptographic primitive you're using, hopefully NIST's Hash_DRBG or HMAC_DRBG if it's based on a hash.

  simplified formula for entropy (log2n) gives value of 7.32 for 160 bits and 9 for 512 bits. Will I be justified to claim 7.32 bit entropy if I decide to use the output of RNG?

Your calculation doesn't make sense. Think of what $n$ is in this formula! The entropy of a source with $n$ possible different equiprobable values is $\log_2(n)$. The entropy of a source that provides $k$ independent bits is $k$. If your source provided 512 independent bits then you would get 512 bits of entropy from it, but in practice physical sources have some amount of correlation that's hard to evaluate precisely, so you probably have much less. In any case, what matters with entropy is that it's sufficient to make the probability that a brute-force attack would succeed negligible. For this purpose, there is no meaningful difference between 160 bits and 512 bits.


What the X stands for in the front of Elliptic curve names like X25519

It is an open standard by IETF.org
We can find the details in the mail archive of IETF, D. J. Bernstein's response;

It has become increasingly common for "Curve25519" to refer to an
elliptic curve, while the original paper defined "Curve25519" as an
X-coordinate DH system using that curve. "Ed25519" unambiguously refers
to an Edwards-coordinate signature system using that curve.
Kenny and others in Toronto recommended changing terminology to clearly
separate these three items. Let me suggest the following terminology:

"X25519" is the recommended Montgomery-X-coordinate DH function.
"Ed25519" is the recommended Edwards-coordinate signature system.
"Curve25519" is the underlying elliptic curve.

All relevant coordinate systems already have standard names in the
literature, and I would suggest sticking to those names whenever it's
necessary to discuss the coordinate systems per se: [...]

Bolds are mine.


Q1 asks “Show how an attacker can act in place of Alice and send a file to Bob tricking him into believing that the file is coming from Alice.”

In your answer, Trudy simply relays the traffic to the two parties without doing anything else, thus this is not really an attack that achieves what is asked. Note that whatever Bob receives is truly coming from Alice in this session.

Hint for Q2: the problem in the protocol is that Bob cannot verify that the last message is fresh, and it can come from a previous session intercepted by Trudy (replay attack).