What is Standard Referencing of Cryptography Papers

I failed to find what the "vol. 97, 2004" part of the question's citation refers to, or a formal journal or proceedings publication for that paper. It is much earlier (made public in November 2000).

The first author cites his paper (at line 38 in the conference paper section here) as:

  BARRETO, P. S. L. M.;  Rijmen, V.; 2000: The KHAZAD Legacy-Level Block Cipher. In: 1st Open NESSIE Workshop, 2000, Leuven (Belgium). Proceedings of the 1st Open NESSIE Workshop.

The second author cites his paper (at line 235 here) as:

  P. S. Barreto, and V. Rijmen, "The Khazad legacy-level block cipher," In Proceedings of the 1st NESSIE Workshop, 15 pages, 2000.

It also has been cited as

  P. Barreto and V. Rijmen. The Khazad Legacy-Level Block Cipher. In
  First Open NESSIE Workshop, KU-Leuven, 2000. Submission to NESSIE.

If I had to cite this paper on this website, it could be as:

  Paulo S.L.M. Barreto and Vincent Rijmen, The KHAZAD Legacy-Level Block Cipher, submission to First Open NESSIE Workshop, 13-14 November 2000, Leuven, Belgium; file khazad/B/Khazad.pdf in khazad.zip.

The closest I found to 2004 is that Paulo Barreto cites (in the Other publications section here) a different, shorter paper,

  V. Rijmen, BARRETO,  P. S. L. M., “The Khazad Block Cipher,”, The Perl Journal 7, p. 5, 2003.

It is online here and was apparently an insert in this.

Addition: if there was ever formal Proceedings of the 1st Open NESSIE Workshop, its current web presence is this. Here are the remains of a Nessie Book planned circa 2004.


What EC curve is used by Apple iOS platform?

Apple's CryptKit Suite
Since Apple's actual documentation is sparse we need to look for all available source;
There is apple/swift-crypto Github page that we can find the source code and cryptokit page also provides only a list.

Swift Crypto is an open-source implementation of a substantial portion of the API of Apple CryptoKit suitable for use on Linux platforms. It enables cross-platform or server applications with the advantages of CryptoKit.

ECDH.swift implements the below standard NIST 800-186 curves

P256 + Signing
P256 + KeyAgreement
P384 + Signing
P384 + KeyAgreement
P521 + Signing
P521 + KeyAgreement
P256 + DH
P384 + DH
P521 + DH

The curves P256 (secp256r1 in SECG, prime256v1 in ANSI X9.62 and P-256 in NIST) and 384 (secp384r1) are in NSA Suite B
The Secp means: Standard for Efficient Cryptography Elliptic Curve Domain Parameters

The key derivation is HKDF

Signing

ECDSA Signing with NIST curves P256|P384|P512.
EdDSA Signing EdDSA signature over Curve25519. Not a standard naming there. I should be Ed25519.

Keys

Curve25519 key agreement

From the BoringSSL support lists

Curve25519 key agreement

For the security of these curves ( possibly a backdoor) see these questions from our site.

Should we trust the NIST-recommended ECC parameters?
Is there a feasible method by which NIST ECC curves over prime fields could be intentionally rigged?

The below from the iOS page SecKeySizes

secp192r1: 192-bit ECC Keys for Suite-B from RFC 4492 section 5.1.1.
secp256r1: 256-bit ECC Keys for Suite-B from RFC 4492 section 5.1.1.
secp384r1: 384-bit ECC Keys for Suite-B from RFC 4492 section 5.1.1.
secp521r1: 521-bit ECC Keys for Suite-B from RFC 4492 section 5.1.1.

There is also iOS-compatible ECIES implementation in Java

kSecKeyAlgorithmECIESEncryptionCofactorX963SHA256AESGCM
Little digging about the constant;

If we take a look at the corresponding constant kSecKeyAlgorithmECIESEncryptionCofactorX963SHA256AESGCM defined in SecKey.h (see here for example) then we can see that this algorithm is considered “legacy” and the recommended one is SecKeyAlgorithmECIESEncryptionCofactorVariableIVX963SHA256AESGCM instead (in Swift it’s eciesEncryptionCofactorVariableIVX963SHA256AESGCM).

and the below from darthnull.org/security

ECIES: Elliptic Curve Integrated Encryption System - an open standard that defines exactly how to do what we’re about to do
Cofactor: Include the elliptic curve’s “cofactor” when completing the Diffie-Hellman key agreement process
X963SHA256: Use the ANSI x9.63* key derivation function (KDF), with SHA-256 as an underlying hash function
AESGCM: For the final symmetric encryption, use AES in Galois Counter Mode (GCM), a form of authenticated encryption

The curve is SecP256R1 (This claim needs to be verified!!!)
The Secure Enclave
Apple describes the Secure Enclave as "a representation of a device’s hardware-based key manager. Secure Enclave only have

NIST P-256 signatures and key agreement as of 2020.

*real ANSI X9.63 is here


open source whitebox-crypto implementation

The current way of implementing a (symmetric) cryptographic algorithm as a white-box is to implement it as a network of encoded lookup tables (a good white-box will also have so called 'external encodings' applied, but I'll skip these for now).

In this case however, a network of tables is not required (one table will do) and as a result encoding the tables is no longer nescessry.
So in this case, I would implement this algorithm as 'a lookup table'.

Let's say (for easyness) that A=0, B=1, ..., Z=25.
Than we can implement the decrypt function on the client as following:

public int WhiteBoxDecrypt(int letter) {
    // Decrypt one encrypted block - in this case, a block is one character (represented as integer).
    int[] lookupTable = {24, 25, 0, 1, 2, ..., 23 };
    return lookupTable[letter];
}

Note that this implementation is as secure as a black box implementation would be (well, a black-box implementation that would decrypt per character). The only way to crack this implementation is to compare the inputs and outputs to the algorithm (all of these inputs and outputs are provided in a single table).
This is why using lookup tables is so cool - it's a datastructure that shows just inputs and outputs, just like a real black-box would do.

Bonus: a pretty good tutorial by James Muir on implementing a white-box AES can be found here.


Prove I know a value $v$ in a Pedersen Commitment without revealing it

This extension of the Schnorr protocol would appear to work:

$P := aG + vH$

$\operatorname{GenProof}(a, v)$:

$x, y \leftarrow Z_q$
$P' := xG + yH$
$t  := RandomOracle(P')$  (alternatively, the verifier picks $t$ after learning $P'$)
$x' := x + ta, y' := y + tv$
return $(P', x', y')$

$\operatorname{Verify}(P, P', x', y')$:

$t := RandomOracle(P')$
accept if $x'G + y'H = P' + tP$


what can attackers do between two end hosts

Attacks like this can be prevented by TLS.
Quote from Wikipedia:

The TLS protocol aims primarily to provide privacy and data integrity between two or more communicating computer applications.2:3 When secured by TLS, connections between a client (e.g., a web browser) and a server (e.g., wikipedia.org) have one or more of the following properties:

The connection is private (or secure) because symmetric cryptography is used to encrypt the data transmitted. The keys for this symmetric encryption are generated uniquely for each connection and are based on a shared secret negotiated at the start of the session (see TLS handshake). The server and client negotiate the details of which encryption algorithm and cryptographic keys to use before the first byte of data is transmitted (see § Algorithm below). The negotiation of a shared secret is both secure (the negotiated secret is unavailable to eavesdroppers and cannot be obtained, even by an attacker who places themselves in the middle of the connection) and reliable (no attacker can modify the communications during the negotiation without being detected).

The identity of the communicating parties can be authenticated using public-key cryptography. This authentication can be made optional, but is generally required for at least one of the parties (typically the server).

The connection is reliable because each message transmitted includes a message integrity check using a message authentication code to prevent undetected loss or alteration of the data during transmission.


IPSec vs SSL : Similarities and Differences

but do SSL and IPSec use different key schemes and algorithms from another to establish contexts?

Well, given that, by IPsec, you mean only AH and ESP (that is, RFC4301-4303), well, the obvious answer is that IPsec doesn't mandate any way to generate keys, select algorithms, or to establish contexts.  All that is assumed to be done by some other protocol (which might be IKEv1, IKEv2, GDOI, manual configuration or possibly others), and exactly how that is done is not IPsec's concern.

TLS (which is the name I prefer to SSL; you shouldn't be using SSLv3 and you really shouldn't even consider SSLv2) has embedded in it an authentication and key establishment protocol, which spells out exactly how things ought to be done.

Of course, as for how they do encryption and decryption, there are some differences.  Some of these differences are design decisions (TLS has traditionally done 'MAC and then ENCRYPT', while IPsec does 'ENCRYPT and then MAC'); on the other hand, a lot of the differences are due to the fact that they're addressing different problems:

TLS is over a reliable transport (typically TCP), while IPsec is over an unreliable transport (IP, which can drop and reorder packets).  What this means is that TLS keeps context between the sender and the receiver and updates that state (such as the sequence number); with IPsec, all that needs to be made explicit (as there is no guarantee that the receiver will get same packets in the same order that the sender sent). [1]
IPsec was designed specifically to protect IP traffic; hence it has a bunch of rules built in with IP in mind; for example, how fragments are processed, how it interacts with IP MTU, how packets interact with the security policy database, how DSCP bits are handled, how ECN (Explicit Congestion Notify) is handled.  In contrast, TLS was designed to protect a byte stream, and it makes no assumptions about what that byte stream means.
IPsec was always envisioned to be security gateway-friendly. That is, it was always expected that one use case for it would be a router in the middle that accepts plaintext packets (say, from your local office LAN), and sends them off encrypted through the internet (perhaps to another security gateway in a different location).  Of course, you could also use IPsec in an end-to-end fashion; both usages were considered in its design.  In contrast, TLS was always envisioned to be end-to-end; that say PC that generates the plaintext was expected to be the one encrypting it.  Now, you can design a TLS security gateway (and most certainly, people have); it is significantly less clean because of design choices behind TLS.

[1]: If you look at DTLS (which is also over an unreliable network), you will see that they modified the protocol to somewhat more like IPsec (such as explicit sequence numbers, and explicit record contexts (DTLS calls them epochs, IPsec relies on SPIs for that)


RSA - Ecrypting the same data with the same public key = same ciphertext?

The answer to your question is "yes, RSA will encrypt the same cleartext to the same ciphertext every time." And yes, this is a known property of RSA. That's why every standard that uses RSA, such as PKCS or CMS, specifies the use of randomized padding.


We want to answer "How many wolves are coming to attack?" by "twenty one" (big-endian), not "one twenty" (little-endian). That can be a matter of life and death, and perhaps natural selection of memes¹ made that the convention in many languages (German is an important exception). Big-endian is thus used in most human positional numeral systems.
When it comes to algorithms for exact addition of large integers, it's much easier to start with the low-order digits. Little-endian thus makes sense in some areas of computing, including making a desktop calculator, which was a motivating application of early microprocessors, and got Intel started in that business. That's why little-endian is sometime called the Intel convention.
In network routing according to packet destination address, the low-order bits of a destination address typically does not participate in the routing, and comes last is the destination address field. That could² me made even so slightly advantageous: having the high-order bits first allows to find the destination earlier. That's how I remember big-endian is called "network order".
In computing, the farther away from hardware, the more big-endian. Because predators.
In crypto, both still coexist, but there's a perceptible trend towards big-endianness. MD5 is little-endian (that made the very first collision exhibited wrong), SHA-1 and later hashes are big-endian. That's the NIST order. And ASN.1 integers are big-endian, thus it has won for many practical purposes.
Bernstein has an history of being a skilled low-level programmer of Intel-compatible CPUs (even recommending some), and generally opposes NIST. That's how I remember Curve25519 is nominally little-endian. OTOH, that's a mere convention that should be without cryptographic significance. When adding Curve25519 to something existing, it's possible to get it big endian (by accident or design), and keep/have that as an option.

¹ I know no evidence big-endianness went genetic!
² The tale of traders making special network equipment to crush the last nanoseconds of latency could use that. I can't pinpoint any network equipment, much less a modern one, that does. But I like the idea, and still hope something (a supercomputer cluster maybe) would use it.


Does a "commutative" asymmetric system exist?

RSA with random exponents would fulfill your key-swapping requirement. I.e. RSA where you generate one exponent randomly and then compute the other from it normally, with neither exponent made public. The operation to encrypt and decrypt is the same (modular exponentiation).

The security of this scheme, or some uses of it is considered in the (currently unanswered) question: Could this "symmetric RSA" scheme provide key compromise resistant communications?

Since you say you do not need it to be extremely secure, it should fit your bill regardless.


How to prove that a ciphertext is encrypting multiplication of two values?

Yes, this is doable.  You can verify that $m=a \times b$, given El Gamal encryptions of $m,a,b$, since El Gamal is multiplicatively homomorphic.  You can also prove that the El Gamal decryption of some ciphertext is in a given range (using a combination of Schnorr proofs).  Putting those two together will give your first desired primitive.

This requires you to use El Gamal encryption rather than a stream cipher.  However, if this is a problem, it is also possible to do it for other encryption schemes as well.  It is known that every statement in NP can be proven in zero knowledge using generic (but slow) schemes, so this can also be extended to work for any stream cipher.  The advantage of ZK proofs based upon El Gamal or other public-key schemes is that they can be made more efficient.

See, e.g.,

Proof of correctness of a homomorphic ElGamal sum
Is there a public key semantically secure cryptosystem for which one can prove in zero knowledge the equivalence of two plaintexts?
http://www.win.tue.nl/sedan/sedan2009/SchoenmakersSedan2009.pdf

There is tons written on this subject in the research literature.  You'll need to do more research on your own to learn this subject.  You should spend some days studying basic material on learning elementary zero knowledge proofs, first by reading textbooks, then by reading some of the classic papers.  A good starting point would be to look at textbooks on theoretical cryptography, such as
Rafael Pass and abhi shelat's lecture notes and Wenbo Mao's textbook.  You could also read http://www.austinmohr.com/work/files/zkp.pdf


Picking up what has been said in the comments:

to simplify: symmetric ciphers are like mathematical operations with 2 operands and 1 result. There is The plaintext message $m$ and $k$ as the key and they result in the ciphertext $c$. In your example, the algorithm can be cut down to a addition and modulo:

$c = (m + k) \mod k_{max}$

And of course there is a reverse algorithm (or more simply operation) that will turn $c$ into $m$ again:

$m = \begin{cases} c - k,& \text{if } c\geq k\\ c + k_{max} - k,& \text{otherwise} \end{cases}$

To sum it up: The way of calculation (the algorithm) never changes. Instead, the parameter(s) to it, the key, are different.

In the computer world these operations are much more complex and involve operations that are easy to compute in the binary system (e.g. XOR or bit-shiftig) that are rather complex to express mathematically.


Is there any quantum resistant pen-and-paper or mind cipher?

You are not likely to find such a construction. One problem you will run in to is that of size: In order to be secure against brute force search with Grover's algorithm, you will need to use at least 200 bits of secret material. And that assumes you are content with a security level of $2^{100}$.

This is equal to 25 random bytes or a 60 digit long decimal number that you will have to remember and do mental math with. In addition, you will also need to keep your message and any intermediate state in mind as well.

Assuming that your ciphertexts will be on paper or some other physical medium (because you wouldn't go through the trouble to compute AES by hand to send the result via e-mail), a quantum computer cracking your ciphertext is probably the least realistic of your concerns - if your adversary already has your ciphertext, they probably already have the messages sender and/or recipient as well, which means they have far less expensive ways of obtaining the message.


What is the purpose of the finite state machine in SNOW?

I read a little more into the 3G Finite State Machine (FSM) here.

I think that it is because the output of the FSM is dependent, not only on the state of the Linear Feedback Shift Register (LFSR), but also on the previous state of the FSM.

A filter function, such as the one used in the Mifare CRYPTO1 cipher, has an output which is entirely determined by it's input. This means that for a given output bit, there is a countably finite number of LFSR states which could have caused such an output. This type of attack is sometimes called a guess-and-determine attack. i.e. here on A5/1

The 3G FSM has an output which is dependent, not only on the state of the LFSR, but also on the previous state of the FSM. There are still a countably finite number of LFSR and FSM states which could have caused an output but the number of possibilities is combinatorially greater. The FSM was changed in SNOW 3G to include two inputs from the LFSR, rather than one, specifically to harden the cipher against guess-and-determine type attacks.

Unfortunately, quantifying why this was done, or how much better or worse it is than a filter function, is not something which is dealt with well when considering symmetric primitives.


If the adversary has the plaintext for a block, then the "current hash" can be calculated by simply performing XOR with the ciphertext block at the same position.  In that case, every block after that can be decrypted as the "current hash" and the "previously ciphered block" are now known. So the scheme seems to fail for a known plaintext attack, and is thus not IND-CPA secure.

That or "the current hash" has a meaning that you haven't told us about.


How does AWS Secret key and access key work

AWS has designed their own custom authentication algorithm. You are referencing the older signature version (v2), a newer one (v4) was released in 2014. Details are outlined here: Authenticating Requests (AWS Signature Version 4) . A major difference is that the request is not signed with the secret itself, but with a signing key which is generated using the secret. It also uses HMAC-SHA256 for signing.

  Why does AWS do this instead of asking user to upload a RSA public
  key? Why is this safer?

Using asymmetric keys would be safer since AWS would only store a public key instead of the secret, which is stored by both the user and AWS.


How long random value is required in random masking method?

Forget $s=8,$ let $s=2t$ and let $t$ be large. An answer of "yes" only means the masked quantity is uniformly distributed in some set which is brute force able if the set is small enough.

Question 1. No, the distribution of the secret plus the mask is not uniform, when the mask is uniformly chosen from $\{0,1,..,2^t-1\}.$ It is triangular. This assumes addition is mod $2^s.$

Edit: If in this question you mean the addition is mod $2^t$ with the secret from the integers mod $2^s,$ the answer is yes.

Question 2. No, and this is even worse since if you get a product divisible by $2^m$ where $m$ is the largest exponent with that property you leak a lot of information. Again this is because there is no modular reduction of the product, it being too small. Say product is 2, then either secret is 1 and mask is 2 or vice versa.

Even if you have wraparound multiplication mod $2^s$ is weak due to it being a ring with zero divisors.

2nd Edit after new comment by OP:

You won't get a uniform distribution. And the divisibility comments above still apply since in general there is no wraparound.  Except you get a wraparound to zero only if you multiply the largest $x$ and the largest $r$  obtaining $2^{512}$ which would wrap around to zero if you reduce mod $2^{512}$ (and this would leak those values).

On the other hand, you now have huge numbers, and brute forcing, even when knowing the divisibility, will take a very very long time, if not being out of reach.

Question 3. Integer arithmetic.

In general addition is better, use full length uniformly distributed masks.


If $G$ is only known to be a random permutation, and one $G(x)$ is given, that gives no information whatsoever about $x$ (it can be any element of $\mathbb F$ with equal likelihood if $G$ is uniformly random). So I would say $G$ is one-way and hiding in the sense of the question.

Things change when for the same $G$ it is considered several given $G(x)$ and perhaps $x$. In particular, knowing $G(x)$ and $G(x')$ we can tell if $x=x'$, since that is equivalent to the testable $G(x)=G(x')$.

Capturing the first situation in a game is easy: change the permutation whenever its input or output changes. But that's bound to give dull results: we're not using most of what the permutation is good for.

To capture the second situation, define the permutation early in the game, and make several rounds with $x$ or $G(x)$ varying. It's possible to establish things like: for appropriately large $\mathbb F$, given a $G(x)$ that was not previously disclosed, the computational advantage in predicting $x$ is negligible.


All ideas and suggestions are welcome on how to achieve this.

It sounds like commitments should be one way to handle it.
A commitment scheme is a method where:

Someone (person B) can generate and publish a commitment to a secret value; someone else (person A) looking at the commitment learns nothing about the secret value (we say that this is the 'hiding' property of the commitment scheme.

Later, person B can open the commitment; they publish the secret value and a proof that the committed value corresponds to the secret value (which anyone can verify).  We insist that person B cannot generate a proof to any secret value other than the one in mind when they generated the commitment (we say that this is the 'binding' property of the commitment scheme.

In your case, person B will initially generate a commitment to the number he has in mind.  Then, when person A has published his guess, person B will open the commitment, and show whether person A's guess to the secret value was correct or not.
The simplest commitment scheme is a hash based commitment; to generate a commitment to the value X, person B would select a fixed size random value r and publish $\text{hash}( r || X )$ (where $\text{hash}$ is a collision resistant hash function, such as SHA256 or SHA3); to open the commitment, you would publish $r$ and $X$.  This is simple, however sometimes you need more from your commitment scheme (such as the ability to generate proofs about your commitments, for example, that the committed value is not the value that person A guessed (without revealing the correct value); if so, then Pedersen commitments make that a lot easier.  I don't know enough about what you need from a commitment scheme to advise you which way to go.


6 Byte for HMAC in wireless system secure?

Is bruteforce possible when transmitting a single wireless package will take 7ms? If an attacker do a bruteforce attack it will take $2^{48} * 0.007  /\  60 /\ 60 /\ 24/\ 365 = 62478.59\ years$ . So my assumption is that this system is secure if secure_hashfuncion is a cryptographically secure hash function.

Actually, I would look at it this way; if the adversary injects a packet, it has a probability $2^{-48} \approx 3.55 \times 10^{-15}$ of being accepted; the attacker can increase this by (say) a factor of a million by using a million packets (which he could do over the course of a couple hours).

Is this "secure"?  Well, that'd depend on your required level of security.  If the effect if the adversary was successful was an ICBM launch, I'd say that we'd want to security to be better.  However, if you're protecting a VoIP stream, and the effect would be to replace a 10msec sound segment, it'd probably be good enough.

  Is there a hash algorithm that is cryptographically secure (only brute-force attacks possible) with a 6 byte output?

For MACs, there are two possible attack approaches; one is to guess the MAC (as above); the other is to try to recover the key.  If you believe that you are sufficiently secure against the first attack, well, there certainly are MACs that are secure against key recovery attacks.

The only caution would be that there are MACs that, once you've found a forgery, make it easier to find other forgeries; GMAC is one such example.  For this application, I'd stay away from that, and use one that doesn't have such a vulnerability; such as HMAC or CMAC [1].

  Can I maybe just use SHA-1 and only use the first 6 byte output?

You'd have to stir in the key somehow.  Now, I suppose you could hash the key and the message together (we typically don't because of length extension attacks, which do not apply because of your truncation); however unless you need to minimize computation, I'd still advise you to use a more traditional MAC, such as HMAC (such is close to what you are proposing), or CMAC.

[1]: CMAC does have that vulnerability, but only if the attacker guesses the entire 128 bit tag; guessing a truncated version (without getting the rest of the bits right doesn't help him)


A generalisation of Shannon's theorem of perfect secrecy

Assume for the sake of contradiction that $|K|<(1-\epsilon)|M|$. We will define an adversary which has semantic advantage greater than $\epsilon$. Let $S=\{D(k,c)|k\in K\}$, where D is the decryption function of our cipher $\mathcal{E}$. We define our adversary A with the following characteristics:

$m_0,m_1\in M$ are chosen randomly
The predicate $\phi$ is chosen randomly with equal probability from either $\phi_1$ and $\phi_2$, which we define below
If $m_0\in S$ and $m_1\not \in S$, then $\phi_1(c)=\phi_2(c)=0$.
If $m_0 \not \in S$ and $m_1 \in S$, then $\phi_1(c)=\phi_2(c)=1$.
If both $m_0$ or $m_1$ are in S, then $\phi_1(c)=1$ and $\phi_2(c)=0$

(Note that while such a predicate function exists, it might not be an efficient one, ergo the part of the problem statement allowing for computationally unbounded adversaries.)
We have the following:
$$Pr[φ(E(k, m_1))]=Pr[\phi=\phi_1]Pr[m_0 \in S\; \text{and } m_1\in S]+Pr[m_0\not\in S \text{ and } m_1\in S]$$
$$Pr[φ(E(k, m_0))]=Pr[\phi=\phi_2]Pr[(m_0 \in S\; \text{and } m_1\in S)]$$
Note that both probabilities are implicitly conditioned on S, which depends on the message the challenger encrypts and sends to the adversary. Also, $Pr[\phi=\phi_1]=\frac{1}{2}$, since we chose our predicate function randomly. Moreover, in the first case $E(k,m_1)\in S$ trivially, and in the second case $E(k,m_0)\in S$, yielding that
$$Pr[φ(E(k, m_1))]=\frac{1}{2}Pr[m_0 \in S]+Pr[m_0\not\in S]=\frac{1}{2}\frac{|S|}{|M|}+1-\frac{|S|}{|M|}$$
$$Pr[φ(E(k, m_0))]=\frac{1}{2}Pr[(m_1\in S)]=\frac{1}{2}\frac{|S|}{|M|}$$
So that $SSadv[A, \mathcal{E}] = 1-\frac{|S|}{|M|}$. Now $|S|\leq |K|$ by definition, and so by our assumption at the beginning $|S|<(1-\epsilon)|M|$. Therefore, $SSadv[A, \mathcal{E}]>\epsilon$, which is a contradiction, meaning that $|K|\geq (1-\epsilon)|M|$ as desired.


This is called a proof of retrievability or provable data possession (slightly different definitions for these two concepts). You will find many papers discussing constructions. Two of the most cited papers in this area are:

Shacham & Waters: Compact Proofs of Retrievability
Ateniese et al: Provable Data Possession at Untrusted Stores


How to perform the modular reduce of Rijndael's finite field


Does there exist a proof-of-retrievability scheme that is publicly-verifiable, limited-use, and does not use homomorphic encryption?

I do not know of any approaches in context of proofs or retrievability (PoRs)/provable data possession (PDP) that use homomorphic encryption. However, many of those schemes employ homomorphic (linear) authenticators/tags for the metadata such that the proofs delivered by the server can be of constant size, i.e., by aggregating single tags.

Now to some misunderstanding regarding the type of verifiability:

Public verifiability in this context means that the data owner who initially outsources the file is the only entity that can modify the data, but a third party, which is given some public information, can only verify a proof from the server that the data is available, i.e., check that the data is still available/retrievable.

Consequently, public verifiability always involves some secret that is only known to the data holder (who creates the file and metadata and may modify the stored data and the corresponding tags) and some public information (corresponding to that secret) that can be given to some third party such that it can trigger proofs for availability of the data (but cannot modify/replace the data). Thus, the party in possession of the public information can only check if data is available, but can not modify already stored data in such a way that a proof after modification of the data will still succeed.

As a consequence, MAC based PoRs/PDP schemes, which are essentially the same but have different security models, can never achieve public verifiability as it is defined in this setting, as it would require to share the respective secret (and this allow modifications). The same holds for any secret key only scheme.

Clearly, the use of a privately or publicly verifiable scheme to allow another third entity (distinct form the data holder) to request and verify proofs from the server depend on your trust model. Public verifiability assumes that the third entity is semi trusted, i.e., only trusted to conduct the proofs honestly, but you do not trust the third party that it wont modify the stored data. If you fully trust the third party, i.e., you are sure that it will not modify your data unauthorized, you can also use a privately verifiable scheme and simply give away your secret to the third party. However, this is a quite strong assumption.

Typically, such PoR/PDP schemes are either private verifiable or public verifiable. But there are also protocols which achieve unbounded private and public verifiability at a quite low cost simultaneously (based on the same metadata/tags). You may look here for such a scheme. However, it is based on pairing friendly elliptic curves and may not be that straightforward to understand as you say your knowledge is quite limited.

A very simple and easy to understand privately verifiable but bounded use scheme is presented here, but it does not support public verifiability as discussed above. Nevertheless, it is easy to implement and may be sufficient for your purpose.


Zero knowledge proof in smart parking managment systems

I believe the answer lies in section 4 of the paper, titled "Privacy preserving outdoor parking management".

The authors explain the details of ZKP schemes later on, as well as the libraries they used and curve parameters chosen... which explains the "how" pretty clearly.

My understanding of this paper is that the the possession of secret information (e.g. personally identifying information) of a parking client is to be proven to the parking system operator in zero knowledge.

I would also add that they mention both interactive and non-interactive versions of ZK protocols. So in that case, only the prover sends a (single) message to the verifier, e.g. for the modified Schnorr protocol (5.3). Again, the client is the prover and the parking system is the verifier in this application, for this non-interactive scheme.


You have to split your file in such way that each block will be smaller then prime $p$ you're using. After that you have $n$ such blocks.

You calculate $\sigma_i$ for every block so $i \in \{1,2,...,n\}$ and $m_i$ means block number $i$

Example:

  Assume you're working in field $Z_p$ with $p=2^{255}-19$ (used in Curve25519 for example) and your file is 254 bytes or $254 \times 8$ bits long. In practice you can split it to blocks of (at most) 254 bits as $2^{254} \ll 2^{255}-19$. You can split your file to 8 parts, each 254bits long. So you have $n$=8, and each $m_1,m2,m3,m4,m5,m6,m7,m8$ are respective blocks from file.

Example2:

  Assume you're working in field $Z_p$ with $p=2^8+1$ and your file is 5 bytes long. You can split it to blocks of 8 bits as $2^8 \lt 2^8+1$. So you have 5 such parts and $n=5$ and $m1,m2,m3,m4,m5$ are respective bytes from file.

Please note that second example is in no way secure as target field is way too small.


Password strength is typically measured in bits of entropy, or in layman's terms, the amount of "true randomness" in the system. This is measured by the process of how the password is generated rather than by the number of bits in the output. It's a simple extension of Kerckhoffs' principle: assume your attacker knows your process, and the only information unknown to him/her is the secret key.

You are correct that the number of permutations of the passphrase is $2000^7$. This is about equal to $2^{77}$, so a password generated with this approach has about 77 bits of entropy, which is a very good password strength. However, passing the output through a digest function like MD5 doesn't actually increase the number of possible permutations. MD5 has $2^{128}$ possible outputs, but we're only actually using $2^{77}$ of them. Put another way, assuming an attacker knows our process, they don't have to guess all possible MD5 outputs; they only have to try ones that correspond to a hash of 7 of the 2,000 most common English words. And that's comparatively much easier to do.

In practice, however, 77 bits of entropy is still quite good for a password. MD5 doesn't add any strength in and of itself but it doesn't necessarily remove any either. As an "encoding" (assuming you're using a 32-character hex representation) to stuff seven random words into a field restricted to 32 characters (and frequently to only alphanumeric values), it appears to me to be practical.

One slight improvement would be to use Base32 encoding for the binary MD5 output instead of hexadecimal. This would reduce the length of the output to 26 characters (by allowing for uppercase letters as well) and could allow you to use this scheme for password fields limited to fewer than 32 characters.

Edit: Others have expressed concerns about weaknesses in MD5. While I also share a general distaste for MD5, I believe this use is perfectly acceptable. It is not being used for its preimage resistance here, because the attacker has no need to determine the original seven words that were used; having the hash itself is good enough. Given that both the chosen words and the MD5 hash itself are considered secret, I don't believe there is cause for concern.


To better understand the below concrete answers, a short background on how disk encryption is usually performed with AES. The most tools will use one of the following two modes:

CBC-ESSIV, which is just standard CBC encryption where each sector is one "message" and the IV is derived deterministically from the index of the sector to be encrypted as $\text{IV}=E_{\operatorname{Hash}(K)}(\text{SID})$ where $K$ is the AES key.
XTS which is the more modern choice because it doesn't suffer from CBC's malleability essentially turns AES into a tweakable block cipher and using a different tweak for data block to hide equal blocks.

  [How] does it relate to sector sizes on the drive which is typically 512 bytes?

The sector size usually must be a multiple of the block size of the underlying cipher so no space is wasted to padding and stream modes don't have to be used (which break even more horribly than CBC under chosen-ciphertext attacks).

  [Who] or what is responsible for dividing disk sectors into data blocks?

The disk encryption software will usually divide the 512-byte blocks into 32x 16-byte blocks for the AES encryption.

  Does it mean that I will use the same key to encrypt all sectors?

Yes.

  Or maybe this key is used to calculate/derive sectors keys/block keys?

No. However in ESSIV mode (see above) a hash of the key is used to generate CBC IVs.


What is the effect of the different AES key lengths?

For symmetric algorithms (like AES or DES or RC4 -- but not for RSA or ECDSA), a key is a sequence of bits, such that any sequence of bits of the same size is a potential key. So longer keys means more possible keys.

Exhaustive search is about trying all possible keys until a match is found. It is an absolute limit to the strength of an algorithm: exhaustive search is always applicable, there is nothing an algorithm can do against it. The only defence against exhaustive search is to expand the space of possible keys, i.e. have longer keys. Fortunately, this is very effective: the largest exhaustive search experiment which was ever reported to have been performed was for a 64-bit key (a search for a 72-bit key is underway, but not completed yet). Traditionally we use "80 bits" as the practical limit, but technology improvement may force us to increase that. Every additional bit doubles the hardness of exhaustive search. See this answer on security.SE for some additional discussion. Bottom line: 128 bits are safe.

It is somewhat delicate to compare strengths of 128-bit and 256-bit keys: while the latter is a much wider key space, the former is already in the "can't break it" zone, and you cannot get better than that, practically speaking. Thus, stating that AES-256 is stronger than AES-128 would be kind of abusive.

There are a few gotchas:

DES uses 64-bit keys (and 3DES uses 192-bit keys). However, the algorithm specification is such that DES totally ignores 8 of the 64 key bits (24 ignored bits for 3DES). Thus, the key size of DES is often said to be 56 bits (168 bits for 3DES).
AES morphs with the key size: with a longer key, there are more rounds. This is not about exhaustive key search; this is because a longer key is a promise of "higher academic strength" ("academic" means "we assume that the attacker can perform 300-bit exhaustive searches"). In an academic way, AES needs exhaustive search to be the best attack (i.e. attacks on the algorithm internal structure must be slower). A 256-bit key raises the bar: the non-exhaustive-search attacks must not be more effective than $2^{256}$ work factor. Hence the extra rounds. In practice, the extra rounds do not buy you more security (just like the larger key does not make the algorithm really less breakable than the already unbreakable AES-128); what the extra rounds do is that they make encryption 40% slower.
When an algorithm morphs with the key size, this is no longer "the same" algorithm, so anything goes. AES-256 could theoretically have weaknesses that AES-128 does not have (there is no guarantee that the extra rounds do not harm security).
Symmetric key size is very rarely the weak point of a system which uses cryptography. If you use 64-bit keys and that key size is indeed the best attack point, then you can consider yourself extremely lucky: the rest of the system must be inordinately robust.


A Flaw

If you try working through your example concretely then you should see at least one issue with decoding.  Consider values mod $8$:

$
A = { 3 } \\
B = {7}   \\
secret = {5 }
$

Using your equations we have:

$
Q = 3 + 7 + 5 = 7 \\
U = 3 - 7 + 5 = 1
$

And for decoding:

$
B = (U - Q) / 2 \\
B = (1 - 7) / 2 \\
B = -6 / 2 ({\text mod} 8)
$

But what is $\frac{-6}{2}$ modulo 8?  How do we get a unique answer here?

Alternatives

Your constraints are a little unclear, but if you're OK with storing $(1 + {\text nrImages})*|{\text image}|$ (A, B, and secret) then use linear integer secret sharing in a traditional manner (below). Obviously this is a little silly seeing as you could use any symmetric encryption algorithm, given that you have a secret.

If you only want to store ${\text nrImages}|image|$ data, and not the secret, then that is harder as you'll have to derive the secret from the combined shares.  For example we could have a small feistel network:

$
Q0 = A + PRF(B)  \\
U  = B + PRF(Q0) \\
Q  = Q0 + PRF(U)
$

Now $U$ and $Q$ are your secrets, protected ONLY by the entropy of A and B and the strength of your PRF.  The entropy in the images could actually be increased without visually altering the typical image.

To decrypt:

$
Q0 = Q - PRF(U)  \\
B  = U - PRF(Q0) \\
A = Q0 - PRF(B)
$

Basic application of LISS

For LISS just generate a random secret, $s$, and compute:

$
Q = A + B + S \\
U = B + S
$

Then, once the shares and the secrets are collected, you can reverse the process via:

$
A = Q - U \\
B = U - S
$


How can I tell how many bits of security a secure hash function has?

Well, how resistant to attack would depend on what security properties you would need from it.

There are three standard assumptions we can make about a hash function:

Given a hash value, it is difficult to find an image that hashes to that value; this is known as preimage resistance
Given a image that hashes to a specific value, it is difficult to find another image that hashes to that same value; this is known as second preimage resistance.  This is considered a stronger assumption than preimage resistance, because it may be possible to modify the image and not change the output value.
It is difficult to find two different images that hash to the same value; this is known as collision resistance.

Sometimes we're interested in collision resistance, sometimes, we're not.  One example where we may be interested in it is if we're using the hash as a part of a signature scheme.  For example, suppose we find two images that hash to the same value; one says "I like icecream" and the other says "I agree to give Bob a million dollars".  We then get Alice to sign the message that denotes that she likes icecream; because what the public key system signs is actually the hash, Bob now hashes a signed message from Alice giving him a million dollars.

Now, there are other times where we don't really care about collision resistance.

So, what's the big deal about collision resistance vs. preimage resistance?  Well, it turns out that, if we don't assume any cryptographical weaknesses within the hash function, it is much easier to break collision resistance than it is to break preimage (or second preimage) resistance.

To break collision resistance, one way would be for the attacker to hash a huge number of variants of the message "I like icecream", and hash a huge number of variants of the message "I agree to give Bob a million dollars", and go through the lists and see if there's a value in common.  For a 160 bit hash, we need about $2^{80}$ messages in both of the lists (because of the Birthday paradox, that's likely to be sufficient); it turns out that this is about the best we can do (assuming no crypptographical weaknesses within the hash), and hence we have about 80 bits of security against this attack.

On the other hand, to break preimage (or second preimage) resistance, we can't use the Birthday paradox.  Instead, about the best we can do (barring a weakness within the hash function) is to hash lots of messages, and hope we get one that hashes to the target value.  For a 160 bit hash, we expect to go through about $2^{160}$ messages before we stumble across one, and hence we have about 160 bits of security against these.


How effective is Serpent-256 in CTR mode?

Any block cipher within CTR operates the same way; CTR security is only dependent on the block size. Serpent was one of the candidates to become AES. It is thought to have a high security margin (and no weak keys etc). None of the currently known attacks seem to have done much damage to the security claims.

All AES candidates have a block size of 128 bit and a key size of 128, 192 and 256 bits (at least). In your case you just list two key sizes, 128 bit or 256 bit as difference. The higher key size is more secure. As the number of rounds of Serpent doesn't change the greater sized key should be preferred, although the strength of the password is much more important.

In the end, an algorithm is effective when it handles your specific requirements. And in general, the security of the system is very likely not much influenced by the choice of Serpent as block cipher (especially if timing attacks are hard to do such as with file encryption, hardware implementations of AES such as AES-NI may have a small advantage with regards to timing based attacks, besides the obvious performance benefit).


Pedersen commitments, what happens if I choose $H$ such that $H = a\times G$?

If the committer knows $a$, then it is no longer binding.

For any $m$ you commit, the commitment will be $(m+a)G$, so it is easy to find $m'$ and $a'$ such that $m'+a'=m+a$ to open the commitment.

Edit to add:
If the receiver knows $a$, then it is still information theoratically hiding because the sender chooses $r$ which is uniformly random.


Is a random circuit likely to compute a one-way function?

The claim that you remember is to good to be true. It is yet unknown (because the question P ?= NP is still open) whether there are one-way functions. If the claim you remember was true, it would prove the existence of one-way functions.

P.S. While P = NP excludes the existence of one-way functions, even with P != NP the existence of one-way functions is still an open problem.


Proving the semantic security of the One Time pad

The proof for the perfect secrecy property of the one time pad is quite simple.

It makes use of basic probabilities and it says that:
 $$Pr[M=m|C=c]=Pr[M=m]$$ for a probability distribution M$\{0,1\}^n$ for the message space and a probability space C for the ciphertext space.

Proof:

$$Pr[C=c]=\sum{Pr[C=c|M=m']\cdot Pr[M=m']}
=\sum{Pr[K=m'\oplus c]}\cdot Pr[M=m']
=\sum{2^{-n}}\cdot Pr[M=m']
=2^{-n}$$
(from bayes theorem)$$Pr[M=m|C=c] = \frac{Pr[C=c|M=m]\cdot Pr[M=m]}{Pr[C=c]}
= \frac{Pr[k=m \oplus c]\cdot Pr[M=m]}{2^{-n}}
=\frac{2^{-n}\cdot Pr[M=m]}{2^{-n}}
=Pr[M=m]
$$

What the last equation states, is the following:
The success probability of an attacker to correctly guess the plaintext m by inspecting its ciphertext c is equal with the probability of correctly guessing the message without obtaining its ciphertext. The latter argument is the perfect secrecy property.

Perfect secrecy is hard to achieved in real world due to its two constraints:

It's one time: the key should be used only for 1 encryption
The key should be as long as the underlying message

So people started to think:"...hmmm maybe we can weak this security definition in order to be more efficient in practise...". And they end up with the computational semantic security which relaxes the perfect secrecy as follows: No polynomially bounded adversary can with non negligible probability infer any information from the ciphertext. This is the semantic version and the indistinguishable version states that no polynomially bounded adversary can with non negligible probability distinguish two ciphertexts.

In real world the second drawback can be mitigated with the use of pseudorandom generators that very briefly take as input a short "random" looking seed and produce a longer pseudorandom number that is indistinguishable from random. In order to come up with the proof following the reductionist approach for the security of the one-time-real-world pad we substitute the key k with the outputs of a PRG and we make the assumption that PRG outputs are indistinguishable from random. The proof now for its semantic security (which is equivalent with IND security) proceeds as follows:

Assuming that $\mathcal{A}$ breaks the semantic security of our OTRWP attacker $\mathcal{B}$ that tries to break the security of the PRG will use it to break PRG security. If we manage to do so we will end up in a contradiction so the truth statement would be that OTRWP is secure. Let's see how it briefly works:
Whenever $\mathcal{A}$ is asking for encryption of messages m the attacker $\mathcal{B}$:

Gets the output of the PRG when it is fed up with a seed that comes from a uniform distribution.
Gets the output of the PRG when it is fed up with a pseudorandom seed.

We made the assumption that PRG is pseudorandom so the success probability of $\mathcal{B}$ distinguishing between 1 and 2 is negligible:
$Pr[|PRG_{pseudorandom seed}-PRG_{uniform seed}|]=neg(1^k)$
But $Pr[PRG_{pseudorandom seed}]$ is exactly equal the probability of the OTRWP for attacker A and $Pr[PRG_{uniform seed}]=1/2$ because it is independent from the view of $\mathcal{A}$.

So:
$$Pr[\mathcal{A}^{OTRWP}]=neg(1^k)+ 1/2$$
which concludes the proof.


The basic idea is to take random (Gaussian) integer combinations of the given LWE samples, and add a little "smoothing" noise.  This will result in new samples which are statistically close to LWE samples with the same secret, but with a somewhat wider error distribution (by a factor of $\tilde{O}(\sqrt{n})$ for typical parameters). This is essentially Regev's classical BDD-to-LWE reduction on the special family of Ajtai lattices.

More precisely, given LWE samples grouped as $(\mathbf{A} \in \mathbb{Z}_q^{n \times m}, \mathbf{b}^t = \mathbf{s}^t \mathbf{A} + \mathbf{e}^t)$ where $m \approx n \log q$, generate a new sample as $(\mathbf{a}' = \mathbf{A} \cdot \mathbf{r} \in \mathbb{Z}_q^n, b' = \mathbf{b}^t \cdot \mathbf{r} + \tilde{e} \in \mathbb{Z}_q)$, where $\mathbf{r} \in \mathbb{Z}^m$ and $\tilde{e} \in \mathbb{Z}$ have discrete Gaussian distributions of appropriate parameters.  One can show that with high probability over the choice of the original $(\mathbf{A}, \mathbf{b})$, the distribution of $\mathbf{a}'$ is nearly uniform.  Moreover, conditioned on any fixed choice of $\mathbf{a}'$, the distribution of $\mathbf{e}^t \cdot \mathbf{r} + \tilde{e}$ (which is the "error" term in the output sample) is close to a discrete Gaussian.

This procedure is sketched in Gentry-Peikert-Vaikuntanathan, "Trapdoors for Hard Lattices..." (for the tight security proof of the IBE), and is done more formally in Applebaum-Cash-Peikert-Sahai, "Fast Cryptographic Primitives..." (as the encryption algorithm for the KDM-secure public-key scheme).


Does Cut-Choose technique for yao garbled circuit provide statistical security?

Cut-and-choose is not a specific protocol that we can analyze, but a general technique whose details can be realized in many ways.

The basic idea of cut-and-choose is to generate many garbled circuits, open some of them to test for correctness, and evaluate the rest. The goal is to ensure that most (or, in some protocols, at least one) circuits used for evaluation are correct. If this condition holds, even of those "correct" circuits were generated by a corrupt garbler, there is no problem. Furthermore, the analysis of how many circuits to generate/open doesn't consider the running time of the corrupt garbler. It is a purely statistical argument. So this central idea of garbled circuits is naturally safe in the presence of an unbounded garbler.

But there are other parts of a "cut-and-choose protocol":

The garbler must provide garbled inputs to the receiver, using oblivious transfer (OT). Naturally the OT protocol must be secure against an unbounded sender, and this is possible.
The protocol must prevent the garbler from using inconsistent inputs across different garbled circuits. Different protocols vary widely in how they realize these properties. I believe that some are secure against an unbounded garbler, and probably others are not.
The protocol must prevent the garbler from causing the receiver to abort with input-dependent probability. Again, whether this is safe against an unbounded garbler depends on how the mechanism is realized. I think that some techniques are safe and others are not.


Truth table for the Boolean function $f(x,y) = x \oplus xy$ - Conflict with answer computed by sagemath

The truth table
\begin{array}{|c|c|c|} \hline
x & y & xy & x \oplus xy \\ \hline
1 & 1 & 1 &  0 \\ \hline
1 & 0 & 0 &  1 \\ \hline
0 & 1 & 0 &  0 \\ \hline
0 & 0 & 0 &  0 \\ \hline
\end{array}
and you can use Boolean formulas
f = propcalc.formula("x ^x&y")
f.truthtable()

outputs
x      y      value
False  False  False
False  True   False
True   False  True
True   True   False


The difference values in the diagram denote the differences going into and coming out of the round function, which only operates on half of the state.  The differences of the two halves of the state are not shown after every round - you have to infer them from the 'omega' differences at the top and the output differences of the round functions.

Note that the difference going into the first round is 00 00 02 02x.  In a Feistel cipher, the input to the round function is a copy of one half of the state - the half that is not modified by the round function.  So that means after the first round, one half of the state still has that same difference (although at the end of the round that half of the state is swapped with the other half).

Now note that the output of the second round function is also 00 00 02 02x.  The output is xored with one half of the state, which is the same half that was copied and used as the input for the first round.  Since the differences are the same and xor is its own inverse, the two differences cancel out.  So now half of the state has difference zero.  The other half still has difference 00 80 02 82x.

The two halves are swapped again, and now the half with difference zero is used as the input for the round function.  But since an input with zero difference always generates an output with zero difference, the diagram shows zeroes in the inputs and outputs of the round function with probability 1.  Do note however that there is still an active difference in the whole state, just not in the half that was copied and used as the input to that third round.

In terms of your second question, these differences are discovered by carefully examining the round function - decomposing it into smaller functions (e.g. s-boxes), examining the difference distribution tables of those smaller functions, and watching how differences from the smaller functions interact in the whole round function.  For extending this over several rounds, attackers typically compile a list of the highest probability single round differentials, and then try to stitch together a high probability multi round characteristic from those.

For ciphers like FEAL, attackers generally look for high probability iterative characteristics, which are difference trails that stretch over a handful of rounds but which have the same initial and final states (just like in the diagram).  Such iterative characteristics enable the attacker to break many rounds, simply by repeating the characteristic as many times as necessary.


What part of an RSA key is referred to by the number of bits?

See https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29

Under Key Generation:

Compute n = pq.
    n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length.


Is this problem based on a known hard problem?

This problem hugely depends on the distributions of the $c_{(i)}$, if they are independant or not, also on the size of the space in which each coordinate of the vectors are, and on the information you gain with each check if $c_{(i)}$ is correct.

Assuming the vector space is $Z_q^n$ and $n$ is polynomial in $\log q$, that $c_{(i)}$ are independant and uniformly distributed, and that your verification algorithm only tells you if $c_{(i)}$ is correct or not, let us look at the problem for one instance of $a$, $b$ and $c$.

If you take $b$ uniformly at random, you have probability $\frac{1}{q}$ to have $⟨a,b⟩=c$, which is exponentially small.

Moreover, there is no way to improve brute force on the value of $⟨a,b⟩$ because you don't learn anything beside the correctness of your $b$, so this is a problem you would call hard is cryptography.
Even if you have a polynomial number of instances, this won't help you that much because finding a $b$ such that even only one $⟨a_i,b_i⟩=c_i$ is already exponentially hard.

Of course, this is an information theoretical approach to the complexity of this problem, and I think the real assumption you want to reduce to is one that would allow you to use my results, i.e. an assumption which makes you learn nothing when you verify $⟨a,b⟩=c$.

I know this is not really a reduction, but that's all I've got to help you, I hope it is enough.

Let me edit to reply to yours.

First, say you have $q$ groups of $a^{(i)}$ and $c^(i)$.

Now if you know $c$, you are just asking to solve a system of $qn$ linear equations with $n^2$ unknown. Now I think the subject is quite known and you can find a lot of documentation on it easily.

Remark that $B$ being an orthogonal matrix corresponds to adding $n$ equations to the system. Even though they are no more linear, I think the subject has already been studied.

As for the complexity questions, if I'm not wrong you can solve the problem with an algorithm running in time polynomial in $n$, so one would consider it easy.


RSA: revealing the modulus factorization by choosing a bad message

Firstly, it's not co-prime to the modulus, so $\gcd(m,N)$ would be greater than $1$.

Secondly, $N$ is the product of two (and only two) prime numbers $p$ and $q$, so if $\gcd(m,N)>1$, then you know $m$ is one of the factors (and prime factors) of $N$.


Since it gives negative power, how is rcon(0) calculated in AES?

See my previous answer here regarding rcon calculation:

Rijndael: explanation of Rcon on Wikipedia?

It is essentially caulcated by division of 0x01 within the finite field.

The most important thing about rcon(0) is that there is no round 0, and thus you will never actually use it in any calculation. Also take note of my comment that the Wikipedia page is not completely correct. I will probably edit the page if someone else does not get to it first.


Is it a bad idea to use PGP encryption for structured/predictable data?

There are no known-plain-text-attacks known for the symmetric encryption protocols used by OpenPGP with the OpenPGP CFB mode in use, so you can safely rely on it.

In the end, the very first few bytes of OpenPGP packets are generally rather easily guessable by design, as they usually introduce a compression-packet and literal (data) packet with either very small parameter ranges each -- and this is not considered a problem for OpenPGP but for some very esoteric and hardly usable adaptive cypertext attack relying on a decryption oracle, that is partially exploiting this.


Protection of Elliptic Curve Implementations against side-channel attacks

It all comes down to your threat model, right? Just because an implementation is done in hardware does not mean that power and fault attacks must be considered. If I host the hardware in my secure facility with armed guards at the door, but the hardware is connected to a machine which is connected to the internet, I might feel that it is okay to not be concerned about power and fault injection attacks. On the other hand, if my hardware is being deployed "behind enemy lines" where it could be captured, you better believe that I should be worried about those sorts of attacks.


Do we have to consider the cryptographic properties of the decryption, if we're only using the encryption?

Diffusion is a requirement for a secure cipher, but it is not by itself sufficient. So even if a certain number of rounds has "full diffusion", it does not mean that the number of rounds is enough. In the case of Treyfer, the decryption direction requires five more rounds for full diffusion, but the suggested number of rounds is much higher at 32. (Even that is not really secure, because the key schedule is broken.)

However, if considering block ciphers more generally the question is whether a block cipher can be secure in the encryption direction without being secure in the decryption direction. The answer is probably yes. For example, Luby and Rackoff showed that a three round Feistel network with a secure PRF is secure against adversaries without access to a decryption oracle, but needed four rounds to prove security against adversaries with such access (which they called strong PRP).

So there seems to be a security difference between a block cipher used only in the forward direction and a block cipher used in both directions.


Which block ciphers are considered staples for constructing hash functions?

Block ciphers used in hash functions built per the Merkle-Damgård structure with a Davies-Meyer compression function (e.g. MD5, SHA-1, and SHA-2) have special requirements:

They must have a wide block (data input and output): as wide as the hash, thus twice the security (in bits) if collision-resistance is a consideration. For 128-bit security, we thus need a block cipher with a 256-bit block. This disqualifies all three variants of AES, and many earlier block ciphers.
They must be immune to related-key attacks, which normally are of secondary concern in block ciphers. This disqualifies DES when viewed as a 64-bit key block cipher (and makes it clumsy when viewed as a 56-bit block cipher), and TEA (Microsoft used it anyway in the original Xbox, and got pwned).
For best efficiency, they need a wide key input (at least twice the block size is typical), and high key agility (low computational effort to change the key). This disqualifies some block ciphers.

The block ciphers used thus tend to be built for the specific use, and designated as the block cipher of their associated hash. An example is SHACAL.


This is actually a rather interesting question whose solution is obvious to all cryptographers, but I guess nobody cared yet to write it down.

After all, our computers that generate secret keys (not just GPG / RSA) are deterministic machines. These deterministic machines implement well-defined routines to generate keys of well-defined format which are later published and serve as an "image" of the function generating the keys. Note that this question can be extended to all ciphers, like good old symmetric encryption and message authentication codes because there you can verify your guess for the start value of the procedure just as easily.

Now for the two parts of your question as I see it:

The algorithm is deterministic and thus it should be possible to reproduce it
The algorithm is well-defined and thus it should be possible to work it backwards ("backtrack it")

To understand the specific case of GPG we need a brief overview of how the algorithm works:

Take a large random value and convert it to an integer
Test if the integer is prime (with high probability)
Repeat the first two steps until two primes were found
Multiply the primes together, this is (along with another constant) is your public key output
The primes now form the secret key (along with a "counter-part" to the above "constant")

As you can see, inverting the algorithm would imply actually factoring the public key modulus. However this is computationally impossible for classical computers for sufficiently large primes ($>2^{1000}$), so you can't backtrack the algorithm.

But how about guessing a starting value for the randomness and then trying all options out? Well, it turns out this doesn't work, because while you could try to guess the random values, each has $2^{128}$ or more possible values and as such you can't try them all out using a classical computer during a human life-span.

Wait, didn't we establish that computers are deterministic, so why is there more than one possible value!?
Computers are indeed deterministic, but the things they use and the things that use them aren't deterministic. Computers take that randomness and "compress it" into short byte strings, which are then used to derive the "large random values" I talked about. So, where does this randomness come from? It could be random keystrokes by the user, network timing, CPU scheduling times, HDD delays (which are created by the air in the HDD cases), mouse movement by the user and actual random number generators which are fed by physically random processes (similar to the Double-slit experiment and other quantum events).


Stream cipher and block cipher usage in network data encryption

In L3 ad L4 security protocols (IPSec and SSL) block ciphers are preferred (AES-CBC).

Errr, no.  Originally, SSL used RC4 (which is a stream cipher); then CBC mode (first DES/3DES and then AES) was added.  In the latest version (TLS 1.3), they discarded RC4 and CBC mode entirely, in favor of AEAD modes (GCM and Chacha20/Poly1305).
As for IPsec, it was originally CBC mode only (first DES/3DES and then AES).  Later, they added AEAD modes, and I believe they are currently the most common.
Hence, your claim that AES-CBC is preferred is not currently accurate, and so the assumptions behind your first question is not relevent.
Your section question is still interesting:

What makes voice data (which is application layer data) suitable for stream cipher? Isn't it easier to divide the voice stream into blocks and encrypt it with block cipher?

With voice, they tend to be quite sensitive to encryption overhead; the VoIP packets themselves are quite tiny (circa 20 bytes on average, IIRC), and so a fixed amount of overhead would be a larger fraction of the total overhead than, say, in TLS.  In addition, VoIP often goes over wireless, and they are especially sensitive to bandwidth there (in large part because of power; transmitting more bytes uses more power).  What this means is that VoIP encryption protoocols (such as sRTP) are designed to minimize encryption overhead over just about any other consideration.
Hence, modes that require padding (such as AES-CBC) would be rejected outright, in favor of modes that don't (such as AES-CTR).


Does a bigger key mean more security - if we do not change the structure of the algorithm?

Generally speaking, more than 128 bit security is not required - except maybe for protection against multi-target attacks where large amounts of ciphertext become available to the adversary. The reason for this is that no system will be able to perform $2^{128}$ operations. So if there is an analysis that threatens the structure or number of rounds used, then increasing the rounds or updating the algorithm will likely strengthen the security of the cipher more than increasing the key size.
Quantum computers are not really an exception to this but because of how they work, they often have a different value for the security in the first place. So for a block cipher you can generally assume that Grover's algorithm reduces the security for quantum computers to 64 bits. For this you'd need a full fledged quantum computer with enough qubits and error correction, not the expensive toys we have now.
Still, that means that upgrading to 256 bit security may be a good idea, so that 128 bits of security is restored when considering quantum computing / multi-target attacks. Going higher doesn't make much sense. If it is smart to increase the number of rounds depends on the algorithm. Maybe a conservative number of rounds was already used. On the other hand, the extension of the key schedule may require that more rounds are used. A good example is of course AES, where 10, 12 or 14 rounds are used depending on the key size.
This might not be necessary if the internal state and / or number of rounds is large enough already. But please be aware that HKDF is not an efficient way of expanding keys. You don't want a very heavy key scheduler because of the amount of instructions (which in turn mean gates when using an hardware implementation) required to execute it. And HKDF would also be considered way too compute intensive during initialization. This may be fine in your situation, but it doesn't work for a generic cipher.


Government root SSL certificate possible vulnerabilities

First - please REALLY check the certificate, download it, open and have a look into details (4096 bit, 30y validity). I don't think your government wants to be insecure themselves (so other parties will act on behalf of it).

If the certificate is to be used as a root (or issuing) certificate for other nationally issued certificates, you need it to be trusted (otherwise all national sites won't be recognized as trusted). It cannot be used to decrypt your traffic (as man in the middle) itself.

The only question to be answered, how trustworthy is the "Qaznet" issuer. Nothing prevents them (except the law and they would loose all credibility) to issue e.g. a google server certificate which will be trusted to all having the root / intermediate certificate as trusted (see http://arstechnica.com/security/2013/01/turkish-government-agency-spoofed-google-certificate-accidentally/ ). It is all about the trust. If you trust the CA provider or not (Qaznet).


For example, for a target bitstring of 100 bits, I cannot scan all bitstrings of 100 bits and XOR each with the target, hoping to recover the message. This approach will produce all messages that can be expressed with 100 bits.

That's not the reason why one-time-pads are considered secure. The reason is that even if you try all possible keys that you get all possible plaintext and you have no method of choosing which one is right. The size of the plaintext/ciphertext/keystream doesn't matter.

  However, not all bitstrings are random, e.g. 111111111111 is less random than 01101001001101. This observation seems to contradict the idea of an unbreakable one time pad.

111111111111 is equally likely as 01101001001101 or any other value of the same size when chosen randomly.

  Proof: If BS3 is compressible, then knowing BS1 would allow us to describe BS2 with a short description (i.e. BS3). Then, either BS1 and BS2 are not both random or are not independent. The only case where they are random, but not independent, is if one is a part of the other.

Values are compressible if they are part of a set where certain values are more likely than others. This is not the case for $C = P \oplus K$ if $K$ is fully random. This is because $C$ will be fully random as well, independent of $P$ being random or not.

  This means that if XORing BS1 with cyphertex BS4 results in a compressible BS5, then BS1 is at least part of BS2 or contains part of BS2.

This will never be the case as BS5 will not be compressible; each possible value of BS5 will be as likely as the other values of BS5 because of the reasons explained above.


How is a per round key generated in DES algorithm?

Numbers $\{14,17,11,24,1,5,3,\dots\}$ come from permuted choice PC-2. So let me explain 16 round DES key scheduling:

DES input key size is 64 bit which contains 56 bit key and 8 parity bits. Parity bits are 8th bit of every 8 bits (on byte). So they are all multiple of eight: $\{8, 16, 24, 32, 40, 48, 56, 64\}$.
Permuted choice PC-1 is used to remove these bits from the 64 bit input key. So PC-1 gives 56 bits as output.

In round $i\ (1 \le i \le 16)$, there is a 56 bit input, $C_{i-1}$ as left half and $D_{i-1}$ as right half (each 28 bits). These two halves are rotated left (for decryption, right rotate is used). For encryption, rotate amount in rounds $\{1, 2, 9, 16\}$ is one and in other rounds it's two. For decryption, one bit right rotation in rounds $\{2,9,16\}$ and two bit right rotation in all other rounds. As inputs of rotation are $C_i$ and $D_i$, outputs of rotation are $C_{i+1}$ and $D_{i+1}$ which are passed to the next round ($i+1$) as input.

After all, in round $i$ there is a 48 bit output, named $K_i$. This sub key is generated from permuted choice PC-2, which takes $C_i$ and $D_i$ as a 56 bit input and outputs the sub key.

Now i think now you understood where those numbers come from. The overall process is illustrated in the picture below (Encryption):

Image Source: Understanding Cryptography by Christof Paar and Jan Pelzl, Chapter 3


Is it safe to assume Salsa20 to be a PRP?

Salsa20 is a stream cipher based on a pseudorandom function, not a pseudorandom permutation.

For a fixed key $k$ and nonce $n$, the mapping $PRF^{S20}_{k,n}: \{0,1\}^{64} \to \{0,1\}^{512}$, which maps a "Stream position" to "keystream block", is supposed to be a pseudorandom function. It is not supposed to be injective (i.e. a permutation, even less since the input/output sizes are different), and there certainly is no easy way to produce a preimage, even knowing the key and nonce.

What you propose is the Salsa20 encryption function for the first "block" of plaintext:
$$\def\Enc{\operatorname{Enc}}\Enc^{S20}_{k, n} : \{0,1\}^{512} \to \{0,1\}^{512}$$
$$\Enc^{S20}_{k, n}(P) = P \oplus PRF^{S20}_{k,n}(0)$$

This is obviously bijective (it is its own inverse), i.e. a permutation, but at the same time, it is obviously not a (pseudo)random permutation. In addition to the self-inverse-property, it for example also has the two-time-pad property:

$$\Enc^{S20}_{k, n}(P_1) \oplus \Enc^{S20}_{k, n}(P_2) = P_1 \oplus P_2,$$

which no random permutation would have.


Decision to Search LWE when modulus $q=p^e$

First of all, it is a search to decision reduction: we are using an algorithm that distinguishes  $A_{\mathbf{s},\chi}$ (the LWE distribution with secret $\mathsf{s}\in \mathbb{Z}_q^n$ and error distribution $\chi$) from $U$ (the uniform distribution on $\mathbb{Z}_q^n\times\mathbb{Z}_q$) in order to find the secret vector $\mathbf{s}=(s_1,\cdots,s_n)$. A decision to search reduction for LWE (like for most other problems) is trivial.

Let's see first how the reduction works when $q$ is prime [R, Lemma 4.2].

Prime $q$. Suppose we have a distinguisher $\mathsf{D}$ for LWE that works with overwhelming probability (i.e., $1-\mathsf{negl}(n)$) -- any distinguisher $\mathsf{D}'$ that works with probability that is bounded away from half by a non-negligible value can be turned into one that works with overwhelming probability using standard amplification techniques: i.e., carry out independent trials, take the majority and apply the Chernoff bound (see e.g., [AB, Lemma 7.9] to see how this is used for $\mathbf{BPP}$). We will use $\mathsf{D}$ to construct an algorithm $\mathsf{F}$ that finds $\mathbf{s}$ as follows. For $k\in\mathbb{Z}_q$ and $l\leftarrow\mathbb{Z}_q$ (where $\leftarrow$ denotes sampling uniformly at random), consider the transformation
 $$(\mathbf{a},b)\mapsto(\mathbf{a}+(l,0,\cdots,0),b+lk).$$
If $s_1$ denotes the first entry of the secret vector $\mathbf{s}$ in the LWE distribution $A_{\mathbf{s},\chi}$, there are two cases:

$k=s_1$: here, the transformation maps $A_{\mathbf{s},\chi}$ to itself, as shown below
$$(\mathbf{a},b)=\left(\mathbf{a},\langle\mathbf{a},\mathbf{s}\rangle+e\right)\mapsto \left(\mathbf{a}+(l,0,\cdots,0),\langle\mathbf{a},\mathbf{s}\rangle+e+ls_1\right)=\left(\mathbf{a}',\langle\mathbf{a}',\mathbf{s}\rangle+e\right)=(\mathbf{a}',b'),$$
where $\mathbf{a}'$ denotes the vector $\mathbf{a}+(l,0,\cdots,0)$.
$k\neq s_1$: the transformation maps $A_{\mathbf{s},\chi}$ to the uniform distribution (as $l$ masks everything).

Now it is easy to recover $s_1$: $\mathsf{F}$ simply runs $\mathsf{D}$ over all $k\in\mathbb{Z}_q$ and outputs the $k$ for which $\mathsf{D}$ outputs $0$ (indicating "LWE"). Since the size of the modulus $q\leq\mathsf{poly}(n)$, this is still efficient. The remaining entries of $\mathbf{s}$ can be recovered by iterating the above procedure, shifting the $(l,0,\cdots,0)$ vector to the right in each iteration. $\square$

Note that the step in the proof which requires $q$ to be prime is the second case ($k\neq s_1$): if $q$ is composite then the map $b\mapsto b+lk\bmod{q}$ is not necessarily bijective and the distribution gets skewed away from uniform when $l$ is one of the factors of $q$. Extending this to the case when $q=p^e$ was sketched in [ACPS, Lemma 1]. The complete proof can be found in [MP, Theorem 3.1] (albeit phrased differently from below).

Prime power $q=p^e$. For simplicity, let's focus on $e=2$ as the argument can be easily extended for $e>2$. For $i=0,1,2$, consider the distributions
  $$A_{\mathbf{s},\chi}^i:=\left\{(\mathbf{a},b+r\cdot p^{2-i}\bmod{q}):(\mathbf{a},b)\leftarrow A_{\mathbf{s},\chi},r\leftarrow\mathbb{Z}_q\right\}.$$
Note that $A_{\mathbf{s},\chi}^0$ is identical to $A_{\mathbf{s},\chi}$ as $r\cdot p^2=0 \bmod{p^2}$. On the other hand, $A_{\mathbf{s},\chi}^2$ is identical to $U$, the uniform distribution on $\mathbb{Z}_q^n\times\mathbb{Z}_q$ as $r$ masks everything.

Step $1$. The first step is to use the distinguisher $\mathsf{D}$, which distinguishes $A_{\mathbf{s},\chi}^0$ from $A_{\mathbf{s},\chi}^2$ to extract $\mathbf{s}'=\mathbf{s}\bmod{p}$. By the hybrid argument, it is guaranteed that $\mathsf{D}$ distinguishes $A_{\mathbf{s},\chi}^0$ from $A_{\mathbf{s},\chi}^1$ or $A_{\mathbf{s},\chi}^1$ from $A_{\mathbf{s},\chi}^2$ with overwhelming probability. We show that in either of the cases it is possible to extract $\mathbf{s}'=\mathbf{s}\bmod{p}$ using the ideas we saw for the case when $q$ is prime. Let's focus on the first case as the second case is analogous, and the only difference is in the transformation.

Case $1$. We are given a distinguisher $\mathsf{D}$ that distinguishes $A_{\mathbf{s},\chi}^0$ from $A_{\mathbf{s},\chi}^1$ with overwhelming probability. The idea is to use a slightly different transform from the previous case. To be precise, we use
  $$(\mathbf{a},b)\mapsto(\mathbf{a}+(lp,0,\cdots,0),b+lkp),$$
where $l\leftarrow\mathbb{Z}_q$ (as before) and $k\in\mathbb{Z}_p$. If $s_1=s_1'+s_1''p$, there are two cases:

$k=s_1'$: the transformation maps $A_{\mathbf{s},\chi}=A_{\mathbf{s},\chi}^2$ to itself, as shown below
$$(\mathbf{a},b)=\left(\mathbf{a},\langle\mathbf{a},\mathbf{s}\rangle+e\right)\mapsto \left(\mathbf{a}+(lp,0,\cdots,0),\langle\mathbf{a},\mathbf{s}\rangle+e+lps_1'\right)=\left(\mathbf{a}',\langle\mathbf{a}',\mathbf{s}\rangle+e\right)=(\mathbf{a}',b').$$
Here, we use the fact that $(a_1+lp)s_1=a_1s_1+lp(s_1'+s_1''p)=(a_1s_1+s_1'lp)\bmod{p^2}$, where $a_1$ is the first component of $\mathbf{a}$.
$k\neq s_1'$: the transformation maps $A_{\mathbf{s},\chi}$ to $A_{\mathbf{s},\chi}^1$ as
$$(\mathbf{a},b)=\left(\mathbf{a},\langle\mathbf{a},\mathbf{s}\rangle+e\right)\mapsto \left(\mathbf{a}+(lp,0,\cdots,0),\langle\mathbf{a},\mathbf{s}\rangle+e+lpk\right)=\left(\mathbf{a}',\langle\mathbf{a}',\mathbf{s}\rangle+e+rp\right),$$
where $r=lk\bmod{q}$. Here, multiplying by $k$ preserves the distribution $l\leftarrow\mathbb{Z}_q$ since $k$ is coprime to $p$.

Now we recover $s_1'=s_1\bmod{p}$ as before: $\mathsf{F}$ simply runs $\mathsf{D}$ over all $k\in\mathbb{Z}_p$ and outputs the $k$ for which $\mathsf{D}$ outputs $0$ (indicating "LWE"). $\mathbf{s}'=\mathbf{s}\bmod{p}$ is obtained by the shifting trick.

Case $2$. Now, given a distinguisher $\mathsf{D}$ that distinguishes $A_{\mathbf{s},\chi}^1$ from $A_{\mathbf{s},\chi}^2$ with overwhelming probability, the only difference is in the transform, which is now
  $$(\mathbf{a},b)\mapsto(\mathbf{a}+(l,0,\cdots,0),b+pr+lk),$$
for $l$, $k$ as above and $r\leftarrow\mathbb{Z}_q$. Note that when $k=s_1'$ the transformation maps $A_{\mathbf{s},\chi}$ to $A_{\mathbf{s},\chi}^1$ and when $k\neq s_1'$ it maps $A_{\mathbf{s},\chi}$ to $A_{\mathbf{s},\chi}^2=U.$

For general $e>2$, the hybrid distributions are defined as
  $$A_{\mathbf{s},\chi}^i:=\left\{(\mathbf{a},b+r\cdot p^{e-i}\bmod{q}):(\mathbf{a},b)\leftarrow A_{\mathbf{s},\chi},r\leftarrow\mathbb{Z}_q\right\}$$
and the $i$-th transformation is
  $$(\mathbf{a},b)\mapsto(\mathbf{a}+(l\cdot p^{e-j},0,\cdots,0),b+(pr+lk)\cdot p^{e-j}).$$

Step $2$. Given $\mathbf{s}'=\mathbf{s}\bmod{p}$, $\mathbf{s}$ can be recoved as described in [ACPS]. $\square$

[AB]: Arora and Barak, Computational Complexity: A Modern Approach

[ACPS]: Applebaum et al., Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems, Crypto 2009

[MP]: Micciancio and Peikert, Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller, Eurocrypt 2012

[R]: Regev, On lattices, learning with errors, random linear codes, and cryptography, JACM 2009


Is it possible to create a ciphersuite for TLS 1.3 using only the Keccak-sponge/duplex?

First for the scope of such a ciphersuite, to quote RFC 8446 Section B.4:

A symmetric cipher suite defines the pair of the AEAD algorithm and hash algorithm to be used with HKDF.

Now to the first question:

Could we for instance define and implement a TLS 1.3 cipher suite to use just constructions solely based on the Keccak-sponge as primitive?

With the above definition of what a cipher suite is, this seems easy enough, we just pair either of Keyak or Ketje with SHA-3 or KangarooTwelve. One of the first two mentioned AEAD schemes would be mostly used for bulk encryption and one of the latter two hash functions via HKDF for key derivation. I'm not sure how much customization TLS 1.3 allows but it might also be possible for an RFC to define Keccak based ciphersuites to use a different KDF than HKDF, though this would most likely lower acceptance.

Additional points go to the answer that also manages to indicate a method of authentication (hash-based signatures?)

Indeed it would be possible to use either of the hash-based NIST PQC Round 3 Alternative candidates for this. In fact Picnic is already based on Keccak (and LowMC to build a MPC-based signature scheme). Additionally SPHINCS+ is also specified for SHAKE-256 for the NIST PQC.

and, possibly more tricky, a key agreement scheme to replace (EC)DH.

Constructing key agreement (or public-key encryption) from hash functions is very unlikely even for theoretical constructions (assuming collision-resistance). It is very much impossible to do so generically only assuming the existence of black-box One-Way-Functions as shown by Rudich and Impaglazzio in STOCS 1989's "Limits on Provable Consequences of One-way Permutations" (PDF).


What's up with unnamed elliptic curves in e-passports?

I don't have any visibility into the BSI standardization process, and so this is a guess; I suspect one of two things happened:

This is a potential way to deal with someone figuring out how to break both Brainpool and NIST curves (but not arbitrary elliptic curves; if they managed that, this hook won't help).  In that case, if someone did that (or if we suspect they might have), we can update the passports without modifying the spec or the readers.
This is a political compromise; some entity with political power pushed it into the BSI spec; possibly because they were card manufacturers that were already using other curves (and BSI decided they didn't want to endorse those curves for whatever reason); possibly because it gave someone a competitive advantage (our password validation equipment does it, our competitor's does not; forcing this in will delay our competitor) or possibly because some bureaucrat got it into their head that this was a good idea.

As for whether coming up with safe domain parameters is non-trivial, well, yeah, it's not something you'd want to hand off to an intern; however the known potential attacks against elliptic curves are well documented; it's not that difficult for someone who knows what they're doing to come up with curve parameters that make all known attacks infeasible.  In fact, there's this paper where they suggest literally creating a fresh elliptic curve for every single key exchange.


Why calculate pi to estimate randomness?

Knowledgeable crypto practitioners do not calculate $\pi$ using a Monte Carlo method to determine if a series of numbers are random.

The test alluded to in the question is a general-purpose¹ randomness test for random number generators with output a real number expected to be uniform of the range $[0\dots1[$. The test consists of drawing pairs $(x,y)$, and determining the proportion such that $x^2+y^2<1$, which should be about $\pi/4$ (because that's the area of the intersection of a square of side $1$ with a disc of radius $1$ and center in a corner of the square, and any subset of the square is expected to get a proportion of the random draws proportional to its area).

Variants of this test can be made for random number generators with bit or integer output, as used in cryptography. However this test is not particularly good, or often used.

Further, general purpose RNG tests are generally not very useful in cryptography:

If applied to the output of a PRNG, such test will declare the RNG good including for cryptographically very weak and poorly seeded PRNG (such as a LFSR seeded with all 1).
If applied to the output of a TRNG directly based on a physical phenomena (such as thermal noise filtered by removing the DC component, keeping polarity, and sampling at a relatively low frequency), many such general purpose tests will tend to fail due to minor bias in the conditioning circuitry, even though the TRNG is working as designed and perfectly usable after conditioning by a properly designed CSPRNG.

In my opinion, the only technically² justifiable use of a general-purpose¹ randomness test in a cryptographic context is to detect gross malfunction³. The archetypal tests for that are the Monobit, Poker and Runs test formerly in FIPS 140-1 and FIPS 140-2; these tests are sound in principle, but had been specified to ridiculously stringent acceptance levels, making these tests usable only on the output of a PRNG, thus largely pointless (per 1. above). After a hiccup altering the acceptance levels, reason prevailed and these tests are no longer mandatory at startup of a FIPS 140-2 device.

A sorry side effect of the above historical error is that the habit of running Monobit and Poker test sticks, hence designers of hardware TRNG strive to have their generators pass these tests to the most stringent levels, hence have an incentive to avoid exposing their inner entropy source before a fair amount of poorly documented conditioning. That makes it more challenging than needed to devise a good field test of the TRNG; that is, a test that reliably catches dangerous defects appearing in a deployed device (including purposely induced defects, e.g. when a Smart Card is cooled by evaporation of a liquefied gas in hope to literally freeze the TRNG), and do so without causing false alarms and/or permanently disabling perfectly good devices.

¹ By general-purpose I mean intended as detecting any deviation from true random, with acceptance level set accordingly. This includes NIST SP 800-22 rev 1a.

² Getting rubber-stamped is a justifiable goal in itself.

³ Detecting gross malfunction is a justifiable goal at some design stage. Validating the design of a cryptographic gizmo (or worse, algorithm) primarily on the basis of the absence of detection of gross malfunction is poor methodology.


How could block encryption in counter mode be secure from viewpoint of entropy?

Summary: an entropy argument shows that block encryption in counter mode can't be perfectly secure.

The remark that any block cipher in CTR mode generates a keystream with very low entropy per bit of keystream is correct. That hints CTR mode is not secure against an hypothetical unbounded adversary. In fact that holds as soon as more bits of keystream are used than there are in the key (or sooner): that unbounded adversary could enumerate all the possible keys, and rule out some keystreams as impossible.

This does not contradict that AES128 is practically safe in most but not all situations, against a real bounded adversary.

As an example of why I write "most but not all situations", consider the feasible case where an exbibyte of data (a fraction of a day's worth of global internet traffic) is enciphered with AES-128 in CTR mode; that's $2^{56}$ blocks, and odds that two ciphertext blocks are exactly identical are a low but sizable $2^{-17}$; should that occur, an hypothetical adversary able to detect and locate that equality (which is much more difficult than the encryption itself, but might still be feasible) would have learnt one tiny bit of information about the corresponding plaintext blocks: they can't be exactly identical; and thus, assuming an all-zero plaintext was characteristic of non-activitly, the adversary would have learnt that there has been activity in at least one of the two spots where the equality is detected.


Clarification on the TLS verification process

The article is wrong, but not there. It's the previous sentence that's incorrect. "The first process is to take the signature on the bottom of the certificate and decrypt it with the CA's public key." Emphasis mine: signatures aren't encryption, decrypting them isn't what the client does, the client verifies the signature. This is unrelated to your question, but it's important not to confuse encryption/decryption with signing/verification, since doing so can lead to major security issues. Such confusion is only really possible with RSA, many other public-key systems don't have any real notion of encryption/decryption to begin with. Confusing basic terminology like this is good reason to stop reading any article about public key cryptography. Confusing signing and encryption is like confusing addition and division: vaguely related, sort of swapped (signing is closer to decryption in RSA though still different), and generally a sign that the article wasn't written by anyone competent.
To answer your question, the server sends a chain of certificates. Each certificate in the chain contains a public key, a name (a domain for the server, an organization name for a CA), some extra information, and a signature covering all that. The signature was created by the private key of the next certificate in the chain, and can be verified by that certificate's public key. At one end there's the certificate of the web site, which doesn't sign any further certificates, and at the other end there's a "root" certificate. This "root" is the only thing that gets preinstalled by the browser. The browser can verify that the named root in the chain has a pre-installed certificate. Then the browser can verify that the next certificate's signature was made by that root, etc down the chain. If all the signatures verify, the final website certificate can be trusted to belong to that domain's owner.
In practice those certificate chains can be short. Lots of CAs are trusted as roots for these chains. For example, this site has (at this time) a certificate for *.stackexchange.com which is signed by the Let's Encrypt R3 certificate (Let's Encrypt is a CA), which is in turn signed by the Internet Security Research Group ISRG Root X1 certificate (ISRG is the organization that runs the Let's Encrypt CA). Browsers trust ISRG Root X1 directly, and verify that it signed the Let's Encrypt R3 certificate. Then they verify that the Let's Encrypt R3 signed the certificate for *.stackexchange.com. Only 3 levels in the chain.


There are a reasonable number of assumptions I'm going to have to make to try and answer this question. For perfect security, we require that the keystream is truely random, and never reused (OTP,shannon).

I've decided to add in a short answer here: STOP! There's absolutely no need to use a reduced character set thing anyway - you can just use your random number generator to generate a random byte and then treat your plaintext as a series of bytes rather than as characters.

Now, I take it you're intending to obey the no-reuse requirement, which leaves us with the question of what happens when my data isn't quite random enough?
Firstly, lets try and work out what a pool of 1000 characters would mean. To run an xor-cipher, we somehow translate the string of characters into a string of bits, using one of many character encodings. There are $2^8=256$ bits in a byte, so I deduce that by character you mean that each character is encoded into two-bytes (which is roughly how UTF-16 seems to work if you don't require very strange characters), meaning there are a total of $2^{16}=65536$ possible characters.

Now, how are you picking $1000$, or indeed $5000$ from them? If they're not randomly sampled from the total options, then you risk letting through some very significant information. For example, if your set is based around "common" characters then because of the way the character sets are constructed there are certain bits which are more likely to be set / not set in your collection of characters.

If you have managed to sample them totally randomly, then at the very least you're loosing out against a naive attack since there are only $1/5$ of the values to check.


How is an epsilon of 1/1000 non-negligible?

How can a computer leverage that tiny extra probability to crack a secret key?

The answer to that depends on what type of key it is, how it's being used, etc. Certainly, the bias would make a brute-force attack easier, but you probably wouldn't need to worry about that, regardless.

Your professor, though, is trying to answer a different question. He wants to know, and wants you to think about:

  How small does the bias have to be in order to ensure that no one can leverage it to crack a secret key?

Note that this question is general: it makes absolutely no reference to what kind of key is being generated, or how it's being used. And this is how it should be: we're designing a general-purpose PRNG, so we shouldn't make assumptions about those things.

Suppose we used this PRNG to generate a 128-bit AES key. Well, assuming the bits are independent (but have the 1/1000 bias), then some math shows that the statistical distance between the result and a truly random 128-bit value is about 0.018. It follows if you used this PRNG in place of some mathematically perfect one, an attacker might be able to increase the chances of a successful attack by as much as 1.8% (but by no more than that).

Is this something you should be worried about? Well, if it's a 1.8% increased chance of someone decrypting a harmless IM conversation you had with a friend... probably not. On the other hand, if you're encrypting your bank password or a set of nuclear launch codes, a 1.8% increased chance of being compromised is probably an intolerable risk.

The 1.8% is an upperbound. We might not be able to find an attack that obtains that advantage. But by limiting the bias to something like 2^{-80}, we can safely stop worrying about the matter entirely.

The theorists would define a bias as "negligible" if it decreases "really fast" with respect to some adjustable parameter of the PRNG. This definition aims to ensure that we can always choose a value for the PRNG parameter such that (1) it's bias is quantitatively really small, e.g. 2^{-80}, but (2) the PRNG is still efficient.

Ultimately, however, you have to fix the parameter when you go and actually start  using the PRNG. At this point, you have to decide what concrete value of "negligible" you're comfortable with. This is a judgement call, but any reasonable PRNG will let you put it safely in the "we don't even have to worry about this" territory and still produce outputs as quickly as you could ask for.


Now, this is where I'm confused. I've read once that selecting right points isn't a trivial task, there exists an algorithm to test the rank of a point, but it's somewhat complex to implement. However I've also heard that most of the points on an elliptic curve are generators, and when selected in a pseudo-random manner it's very unlikely to fall onto a bad point.

Actually, finding a generator is typically a lot easier than what you've read, at least in practice.

In crypto, we generally use curves that have an order of the form $hq$, where $q$ is a large prime, and $h$ is a small integer.

So, what you do is:

Run your hashing function to create an arbitrary point $H$
Multiply it by the cofactor $h$ to find the point $H' = hH$ (which is totally trivial for those curves with $h=1$; not that difficult for curves with larger cofactors)
Verify that $H'$ is not the neutral element (aka the identity aka the point at infinity).

If $H'$ is not, then that's your generator; it's guaranteed to be of order $q$, and to have no known relationship with other points (assuming that your original point $H$ didn't)


Question on the CPA-security proof of the CTR-Mode

The problem is with your statement "There is no overlap and A probability to win is $1/2$, because the PRF is secure." What does that mean? The only way to formalize that is to show that if adversary wins with probability greater than $1/2$ when there is no overlap, then you can break the PRF. That is essentially what the proof does. Note that it doesn't have to be by contradiction - it's also possible to show that when there is no overlap, then a reduction to distinguishing the PRF from random shows that the gap is negligible. That is the way the proof written in the book works.