Given that we can add only 4 digits (13.3 bits) of redundancy, there is no way to use asymmetric cryptography. We'll have to use a secret key in the verification terminals.

This is an application for Format Preserving Encryption. It can act like a block cipher, except we can decide the block width, and deal with decimal rather than binary or hexadecimal digits. Methods for FPE are given in NIST SP 800-38G. The previous link leads to references with other methods.

Take the 16-digit plaintext, append four zeroes, yielding 20 digits. Encipher that using FPE, yielding 20 digits, put that on the ticket.

On reading a ticket, check that it is 20 digits, decipher per FPE (yielding 20 digits), and consider the result valid when it ends with four zeroes; remove these.


What is an easy method of proving that a cryptographic oracle attack is possible?

We have a Padding Oracle if there is a different response from the server gives us an indication of the correctness of the pad (say if this needs proving). We can establish this by playing a game where we send badly padded cipher-text and random strings to the server, finally submitting some at random and seeing if we can get a non-negligible Advantage is guessing which one we sent.

The problem is that this might be the "brute force" way. It's fairly easy to do if there is obvious data-leakage, but you have to check through a lot of side-channel attacks to rule out data-leakage to an efficient adversary. I sense you want a clever fast way to prove there is no data-leakage, which doesn't sound possible to me.


Is there a LWE based public-key encryption scheme which is CCA1-secure?

Yes. You can see Micciancio's annotated bibliography for some relevant papers (including generic transformations from CPA security to CCA security in the random oracle model). If you want to see "actual" schemes which are CCA1 secure, Kyber is a CCA2-secure KEM with security based on a variant of LWE over "Module Lattices", which can be viewed as a slight generalization of R-LWE.


For RSA keys, is the safety of a given key-length different for signing vs encryption?

No, the security is about identical, as the underlying RSA problem is the same.

Besides that, non-repudiation is usually managed differently with regards to legal requirements. Providing confidentiality (encryption) is a rather different use case than non-repudiation (signing a contract).

It is also possible to use signatures for authentication rather than non-repudiation. In that case you may be able to get away with smaller signatures if the authentication and key is only valid for a limited amount of time.

All in all, the key strength should be considered given the use cases, threat model and of course the system parameters. Defining a minimum RSA key size without considering the system is not a good idea.

Notes:

It could be possible to assign a notary that immediately signs the document after signature generation by the other party. The notary should of course use a key of sufficient strength.
I've used the notion of a larger key, but what you're really after is a stronger key. Usually larger keys are stronger for the same algorithm though.
If you go over a 16Ki key size then the key size doesn't matter much anymore. The key will only be broken if RSA itself is broken (e.g. using a hugely powerfull Quantum Computer).


How can AES-CCM behave as an AEAD stream cipher?

The property that you are looking for is the "online" property of a stream cipher. CCM was however developed for packet encryption where the size of the data is known beforehand. So CCM lacks the strict online requirements for an online cipher. However, since the cipher underneath still uses counter mode, the encryption itself can still be performed on each byte separately in an online fashion (performing online per bit encryption / decryption is not possible in most implementations).

Usually you'd want to verify the authentication tag for correctness before decryption for any AEAD cipher. That means that the online properties of the underlying counter mode are generally not used. Still, you could first verify and decrypt in online fashion afterwards using two passes over the ciphertext.

Furthermore, if the authentication tag is considered part of the ciphertext - like most libraries do - then it is unlikely that those libraries will expose the online properties of the underlying counter mode during decryption. The implementation will have to cache at least as many bits as present in the authentication tag before it decides that they are part of the counter-mode encrypted plaintext or part of the authentication tag. That means that during decryption the cache is always kept full until the end of the stream is reached.

That the CBC-MAC (not CMAC) used by CCM needs to process the data block by block us usually not considered a problem. Any MAC is required to keep state anyway, and the verification can simply take place when all the data has been processed. Note that GMAC within GCM also performs multiplication over 128 bit blocks. The online property is therefore considered for the cipher part of the AEAD mode only.

Conclusion: CCM has not been defined to offer online encryption / decryption, and there are serious issues with using AEAD ciphers for online encryption / decryption even if it was. That the CBC-MAC construction is used has little to nothing to do with the underlying issues.

I'd you're looking for an AEAD mode with better online properties and MAC based on the block cipher then take a look at EAX. EAX is basically a standardized way of using CTR mode and CMAC authentication.

There are two major drawbacks:

It has only been accepted as draft standard by NIST;
Due to the additional calculations for CMAC compared to CBC-MAC it adds a constant overhead preset message.

And you'd still have all the generic drawbacks mentioned for AEAD ciphers when it comes to online decryption, of course.


Can any block cipher in CTR mode be used as a CSPRNG?

can any block cipher in CTR mode be used as a CSPRNG?

Formally speaking the CTR mode transforms a PRF (or a PRP) into a PRG and as the PRP notion is the standard notion to model block ciphers, pretty much all secure block ciphers should yield a secure PRG when used in CTR mode.

Less formally speaking CTR mode transforms a secure block cipher into a secure stream cipher. This implies that you "encrypt a stream of zeroes" which should be properly secure as a CSPRNG because chances are that you could break the stream cipher otherwise.

Finally you'll also see CTR mode as a building block for a sophisticated CSPRNG in practice quite often, for example with CTR_DRBG (PDF) (which among other applications is used by Intel's RdRand).

  Or are there specifc characteristics a block cipher should have to be
  used as such?

As said above, it should behave like a PRP, that's all, but (nearly?) all secure block ciphers do just that.

  Can such a CSPRNG be used to produce key material, or do I have to
  specifically use a key generation/derivation algorithm for that
  purpose?

Technically you could use CTR mode directly to derive keying material. However specialized CSPRNG constructions and KBKDFs exist for reason. So if you have a properly seeded CSPRNG, you can directly derive keys from that or else you want to use a KBKDF if you're basing of some shared keying material (like a DH shared secret).

These specialized algorithms usually allow for customization and have advanced usage scenarios in mind. So for example you have a static secret and a counter? You can use CTR_DRBG to turn this into a CSPRNG! Or you have a secret key and some context? You can use HKDF to derive keying material with a context label and context info!


Blake2: truncate 512-bit hash is safer than 256-bit by Config?

You should always use config options to select the output size of a hash function.

If you need a standard output size (e.g. 224, 256, 384, 512 bit) use the recommended parameter set.
This mainly applies to standards like SHA-3, where if you use SHA-3-256 you'll get a different (more standard output) than with "Keccak-256", SHA-3-512/256 and SHAKE128-256, which all use something called "domain seperation" (i.e. append a specific byte sequence to the input to get different hashes).

The reason for the first statement is the following:
The config option is always equally good as / better than the manual truncation. In worst case (e.g. SHAKE) it's just simple truncation of an infinitely long key stream and thereby exhibits the same security properties as manual truncation. In best case (e.g. Skein) the selected output size will influence the output, i.e. Skein-256-256 will give a completely different output for a message $m$ than  Skein-256-255 will. Obviously this is more secure (and usually not less fast) as it will guarantee you that $Trunc(H_{d}(m),t)\neq H_t(m)$ which may be a desirable property (although rarely needed).

Blake2 corresponds to the second case (i.e. the digest size affects the output). The requested digest size is used as the initial internal chaining value (right after the IV) along with a static constant and the MAC-key (if used). And thereby it affects the hash as much as the IV does which means Blake2b-32 will be vastly different from Blake2b-64 for the same message. This can be found in RFC 7693 on page 4 (variable name) and page 9 (usage of hash size).


Paillier Encryption: problems with double encryption

No, this is not possible. The homomorphism only works at one layer.

A ciphertext in Paillier is $g^m\cdot r^n\bmod{n^2}$. The plaintext space is the multiplicative group of integers modulo $n$. So, for it to even have a chance to work, first of all, the modulus of the outer encryption would have to be greater than $n^2$, where $n$ is the modulus of the inner. Assume this is true. Let the moduli be $n_i$ and $n_o$ for the inner and outer encryptions respectively (and $n_o > n_i^2$ (I'll similarly subscript all the other parameters).

So, for the encryption of $m_1$ we get $g_o^{g_i^{m_1}\cdot r_i^{n_i}\bmod{n_i^2}}\cdot r_o^{n_o}\bmod{n_o^2}$. Now, what we want is something like $g_o^{g_i^{m_1+m_2}\cdot r_i^{n_i}\bmod{n_i^2}}\cdot r_o^{n_o}\bmod{n_o^2}$. Possible options to get there include exponentiating the first by $m_2$, but that doesn't work. We could multiply the first by encryption of $m_2$ with the outer key, but that doesn't work. Even multiplying by the double encryption (first with inner, next with outer) doesn't work.

I know this isn't a rigorous proof, but there doesn't seem to be a way. The algebraic structure is just too mangled after a second encryption for it to work.


Reference books in security and privacy preservation

You can start your learning
https://www.coursera.org/learn/crypto/home/welcome
An excellent course to start with all about Symmetric/Asymmetric encryption/TLS/MAC etc.
A free ebook is also available https://crypto.stanford.edu/~dabo/cryptobook/BonehShoup_0_4.pdf

https://www.schneier.com/books/applied_cryptography/


Curve25519/Montgomery curves points with order 8

Curve25519 has order $8\cdot q$, and we want a point of order $8$. This is the laziest solution I can think of:

Generate a random point $P$ on the curve;
Compute $Q = [q]P$. This point has order $1$, $2$, $4$ or $8$.
If $Q$ is not of order $8$, go back to step 1.

A sample code to see the points we get:
E = EllipticCurve(GF(2^255-19),[0,486662,0,1,0])
for i in range(20):
    P = E.random_element()
    Q = P.__mul__(2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed)
    print (Q.order(), Q)

Expect a few attemps until a point of order $8$ is found.

Another way to do this is to use division polynomials.
Just giving the general idea about them. There is a series of polynomials whose roots are related to torsion points. Basically, the points $P$ such that $[n]P = \infty$ have their $x$-coordinate as roots of a polynomial.
However, those roots can be over an extension field, so they do not correspond exactly to points on the elliptic curve over the base field.
Using SageMath, we can find the $8$-torsion points of Curve25519:
sage: p = 2^255 - 19
sage: E = EllipticCurve(GF(p), [0,486662,0,1,0])
sage: E.division_polynomial(8).roots(multiplicities=False)
[0,
 57896044618658097711785492504343953926634992332820282019728792003956564819948,
 39382357235489614581723060781553021112529911719440698176882885853963445705823,
 325606250916557431795983626356110631294008115727848805560023387167927233504,
 1]

There is the point $(0,0)$ of order $2$, the next root corresponds to two points of order $4$ on Curve25519 over $\mathbf F_{p^2}$, the next two roots to four points of order $8$, and the last one to two points of order $4$.


Complexity of multiplication of two numbers

The maximum size of $m$ is $n/2$, and the maximum value of $n$ is $10^k-1$. It follows that the size of $m$ is exponential in $k$. Since (when $n>0$) the multiplication algorithm must read the whole of $m$, and that takes time at least proportional to the size of $m$, it follows that the complexity is at least exponential in $k$.
From a theoretical standpoint, the multiplication is thus not efficient for security parameter $k$, since efficient is defined as time bounded by a polynomial of the security parameter.
If the security parameter was $n$, the algorithm could be efficient (and we could prove that by exhibiting a multiplication algorithm with cost bounded by a polynomial in $n$, which is easy: the schoolbook algorithm turns out to be enough; this is left as an exercise to the reader).
In a crypto context, we want the security parameter to be such that it makes the normal user's cost at most polynomial (i.e. efficient), but the attacker's (conjectured) cost at least super-polynomial (hopefully exponential). Thus if our algorithm is to be considered interesting, then

if that multiplication is to be performed by the user, it must be efficient and thus our parameter can't be $k$.
if that multiplication is to be performed by an attacker in an attack, but not by the legitimate user, our parameter can be $k$, and probably should be. The multiplication then can be efficient (and is, unless the multiplication algorithm is abysmally inefficient).


Prove the correctness of decryption process of Paillier cipher

First, we simplify $\mu$.
\begin{align*}
    g &= (1+n)^{\alpha}\beta^{n} \bmod n^{2} \\
    g^{\lambda} &= (1+n)^{\alpha\lambda}\beta^{n\lambda}\bmod n \\
    &= (1+n)^{\alpha\lambda}\bmod n^{2} \\
    &= (1+n\alpha\lambda)\bmod n^{2} \\
    L(g^{\lambda}\bmod n^{2}) &= (\alpha\lambda)\bmod n^{2}
\end{align*}
Then, let's take a look at $L(c^{\lambda}\bmod n^{2})$.
\begin{align*}
    c &= g^{m}r^{n}\bmod n^{2} \\
    c^{\lambda} &= g^{m\lambda}r^{n\lambda}\bmod n^{2} \\
    &= g^{m\lambda}\bmod n^{2} \\
    &= (1+n\alpha\lambda)^{m}\bmod n^{2} \\
    &= (1+mn\alpha\lambda)\bmod n^{2} \\
    L(c^{\lambda}\bmod n^{2}) &= (m\alpha\lambda)\bmod n^{2}
\end{align*}
Hence, $\frac{L(c^{\lambda}\bmod n^{2})}{L(g^{\lambda}\bmod n^{2})}=m\bmod n$, the decryption process of Paillier cipher is correct.


I point this out because a fair number of practicing cryptographers aren't aware: PBC is slow and outdated and a pain to work with. MIRCAL and RELIC are the two main alternatives.


Is a singular LUKS volume with different passwords that unlock different filesystems possible?

No, LUKS does not support this. What you are looking for is plausible deniability, similar to what VeraCrypt supports. LUKS does not support this, with the reasoning explained in section 5.18 of the official cryptsetup FAQ. Their reasons for not supporting this boil down to the fact that it is difficult to use plausible deniability with hidden volumes correctly. For example, if you don't write to your dummy volume in a while and the timestamps show this, the deniability is broken.


GCM: use the same key:IV pair to encrypt file and filename

This is terrible. In GCM, if you use the same nonce, then the authenticator is completely broken (for all messages in the future). You should never assume that the attacker doesn't know the filename either. You MUST use different IVs.


Although I cannot speak to the first part of your question, I can answer the second part.  Also, I have never seen a formal explanation of how to map polynomials to a LFSR.  In retrospect, I honestly do not know if the polynomials that I have been given were picked because it was known that they would map to circuits, but here is how I do it.

As our example, we will start with the irreducible polynomial used in AES:

$$P(x)=x^8+x^4+x^3+x+1$$

I drop the $+1$, which is the $x^0$ term.  This gives me 8 total flip flops: $x^8,x^7,x^6,x^5,x^4,x^3,x^2,x^1$.  Due to the form of $P(x)$, I expect XOR feedback taps after $x^8,x^4,x^3,x^1$, which tap $x^8$ becomes just a feedback line as it goes to nothing.  The resulting circuit is:

In the circuit above, the data moves to the left from the right.  Taking the initial condition for AES as 0x01, we get the logic of:

01: 0x01
02: 0x02
03: 0x04
04: 0x08
05: 0x10
06: 0x20
07: 0x40
08: 0x80
09: 0x1b
10: 0x36
11: 0x6c
12: 0xd8
13: 0xab
14: 0x4d

This method has worked every time that I have implemented a LFSR as an irreducible polynomial. The first time I looked at the problem was with a simple polynomial and the answer was just "obvious".  I carried that system forward to ever other time and so far, so good.

Additions, comments and a proper method would be welcome.


Is there any IND-CPA secure stream cipher with a "standard" hardness assumption?

Sure.

one-way permutation  +  strong hard-core functions
$\to$
pseudorandom generator
$\to$
stream cipher

The keystream is concatenation of the strong hard-core function's values at

the iterates of the one-way permutation on the key.  ( k,f(k),f(f(k)),f(f(f(k))),... )


The scheme you propose is not possible as far as I know. This is because $enc(M)$ has to be known for the dead-man's switch to operate (in a time capsule like way, as you described), but there is no way in taking away the time capsule from someone non-cooperative (Eve), to substitute it with $update(enc(M))$.

Another possible scheme can be thought of, if you have a group of trusted parties. One can then use a threshold scheme in order to hide the key $k$ to your encrypted message $enc_k(M)$.
Whenever you don't update those trusted parties, after $t$ time, they can connect to each other, and if they reach the threshold of the scheme, release the key $k$.
This protocol requires a couple of external trusted parties. Although they can be computers, both computer and human can get compromised before the dead-man's switch fires.


What is the difference between a cryptographic primitive and a functionality?

It is difficult to answer this question without looking at the same papers you are looking at. Still, I interpret these concepts as fairly different, for reasons I will sketch below.

A function is common in mathematics, and can be written as some mapping $f : X\to Y$ of inputs to outputs. Many algorithms implement the behavior of functions --- they take some batch of inputs, and return outputs. Consider prototypical examples as being "sorting algorithms" or "graph algorithms" or "essentially any algorithm you learn about in an algorithms course".

Functionalities do not necessarily collect all of their inputs before starting processing them. Later inputs can depend on prior inputs, potentially in non-trivial ways. This is in particular important for interactive protocols, where for a two-person protocol with participants $P_1$ and $P_2$, $P_2$'s later inputs can depend on $P_1$'s prior inputs (potentially in an adversarial way). This is somehow the "core" of the idea, where other similar concepts (say streaming algorithms) often are not called functionalities because of the lack of multiple participants.
So functionalities can be seen as the mathematical abstraction which captures the notion of interactive algorithms.

A cryptographic primitive is some tuple of algorithms $(\mathcal{A}_1,\dots,\mathcal{A}_k)$ (which might each individually be a function or a functionality), along with certain conditions they must satisfy.
There are many conditions you can impose, but common ones are things like:

Correctness
Soundness
Indistinguishability of various quantities ("privacy" or "secrecy" conditions)

For example, symmetric-key encryption is often described as a triple of algorithms $(\mathsf{KeyGen}, \mathsf{Enc}, \mathsf{Dec})$ such that:

There is a correctness condition:

$$\forall k\leftarrow\mathsf{KeyGen}(1^\lambda), \forall m\in\mathcal{M}
 : (\mathsf{Dec}_k\circ\mathsf{Enc}_k)(m) = m$$
Where $\mathcal{M}$ is the message space of the algorithm.
There is a secrecy condition, namely that for $k\leftarrow\mathsf{KeyGen}(1^\lambda)$, and $m_0\neq m_1$, $\{\mathsf{Enc}_k(m_0)\}$ is (some form of) indistinguishable from $\{\mathsf{Enc}_k(m_1)\}$, where these quantities are distributions over the choice of random coins of encryption.

So we can view each of the individual algorithms as being functionalities, but them combined together with conditions they must fulfil as being a cryptographic primitive that we call "symmetric key encryption".

Note that one could technically view something like a sorting algorithm as a "cryptographic primitive with solely a correctness condition", but this is rather non-standard. We generally assume all algorithms must be correct, so only start describing things as cryptographic primitives when the condition is something like "correct in an adversarial context", or conditions such as "secret" (or other "more than just correct" conditions).

While I believe this viewpoint is fairly common, I don't know if it is universally agreed upon by all authors at all times, so particular questions you have about particular papers would still be easier to answer with a pointer to those papers.


Is using EAX mode with a 64-bit block cipher a bad idea?

Using EAX with a 64-bit block cipher is problematic, because the short block size causes some weaknesses due to internal collisions.  I do not recommend it.  Use a 128-bit block cipher.
Indeed, the world has moved away from 3DES and towards AES exactly because of these fundamental problems with a 64-bit block size: the internal collision effect means that, with a 64-bit block cipher, once you encrypt more than about $2^{32}$ blocks of data, it is very likely that there will be at least partial leakage of secret information.  This problem is not specific to EAX: it is endemic to essentially every block-cipher-based mode of operation around.
We can be more precise and quantify the nature of the problem by looking at the security theorem for EAX.

Confidentiality. The security theorem (Corollary 6 in the EAX paper) says that, assuming our block cipher is perfect, an adversary who wants to violate confidentiality can do so with advantage at most $9.5 \sigma^2/2^n$.  Here $\sigma$ counts the number of $n$-bit blocks that are encrypted, and $n$ is the block size.  If you want to use EAX with a 64-bit block cipher, then  you have $n=64$, so this expression for the adversary's advantage evaluates to $9.5 \sigma^2/2^{64}$.  For good security, you want to keep this number significantly lower than 1.  Unfortunately, if you encrypt one billion blocks (8 GB of data, i.e., $\sigma = 2^{30}$), then this expression evaluates to $0.59$, so the adversary's advantage might be that big.
In rough intuitive terms, if you encrypt 8GB of data under a single key using EAX with a 64-bit block cipher, there's at least a 50% chance that the attacker learns some partial information about the secret messages.  That's not good.  Instead of 50%, we would much prefer this number to be much smaller: like one in a million or something.  So,  the security level obtained is not really acceptable.

Integrity. The same security theorem also gives us a bound on the chances that the attacker is able to create a forged packet, assuming the attacker gets a single attempt.  This probability is at most $11 \sigma^2/2^n + 1/2^\tau$, where $\sigma,n$ are as before and where $\tau$ is the length of the authentication tag.  Assuming you use a 64-bit authentication tag (which I recommend), the security level is $(11 \sigma^2 + 1)/2^{64}$.  For $\sigma=2^{30}$ (8GB of data), this probability is about $0.69$.
In other words, if you encrypt up to 8GB of data using EAX with 64-bit block cipher (using the same key for all data), then an attacker who makes a single attempt at forgery might have as large as a $0.69$ chance of success, with just a single attempt.  If the attacker makes multiple attempts (which of course the attacker can do), then the attacker's success probability might increase even more.  This is totally unacceptable.  We probably want the attacker's success probability, after making (say) a billion attempts, to be small (say, one in a million or something).  A 64-bit block cipher falls far short.

TL;DR: Use a 128-bit block cipher.  A 64-bit block cipher is cutting things too fine.


Why can't eavesdropper not make up own private key on diffie hellmann?

Eve does not have the same information. It's only with you poor choice of numbers did you get the phenomena where the number you chose for Eve happens to match.
In general this doesn't happen, and with careful choice of parameters and large numbers the chance for this happening is negligible.

You chose an unsafe prime $17=2^4+1$ rather than a safe prime of the form $p=2*q+1$ when q is also prime. You then chose $g=2$ which only spans a group of size 8. $2^8=1\space mod\space 17$ rather than for instance g=3 which can produce the full range.

For Alice and Bob it is guaranteed: $(g^{P_a})^{P_b}=(g^{P_b})^{P_a} = g^{P_aP_b}$
Since Alice and Bob aren't using Eve's public key, she can't calculate the shared key with them.
In the vast majority of cases she will end up with a different number.

In your example the shared key came out 1, and many guesses by Eve work (but not all). Because the public key for Alice and Bob came out with low rank (2 and 4). Using a large safe prime and a generator will make this highly unlikely.

It is considered very difficult to calculate $g^{ab}$ from $g^a$ and $g^b$ without knowing either a or b. Eve guessing a random key isn't likely to help. For random $e$ in almost all cases $g^{ae}\ne g^{ab}$


Cryptool - DES (ECB and CBC ) - double encyption

There are a couple of things going on:

First of all, the DES key FF FF FF FF FF FF FF FF happens to be a "DES weak key"; by that, we mean that if you send a block through the cipher twice, it'll end up with the original value; that is:

$$X = DES_{weak}( DES_{weak} ( X ))$$
You are obviously encrypting in CBC mode with a zero IV.

So, let us look at what happens to the first block during your encryption.  He's call the initial value of that plaintext block $A$ (which is 44 6F 75 62 6C 65 20 65 in your example)

First you encrypt the text in ECB mode.  For the first block, this just sends it through DES, resulting in a ciphertext block we're call $B$ (which is A3 77 A8 0A AD 2B EA 6E in your example:

$$B = DES_{weak}(A)$$

Then, you encrypt that in CBC mode (with a zero IV).  For the first block, this exclusive or's the block with the IV, and sends it through DES.  Because we are using a weak key, this results in the original $A$ block, as:

$$DES_{weak}(IV \oplus B) = DES_{weak}(B) = DES_{weak}(DES_{weak}(A)) = A$$

Lastly, you encrypt the text again in ECB mode.  For the first block, this just redoes what we did in the first pass (because the first block is the exact same value it was):

$$B = DES_{weak}(A)$$

Now, this doesn't happen with the second block; that's because of the CBC mode in the second pass.  CBC mode exclusive or's in the value of the first block, and since that is not zero, the second equation does not hold.


Real life systems that use concepts of crypto computing

IACR uses electronic, encrypted voting for their elections every year. They use Helios
Sharemind has been used in a few applications (financial data analysis, social study)
CipherCloud claims to do a number of things on encrypted data. There was some discussion of their work on here that was partially removed due to a DMCA request.
Skyhigh Networks does functionality-preserving encryption of cloud apps
CryptDB aims to build encrypted databases.
Dyadic uses multiparty computation to protect cryptographic keys that would otherwise be compromised by a break of a single server.
ShareMonad has been used to prototype MPC voice accumulation, regular expressions, SHA, AES, and SAT.


question on encryption of multiple distinct messages

It does not work either. There are a few counter examples:

Let $x=G(k)$ be the key stream, which I understand you want to use to encrypt multiple messages

1 $m_1=0^l$ and $m_2=r \in\{0,1\}^l$, once you encrypt $m_1$, the ciphertext $m_1\oplus x = x$ is exactly the key stream, that can be used to decrypt the ciphertext of $m_2\oplus x\oplus x=m_2$. Note $m_1$ and $m_2$ are distinct.

2 Let $m \in \{0,1\}^{l-1}$, $m_1=m||0$, $m_2=m||1$, $m_3 =r \in\{0,1\}^l$, then given the ciphertext of $m_1$, in a CPA game, the adversary can easily distinguish $m_2$ and $m_3$. All 3 messages are distinct.

The main problem is that distinct means the messages are not equal, but nothing more on their distributions. Therefore, it is insufficient to ensure the indistinguishability of ciphertexts.

When you use an iv, which is a long enough random string, the iv is used as input to $G$ (well I am abusing the syntax a little bit), so you have $G(k,iv)$ which produces a different and independent key stream per iv.


CCA-attack is possible in RSA, but how the decryption key $d$ is known to anyone

Chosen Ciphertext Attacks against RSA (such as Bleichenbacher's Attack on PKCS #1 encryption) do not actually reveal the private key.

If they don't, they why do we say that they are a threat?  Well, it's because that the keys are generally not of interest to the attacker.  Instead, given an encrypted message, the attacker actually wants to know what that message says. He's interested in the key only because the keys would reveal the message.  If the attacker can find a way to get the message without the key, he has won the game.  Bleichenbacher gives him such a way.


How to calculate Modulo using a standard calculator for a one time pad encryption

In modular calculations such as this, the divisor (in your case 26) must be at least the size of your character code space. Your code space is 46 characters, so that is not going to work.

Any output of the modular calculation will be less than the divisor, so you will never get 83 for x mod 26, it is not going to happen. For a 46 character code space, 46 is the appropriate divisor.

Also the code space for your message characters is inconsistent, 06 codes to both "6" and "R". 92 will also code the same as 00 mod 46, so your code book values will never work. They must all be unique mod 46.

You have even more problems with your key and ciphertext. There was no modular calculation in generating your ciphertext, or all values would be less than 26. I also have no idea how you got 83+48=105, and 48 is once again outside the code space.


I am an author on the FleXOR paper and can comment a bit. Let $A_0$ and $A_1$ are the false/true wire labels on some wire, and let $A_0 \oplus A_1$ denote the offset of that wire. The idea behind free-XOR is that when the 3 wires that touch an XOR gate have the same offset, then the XOR gate can be garbled for free. So you arrange for all wires in the circuit to have the same offset.

The idea behind fleXOR is to have not one global offset but several throughout the circuit. Again, whenever 3 wires touching an XOR gate have the same offset, you get that XOR gate for free. When only 2 wires touching the XOR gate have the same offset, you get that XOR gate for a cost of 1 ciphertext. So now we have made [some] XOR gates cost a little bit more. But it turns out by adding this flexibility you can make the AND gates cost less. In some cases it turns out to do better than free-XOR. (Another reason to favor fleXOR is because it can be instantiated in a way that requires a milder hardness assumption.)

I will point out that if the size of a garbled circuit is all you care about, then fleXOR has been made obsolete by the half-gates construction:

  Samee Zahur, Mike Rosulek, David Evans: Two Halves Make a Whole - Reducing Data Transfer in Garbled Circuits Using Half Gates. EUROCRYPT (2) 2015: 220-250

As for implementations, free-XOR is implemented probably in every GC library out there (JustGarble, etc). I'm not sure about implementations of fleXOR, its moment of fame was short-lived before it was superseded by half-gates. For the paper we implemented the circuit-analysis steps so that we could determine the concrete garbled circuit size, but we didn't implement the actual garbling/evaluation algorithms. Yehuda Lindell hangs around here; he has a recent paper with some followup work on the fleXOR techniques, which may have involved an implementation (I don't remember off the top of my head).

For more details about the differences between various garbled circuit constructions, you can check out a survey talk I gave about the topic: video, slides.


What is the difference between SHA-3(Keccak) and previous generation SHA algorithms?

They are all hash functions. Apart from that, they are structurally quite different. The SHA family (SHA-0, SHA-1, and the SHA-2 functions such as SHA-256 and SHA-512) use the Merkle-Damgård construction, around an internal permutation which happens to be an extended Feistel network. Low-level primitives include boolean bitwise operations, and addition over 32-bit or 64-bit integers.

In SHA3, the structure is that of a sponge function, which is quite different. Moreover, the inner permutation is not a Feistel network; low-level primitives are boolean bitwise operations over 64-bit words, but not additions. This avoidance of operations that involve carry propagation helps a lot with performance on hardware implementations (FPGA, ASIC).


How can XTS be used to detect the presence of TrueCrypt hidden volumes?

They don't issue cryptographer's licenses to pseudonymous carrion fowl, so I can't rightly claim to be a cryptographer, but I can confidently say that if there is any problem here it is far more likely to arise from unrelated mistakes in VeraCrypt's protocol or implementation than in cryptanalysis of AES-XTS.  Any distinguisher on AES-XTS implies a nearly-as-good distinguisher on AES itself, and the difference is so small for a number of queries so far below the birthday bound as this that effectively it would mean someone has broken AES.


Converting R1CS to QAP - checking the last step

There are both.
To produce a QAP system, you do dot-product witness and polynomials (no evaluation).
To verify a SNARK-proof, you do dot-product witness and polynomials evaluated at "toxic waste" multiplied by group elements.
Please note it's actually both public input and witness concatenated (all the variables).


Homomorphic cryptosystem with respect to concatenation

Yes, we can construct a cipher homomorphic with respect to the concatenation operation (noted $\mathbin\|$ ). In short, we make the encryption of a concatenation the concatenation of the encryptions.

Start from any (CPA or CCA-)secure cipher capable of enciphering into a fixed-size cryptogram a single-symbol plaintext (e.g., an octet or a bit depending on granularity thought). Note $E$ the encryption function, with $c=E(k,r,q)$ the result of the encryption under key $k$ with random nonce $r$ of the single symbol $q$, and $D$ the decryption function $c\mapsto D(c)$ such that $\forall k,\forall r,\forall q,D(k,E(k,r,q))=q$ (for asymmetric cryptography $k$ can be a public/private key pair with the public key used for encryption),  Also assume a public pseudo-random permutation $r\mapsto P(r)$.

Then extend $E$ by stating that when $q$ is the concatenation of more than one symbol, it can be expressed as $q=\hat q\mathbin\|\tilde q$ with $\hat q$ the first symbol of $q$ and $\tilde q$ the rest, and $E(k,r,q)=E(k,r,\hat q)\mathbin\|E(k,P(r),\tilde q)$.

Correspondingly extend $D$ by stating that if $c$ is wider than the (constant-width) encryption of a single symbol, it can be expressed as $c=\hat c\mathbin\|\tilde c$, with $\hat c$ just wide enough for a single symbol, and $D(k,c)=D(k,\hat c)\mathbin\|D(k,\tilde c)$.

Using that operator $\|$ is associative, that construction $E$ can be shown (CPA or CCA-)secure as the original is (we use that applying the PRP $P$ iteratively on random/nounce $r$ generates a pseudo-random sequence); and has the property thought in the question, with $g$ concatenation.

$E$ can for example be AES-CTR with random IV $r$ at the beginning of the ciphertext; or RSAES-OAEP (with symbol a byte, or with encryption of a bit defined as encryption of the byte 00 or FF depending of the bit's value). $P$ can be any PRP independent of $E$.

One drawback of the above simple construction is that it expands ciphertext size considerably. However, that can be fixed, as follows.

we start from any cipher than can cipher an arbitrary string of symbols, and prepend a single 1 bit to its ciphertext in that simple case
we define $g(c_1,c_2)$ with $c_1$ of $k>0$ bits as the concatenation of

as many 0 bit(s) as there are bits in the binary representation $k$
the binary representation of $k$, big-endian (thus starting with a 1 bit)
$c_1$
$c_2$

decryption parses the ciphertext

if it starts with 1 then it is elementary and what follows the 1 is deciphered normally;
otherwise, the ciphertext is composite; the number of initial 0 gives the length of the binary representation of $k$; $k$ follows; then $c_1$ follows on $k$ bits; then the rest is $c_2$; $c_1$ and $c_2$ are then deciphered, recursively.


How can I verifiably announce a choice without revealing its content?

This is the premise of a commitment scheme.  The dramatis personae in this setting are the prover, Peggy, who wishes to prove foreknowledge of a message $m$ to a verifier, Victor, but only later reveal $m$, at which point Victor can verify that Peggy didn't change her mind in the meantime.

For a message $m$, Peggy can commit to $m$ by choosing randomization $r$ and computing a commitment $c = C_r(m) \in \mathcal C$ which she gives to Victor while keeping $m$ and $r$ secret.  Later, when Peggy wants to reveal the message, she gives Victor $m$ and $r$, so that Victor can verify $c = C_r(m)$.  The commitment $C_r(m)$ should have two properties: it should reveal essentially no information about $m$ to anyone who doesn't know $r$, but it should be essentially impossible to to find $m' \ne m$ and $r'$ such that $C_r(m) = C_{r'}(m')$ and thereby break a commitment.

The first property is hiding, and can be formalized by putting a bound on the advantage of any (possibly cost-limited) adversary $D(c)$ to distinguish the commitment $C_r(m)$ of any message $m$ for uniform random $r$, from a uniform random commitment $c \in \mathcal C$: $\left|\Pr[D(C_r(m))] - \Pr[D(c)]\right|$.  If the distribution of $C_r(m)$ is exactly the same as the distribution of $c$, then this advantage is exactly zero, and the commitment scheme is said to be information-theoretically hiding; otherwise it is computationally hiding.

The second property is binding, and can be formalized by putting a bound on the probability of any (possibly cost-limited) adversary $F()$ to find $(r, m, r', m')$ with $m' \ne m$ such that $C_r(m) = C_{r'}(m')$.  (If it looks odd to see no parameters in $F$, that's because we usually instantiate it with a random oracle $H$ or a common reference string $\sigma$ and ask that of $F(H)$ or $F(\sigma)$.)  If there is exactly one message possible for every commitment, then this probability is exactly zero, and the commitment scheme is said to be information-theoretically binding; otherwise it is computationally binding.

Standard examples:

Hash commitments.
$C_r(m) = H(r \mathbin\| m)$, or $C_r(m) = \operatorname{HMAC-}\!H_r(m)$, where $H$ is a uniform random function chosen in advance so that Peggy and Victor have no influence over it, modeled as a random oracle in proofs, and implemented by a preimage- and collision-resistant hash $H$ like SHAKE128.

Hash commitments are only computationally hiding, but a distinguisher on this can be translated into a preimage attack on $H$, so if $H$ is preimage-resistant then a hash commitment is hiding; conversely a preimage attack on $H$ may enable an adversary to learn a secret commitment value.
Hash commitments are only computationally binding, but breaking a commitment on this can be translated into a collision attack on $H$, so if $H$ is collision-resistant then a hash commitment is binding; conversely a collision attack on $H$ may enable an adversary to break a commitment.  Consequently, for example, MD5 and HMAC-MD5 are unsuitable for $H$ even though HMAC-MD5 still seems to be a good PRF.

People sometimes use hash commitments on Twitter because it's convenient and everyone knows how to compute SHA-256 to verify them.
Pedersen commitments.
$C_r(m) = g^r h^m$, where $g$ and $h$ are elements of a prime-order group $G$ in which discrete logarithms are hard—elements chosen uniformly at random in advance so that Peggy and Victor have no influence over them, modeled as a common reference string in proofs, and implemented by protocols like FIPS 186-4, Appendix A.2.3 using hash functions like SHAKE128.  Here, unlike hash commitments, messages are not bit strings but elements of $\mathbb Z/\ell\mathbb Z$ where $\ell$ is the order of the group $G$.

Pedersen commitments are information-theoretically hiding, because $r \mapsto g^r h^m$ is a bijection with inverse $c \mapsto \log_g (c/h^m)$, so the distribution of $g^r h^m$ for uniform $r$ is uniform in $G$.
Pedersen commitments are computationally binding, because anyone who can compute discrete logarithms in $G$ can find $x = \log_g h$ so that $g^r h^m = g^{r + x m}$ and thereby can break commitments with arbitrary messages $m'$ by choosing $r' = r + x (m - m')$.  More specifically: if a Pedersen commitment breaker $F(g, h)$ can find $(r, m, r', m')$ with $m \ne m'$ such that $g^r h^m = g^{r'} g^{m'}$, then $\log_g h = \frac{r' - r}{m - m'}$, so anyone who can break a commitment in this scheme can compute discrete logs in $G$.

Pedersen commitments are also homomorphic: if $c_0 = C_{r_0}(m_0)$ and $c_1 = C_{r_1}(m_1)$, then $c_0 c_1 = C_{r_0 + r_1}(m_0 + m_1)$, and as such are convenient for fancy cryptography in zero-knowledge proof systems.  People sometimes use Pedersen commitments to (accidentally?) put back doors in electronic voting, in an attempt to prove that votes shuffled for anonymity were not forged in the process.  Pedersen commitments have a back door if Peggy can choose the elements $g$ and $h$: if Peggy chooses them to have a known relation $h = g^x$, then she can forge commitments as above and commit unrestricted vote fraud.
Elgamal commitments.
$C_r(m) = (g^r, h^r m)$, where $g$ and $h$ are elements of a prime-order group $G$ in which discrete logarithms are hard—elements chosen uniformly at random as a common reference string, etc., like Pedersen commitments.

Elgamal commitments are computationally hiding, because anyone who can compute discrete logarithms in $G$ can, given a commitment $(u, v)$, recover $r = \log_g u$ and $m = v/h^r$.  More specifically: an Elgamal commitment distinguisher can be turned into a decisional Diffie–Hellman attack on $G$, so Elgamal commitments are computationally hiding if DDH is hard, although conceivably DDH could be easy while DLOG is hard in $G$.
Elgamal commitments are information-theoretically binding, because there is exactly one possible message for each commitment.

Elgamal commitments are also homomorphic: if $c_0 = C_{r_0}(m_0) = (u_0, v_0)$ and $c_1 = C_{r_1}(m_1) = (u_1, v_1)$, then the elementwise product $c_0 c_1 = (u_0 u_1, v_0 v_1)$ is $C_{r_0 + r_1}(m_0 m_1)$.  I don't know who uses Elgamal commitments in practice.  Elgamal commitments have a back door if Victor can choose $g$ and $h$: if Victor can choose them to have a known relation $h = g^x$, then from a commitment $(u, v) = (g^r, h^r m) = (g^r, g^{x r} m)$, Victor can recover $m$ by $v/u^x = g^{x r} m / (g^r)^x = m$.


The sender chooses log n pairs of secret keys (say, for encryption). Then, each number between 1 and n is naturally associated with a subset of exactly log n keys. The protocol then works by running log n 1-out-of-2 OTs where the receiver asks for the keys that are associated with its input (number between 1 and n). Finally, the sender encrypts each of the n messages with the subset of keys associated with the number (using encryption so that without all keys nothing is learned).
It is not difficult to formally prove the security of this using simulation (as long as the OT is secure for malicious adversaries, this is also secure for malicious adversaries).
This solution goes back to a paper by Benny Pinkas [1].
[1] Moni Naor and Benny Pinkas. 1999. Oblivious transfer and polynomial evaluation. In Proceedings of the thirty-first annual ACM symposium on Theory of Computing (STOC '99). Association for Computing Machinery, New York, NY, USA, 245–254. DOI:https://doi.org/10.1145/301250.301312


Probably the best thing to do is to decide the maximum message size in bytes, then divide that size by 16 (the block size), call that $m_c$. The number of bytes required to encode $m_c$ is called $l_c$.

Create an IV of 16 bytes and randomize the first (leftmost) bytes, leaving at least $l_c$ bytes at zero. You then have a non-repeating counter of size $l_r$ bytes where $l_r = n - l_c$. That means that you can encrypt about $2^{l_r * 8 - 64}$ messages with the same key while still having a rather small chance of ever repeating the random nonce $r$ and thus the counter.

Time stamps are dangerous, an attacker can try and control the time, clocks can get out of sync, and there may be precision related issues. Time stamps are therefore commonly not used to create nonces - for encryption modes anyway. You don't want to use /dev/random either. Generally /dev/urandom is secure and at least it doesn't block.


Applied cryptographers often see one of the three variants of AES, say AES-256, as a function:
$$\begin{align}E:\ \{0,1\}^{256}\times\{0,1\}^{128}&\to\{0,1\}^{128}\\ (k,p)\quad &\mapsto c=E(k,p)\end{align}$$
such that:

for all $k\in\{0,1\}^{256}$, encryption with key $k$ defined as follows
$$\begin{align}E_k:\ \{0,1\}^{128}&\to\{0,1\}^{128}\\ p\quad &\mapsto c=E_k(p)\underset{\text{def}}=E(k,p)\end{align}$$
is injective, surjective, and bijective (the three are equivalent for any function over a finite set), that is a permutation of $\{0,1\}^{128}$
there's an efficient encryption algorithm computing $E_k(p)$ from $k$ and $p$
there's an efficient decryption algorithm computing $p$ with $c=E_k(p)$ from $k$ and $c$ (note: not quite as efficient, but close).
it is practically impossible to distinguish a challenger/oracle implementing these algorithms with a fixed unknown value of the key $k$ chosen at random, from an oracle implementing a random permutation and its inverse.

Note: Condition 4 is only good for keys chosen independently at random, which is the main design criteria for AES. It's not applicable to related-key attacks or the ideal cipher model.
Note: The quantitative security-oriented cryptographer compares the advantage of a distinguisher succeeding at 4 to that of a generic attack requiring the same work and trying keys in sequence, and to a no-nonsense threshold.

The more theoretical-oriented cryptographers want to formally define "efficient" and "practically impossible". They do so by stating that the algorithms involved are in the class of polynomial-time algorithms; and using the notion of negligible probability. But these require a "security parameter" that goes to $+\infty$ as the input of a polynomial, and AES is only defined for $|k|\in\{128,192,256\}$ and $|p|=128$, which are bounded.
To solve that, we can use that AES is formally defined as a restriction of Rijndael, and section 12.1 of that observes:

The  key  schedule  supports  any  key  length  that  is  a  multiple  of  4  bytes. (…) The cipher structure lends itself for any block length that is a multiple of 4 bytes, with a minimum of 16 bytes.

That section also tells how many rounds there should be, and how ShiftRow can be extended for 128, 192 and 256-bit block, that we can further extend.
For parameter $n\ge128$, we can take block size $|p|=32\,N_b=32\,\lfloor n/32\rfloor$ and key size $|k|=32\,N_k=32\,(N_b-3+(n\bmod 32))$, with $N_r=N_k+6$ rounds. We are back to a standard framework where algorithms are written for arbitrarily high security parameter $n$, fed as input to polynomial-time algorithms as a bitstring of $n$ bits, conventionally at 1. When $n=131$ (resp. $n=133$ and $n=135$) we get AES-128 (resp. AES-192 and AES-256). For $n=128$, we get a 128-bit cipher with a toy-sized 32-bit key.
But I do not know any security analysis of AES that cares to do something remotely similar and study attack on large $n$. This shows the gap between theory and practice!
Note: There would be other ways to make AES a family of block ciphers indexed by a security parameter. In particular, we could define variants working for more granular values of $|k|$ and $|p|$, and working in $\mathbb F(2^j)$ for $j$ variable, rather than $j=8$ as in AES; and/or tweak the $32=4\, j$ to another multiple of $j$. However that matches AES even less than the above, which is somewhat supported by a document referenced in appendix D of the formal definition of AES.


Good key update algorithms for key evolving schemes

AES is not irreversible, at least not when the key is known. I'd rather look at a PRF (Pseudo Random Function) rather than a PRP (Pseudo Random Permutation) such as AES.
A good PRF is HMAC. HMAC also has the nice properties of having no limit to the input message and a rather large, although statically sized output.

Even more specifically you might want to use a Key Based Key Derivation Function (KBKDF) such as HKDF - which is based on HMAC. A HKDF specifically takes input keying material to create output keying material.
It might be that KDF functions are e.g. present in hardware devices. This means that they keying material could stay into the hardware device, while ciphertext or HMAC values are commonly exported.


What is the structure of a Server Key Exchange Message structure when using a psk identity hint?

RFC 4279, section 5.2, says this about identity hints:

In the absence of an application profile specification specifying
otherwise, servers SHOULD NOT provide an identity hint and clients
MUST ignore the identity hint field.  Applications that do use this
field MUST specify its contents, how the value is chosen by the TLS
server, and what the TLS client is expected to do with the value.

So what this means is that it is up to you, the application designer, to define the hint structure. From the TLS point of view, the hint is an opaque sequence of bytes (no longer than 65535 bytes, but otherwise arbitrary).

In this answer, it is claimed that the "hint" was used directly in the key derivation system in the case of a protocol called "NETCONF", but this was dropped during the definition of the RFC (i.e. draft 4 has it, not draft 5 and subsequent). Even if the PSK support was not ultimately used in NETCONF, this shows how such a definition  is to be done: each protocol that leverages TLS-PSK is supposed to specify the hint format and processing.


What is an approximate length for a digital signature (SHA) in this case?

BLS signatures are $\:2\hspace{-0.04 in}\cdot\hspace{-0.03 in}k\:$ bits long, where $k$ is the security parameter, and the probability of a forgery is $\hspace{.01 in}\epsilon$.

Pseudorandom MACs (such as HMAC) can be truncated to $L\hspace{.01 in}$ bits, and the probability

of forgery (by someone who is outside of the system) will be $\: \frac{\text{# of tries}}{2^{\hspace{.01 in}L}}+\epsilon \;\;$.

(As alluded to in my comment, the verifier(s) can trivially forge valid authenticators for the MAC approach.)


Is there any place where I can find test vectors for point addition and doubling of ECC?

You can check Elliptic Curve Calculator.
It has point addition and scalar multiplication. For doubling, adding the same points(P+P) should do the work.


Encryption method that reduces the cipher text to a single byte

Single byte, no? How about 16 bytes? Sure. Encrypt using AES-128 with a random key. The key is now the "ciphertext" and the output of the encryption (what we normally call the ciphertext) is now the "key". Problem is, how do you distribute the "key"?

The thing is, from a real world perspective, the idea of shrinking the ciphertext and growing the key is a non-starter. Keys must be shared over a secure channel, ciphertexts do not. If you had a secure channel that was efficient enough to share large amounts of data, why not just share the plaintext directly over that channel and skip the whole encryption business?


Data decrypted, but unwanted characters in the beginning

If the data at the beginning is exactly 16 characters long every time, then it is certainly the initialization value for the CBC mode, and you can simply cut them off and output the valid data starting at byte 17.

My guess is that because that web decoder provides no specific input for the IV, it does not attempt to truncate the prefix itself, and simply outputs all the data, letting you decide what to do with it.


Machine Learning to improve Encryption algorithms

No. There is large consensus that:

There is nothing special about image encryption algorithm, they are just encryption algorithms.
ECC is useful for such algorithms inasmuch as they need to be made public-key. That's done by way of hybrid cryptography. Directly encrypting images with ECC cryptography would have terrible performance, thus is not worth serious consideration.
There's no clear need to improve any of these algorithms in a way where machine learning seems to be necessary or even helpful.

In a quite different direction: Machine learning also has a poor track record at attacking modern cryptographic algorithms, but that idea may not be worthless. Perhaps machines one day will learn cryptanalysis.


Error Correcting Codes Post Quantum Finalists

I want to investigate ECC/fault detection in hardware (or more accurately their lattice counterparts), specifically with one of the NIST finalists. Does anyone have any insights into this sector of Lattice Cryptography?

Actually, none on the NIST Lattice finalists (Kyber, NTRU, Saber) use error correction; for that matter, neither do the NIST Lattice alternates (Frodo, NTRUPrime).  Hence, that wouldn't be a promising avenue to research.  Several round 2 candidates (LAC, Round5, probably others) did, however they didn't make the cut.
As for fault detection, well, that's always a possible concern.  Glancing through the paper you cited, it would appear that they are concerned mostly about deterministic faults (e.g. a gate within the hardware breaks), and less about deliberate fault attacks (e.g. the attacker glitches the power supply at just the right time to cause a single value to be miscomputed).  You might consider investigating that (possibly starting with figuring out how out would perform a fault attack on the reference implementation, and using that to form a generalized concept about how a fault attack would work; then, you form a defense against that (assuming some limit on how powerful the attacker is; obviously, if he can fault things arbitrarily, he can make the hardware do anything...)

however none of the finalists use RLWE (as far as I can tell?)

No, but as ideal lattices, they aren't that different; of course, as a part of your thesis, you would need to explore them in detail...


You can decrypt with the -nopad option and check the HEX output.

Example piped command :

$ echo "hi"
| openssl enc -aes-128-cbc -e -K 1001001 -iv 0100110
| openssl enc -aes-128-cbc -d -nopad -K 1001001 -iv 0100110
| hd

And  output :

00000000  68 69 0a 0d 0d 0d 0d 0d  0d 0d 0d 0d 0d 0d 0d 0d  |hi..............|
00000010


Does humanly verifiable one time pad authentication exist?

I'll use $m\boxplus k$ for combining characters $m$ and $k$ by addition (modulo $n=28$) within the character set, or strings of individual characters of equal-length, rather than " m ⊕ k " in the question. I consider alphabetical ordering of $n$ (e.g. 28) characters with letters first, such that $\;\mathtt{'A'}\boxplus\mathtt{'A'}\;=\;\mathtt{'A'}\;$ and $\;\mathtt{'B'}\boxplus\mathtt{'C'}\;=\;\mathtt{'D'}\;$.

The question's method of sending $M\boxplus K_1\;\|\;M\boxplus K_2\;\|\;\dots$ is extremely insecure: replacing each ciphertext character $x$ by $x\boxplus\mathtt{'B'}$ is not detected, but correspondingly alters the message. There is a partial fix: for each character $m$ of the message, append to the message the character $m\boxplus m\boxplus m$, then encipher with OTP; since $\gcd(3,28)=1$, this makes altering a plaintext character precisely as hard (or easy) as guessing it. Even with that improvement, if the message (or a segment thereof) is known, it is possible to change it (or that segment) to anything desired, with certainty that the change goes undetected. That's insatisfactory.

Goals

Integrity check should be based on the plaintext, thus catching decryption errors (accidental or not) introduced by whatever deciphers, and avoiding the need to keep the full ciphertext for integrity check.
It shall remain convenient to decipher first (including while receiving), postponing integrity check.
Same unconditional plaintext confidentiality as OTP in ciphertext-only attacks, and only practically negligible leak under an attack model where the MitM gets to know if an attempted forgery succeeds or not. The receiver does not know the message length in advance. We posit integrity of the random pad, that it is synchronized between sender and receiver at the beginning of each message, and is never reused by sender or receiver.
In order to keep the integrity check feasible by hand, we restrict to use of the same $\boxplus$ as used for encryption, public latin square(s), random characters supplied by the random Pad (after those used by en/decryption), a moderate number of characters (or integer) variables (perhaps selection among these, and simple decimal arithmetic). Paper and pencil is OK (even if plaintext-leaking material gets written on it), a calculator is not.
The amount of work for integrity check should be minimized, as well as the transmission overhead, and drain of the random pad.
Quantifiable level of security against forgery, including with known plaintext (which makes sense if we do not fully trust whatever deciphers, see 1).

Circular buffer with latin square and addition (2017-06-03b)

We spare the first $s\ge2$ characters of ciphertext for integrity check, computed from the plaintext and the first $t\ge s$ characters of the random pad (or stream generator); think of $s=4$, $t=10$. The $s$ integrity check characters are computed by the sender, and optionally recomputed and verified by the receiver. All the rest is standard One Time Pad (or stream generator) and we do not further discuss encryption and decryption.

The system uses a single public $n\times n$ latin square; assume for now a random one.

For manual computation, the first $s$ characters of the random pad are written down (with - for space and + for the extra character). For each character of the plaintext, and then for each of the $t-s$ next characters of the random pad:

fetch the latin square at the line defined by that character, and the column defined the last character that was written;
combine the result using $\boxplus$ (addition modulo $n$ as used in the OTP) with the first character not striked-out (which is also the $s^\text{th}$ from the end), and strike that character;
write the resulting character following the $s-1$ characters not striked.

The $s$ characters remaining are the check characters.

(In)Security:

Each step combines the newly added character, leftmost and rightmost check characters, into a new check character, in a manner such that knowing 3 our of these 4 characters the other can be uniquely determined. It follows that the $s$ check characters remain uniformly distributed during the whole computation, for constant plaintext. No information about the plaintext can leak from the check characters, and information leak from acceptance/rejection is limited by the forgery rate.
The tight alternation of the latin square and $\boxplus$ combiners quickly and non-linearly diffuse changes; this is critical (forgery is trivial if we replace the latin square with $\boxplus$).
There is a forgery with $(n-1)^{-2}$ odds of success ($2\log(n-1)\approx9.5$-bit security): alter randomly two consecutive characters, then a third with $n-2$ non altered characters in-between. Slightly better strategies tailored to the latin square (and known/chosen plaintext if applicable) are possible. For the desired $n=28$ it is possible to objectively rank latin squares for their resistance to such attacks.
Security can't be better than $s\log_2(n)$-bit (forgery by random choice of check characters); nor than $(t-s)\log_2(n)$-bit for known plaintext (guess of the $t-s$ characters at end of computation).

That's calling for future work.

Methods in Mark N. Wegman and J. Lawrence Carter's New Hash Functions and Their Use in Authentication and Set Equality, in Journal of Computer and System Sciences 22 (1981) would be great, but I did not find something easy to perform without a computer.


From dictionary.university with search clearsigned definition

Dictionary of Internet Terms A digitally signed S/MIME or PGP message in which the content of the message is readable even if the signature is not.

A message that is digitally signed but not encrypted.

These might be helpful, too;

Cleartext  is readable data transmitted or stored “in the clear” (i.e. unencrypted)

Plaintext is the input to an encryption algorithm

Ciphertext is the unreadable output of an encryption algorithm

Plain text means its text that hasn’t been formatted (i.e., a plain text file)
Note that plain text might be an ambiguous term without context. See the commnets.


In RSA, given $n=100$ and $e=13$ ,Encrypt and Decrypt the plain Text "SECRET"

At least, there's an issue with using $n=100$ as the public modulus in RSA: that number is not squarefree. This implies that $m\mapsto m^e\bmod n$ can't be a bijection of the range $[0,n)$. And thus we must restrict the plaintext space to something lesser than $[0,n)$ if we want a deterministic decryption procedure.

Proof: if $n$ is not squarefree, there exists $s>1$ with $s^2$ dividing $n$. Let $m$ be an element of the subset $\mathcal S$ of $[0,n)$ with multiples of $s$. For $e>2$, $m^e$ is a multiple of $s^2$, which divides $n$. Therefore $s^2$ divides $m^e\bmod n$. Therefore $m^e\bmod n$ belongs to the subset $\mathcal T$ of $[0,n)$ with multiples of $s^2$. $|\mathcal S|=n/s$ and $|\mathcal T|=n/s^2$. Thus $|\mathcal S|>|\mathcal T|$. Therefore the function $f:\mathcal S\to\mathcal T, m\mapsto m^e\bmod n$ is bound to collide. Such collision is also a collision for RSA encryption on $[0,n)$.

For example, with $n=100$ and $e=13$, $m_A=65$ and $m_U=85$ both encipher to $25$. This means we can't even reversibly encipher the uppercase ASCII alphabet. If we try to use $c\mapsto c^d\bmod n$ for $d=e^{-1}\bmod\varphi(n)$ as a decryption function, it will sometime fail. For example, $m_R=82$ enciphers to $c=32$ and deciphers to $32\ne m_R$.


Feedback requested on a method of posting a message without revealing the author

So a fundamental property of  multi-party anonymous systems is you are only anonymous out of the number of honest participants in the system. If the Stasi control everyone else at the dinner table and know they didn't send the message, then they know you did no matter what protocol you use.

In your case with this ring topology, because only your two adjacent neighbors  in the group know about you and therefore you only interact with them, they only need to be malicious. Specifically, if the member's before and after you collude by cutting you out of the real network and putting you in one that just involves the two of them, then they will know you sent the message when you complete the protocol and remove your key.


Constructing RSA private key, given public key

OpenSSL private key format, for RSA, follows the ASN.1 syntax given at the end of PKCS#1 (the structure is then encoded with DER, then Base64, and PEM header and footer lines are added). This is easy if you know these formats, but, in practice, you will be happier if using a library which does the encoding for you. For instance, OpenSSL (the library) lets you create a private key as a bunch of big integers (because that's what a RSA private key is -- again, read PKCS#1).

That being said:

  I can determine p and q by using an arbitrary precision library and iterating through until I find something that satisfies N mod p = 0

I hope you are patient !

(Hint: read this. Factoring a 256-bit integer is feasible, but not immediate. You'll need a bit of computing with a smart algorithm like quadratic sieve.)


This seems entirely straight forward. Each player publishes a commitment, essentially a hash of their board. Possibly signed.

If the boards are not high enough entropy themselves we will tack on some random data to increase their entropy to make the result unguessable.

When a player declares victory he will provide a Zero Knowledge proof that he knows of a winning board matching his commitment.

Note Zero Knowledge proofs are very powerful stuff, but we need to open the black box of the functions we use (such as hashing) in order to use them. For any efficiently computeable predicate function $f$ we can prove we have $x$ so that $f(x)=true$ without revealing anything about $x$ beyond the statement.

In our case we would have $f(board)$ be the predicate which checks the board is a winning board and matches our commitment. Obviously trivial to compute.


Well, yes, but you cannot use the key $k_1$ for anything else because knowledge of $k_1$ would mean that an attacker can simply calculate $k_2$. If an attacker can find a direct relation between parts of the output then the function is of course not pseudo random anymore. So although it is possible it seems pretty useless to me.

Even if you would not directly use $k_1$ as output you would need to prove that you use it in such a way that security is not compromised. In general you should try to not reuse keys for different purposes.


All the Quagmire ciphers (see e.g. here for definitions) are combinations of a Vigenère shift cipher and a keyword-based simple substitution cipher, where the substitution cipher is used to scramble the alphabet before and/or after the Vigenère encryption.

In particular, the Quagmire III cipher in effect scrambles the plaintext alphabet before doing a normal Vigènere encryption (with a key that is derived from the "indicator" by also scrambling its alphabet the same way), and then unscrambles the alphabet of the resulting ciphertext.  Equivalently, we may view it as just a Vigenère cipher, but using a non-standard (and typically secret) mapping from letters to numbers instead of the usual A=0, B=1, C=2, etc.

This has a couple of notable consequences:

All the usual methods of determining the key length for a Vigenère cipher, like Kasiski examination or calculating the index of coincidence, will work just as well for a Quagmire cipher, at least as long as they make no explicit assumptions about which letters are most common in the plaintext.
Once you've determined the length $k$ of the repeating Vigenère key (a.k.a. "indicator"), you can simply take every $k$-th letter of the ciphertext and apply frequency analysis just as if you were attacking a simple substitution cipher (since that's effectively what you have at this point).

Furthermore, the $k$ different substitution alphabets corresponding to the $k$ different indicator letters are related in a particular way: mathematically, they are all powers of the same cyclic permutation (in the strict sense; no fixed points allowed) of the alphabet.  (This is also true of the basic Vigenère cipher; in that case, the underlying cycle is simply the one-letter shift A → B → C → ... → X → Y → Z → A.)  Thus, once you manage to solve one of the $k$ substitution ciphers, the rest should be significantly easier (and you can also compare the solutions to make sure they are correct).

Also, the cycle structure of a power of a cyclic permutation is itself somewhat restricted: it cannot have fixed points (unless it is the identity permutation) and all of its cycles must have the same length that divides the size of the alphabet.  In particular, for a 26-letter alphabet, the power of a cyclic permutation always consists of either one 26-cycle (making it also cyclic), two 13-cycles, 13 two-cycles or 26 fixed points (in which case it is the identity).  Of these, the first two possibilities (one 26-cycle or two 13-cycles) are by far the most likely, so if you see anything else (especially if it's not one of the remaining possibilities above), you'll know that you've made a mistake somewhere.

Given sufficient ciphertext, breaking this cipher via the methods described above shouldn't be particularly difficult.  Indeed, determining the key length using the index of coincidence method doesn't even need all that much ciphertext; I tried it on the Kryptos K1 and K2 ciphertexts (using a Wilson score interval correction to reduce sampling noise for large key lengths) and it pretty clearly identified the key length of K1 (63 letters) as 5, 10 or 20 letters (actual keyword: PALIMPSEST, 10 letters) and the key length of K2 (369 letters) as most likely 8 letters (actual keyword: ABSCISSA).  However, with a limited amount of ciphertext and a long key, solving the individual substitutions may require a considerable amount of trial and error.

Also, it's worth noting that this method does not automatically yield the keywords used to encrypt the text.  Indeed, it cannot, since the Quagmire ciphers have many equivalent keys.  However, simply considering all the possible solutions for the substitution alphabet and the shift amounts may turn up one that arises from a particularly natural pair of keywords.


How can one generate pairs/triplets/.../n-ary MD5 collisions

MD5 is a Merkle–Damgård hash, so it's vulnerable to the length extension attack.

That means there's a simple way to find multicollisions using any algorithm that can find collisions for an arbitrary IV:

Find some collision $\operatorname{MD5}(a) = \operatorname{MD5}(b)$ using the normal IV.
Find another collision $\operatorname{MD5}'(c) = \operatorname{MD5}'(d)$ using the output from the first step as IV.
Combine them to valid messages that look like $a||c$, $a||d$, $b||c$ and $b||d$, except for the padding. This may require adding one more (equal) message block to get a valid padding and length.


For encryption with a passphrase, should you re-use the same salt for key generation?

The purpose of a salt started with password storage. Within the very common use-case of using a hash function to store usernames and passwords, unsalted password hashes reveal which users have the same password. This reveals a lot of information about the underlying passwords and would make password hash "cracking" much more efficient.

In your use-case you are not dealing with hashed passwords but password-derived keys, however, the use-case for salts is similar. Would it be an acceptable design for your vault to reveal that all ciphertexts are encrypted using the same derived key? If, for example, your vault allowed users to specify per-file passwords for key derivation a static salt may reveal that multiple files used the same password to derive their encryption key.


Distribution of randomness in elliptic curve Diffie-Hellman shared secret

Fix a short Weierstrass curve $y^2 = x^3 + a x + b$ over a finite field $\mathbb F_p$ of order $n$.  (secp224r1 is an example, with $p = 2^{224} - 2^{96} + 1$, $a = -3$, and $b$ selected from an allegedly randomly chosen but unexplained seed passed through SHA-1.)

There are at most $n$ distinct values of $(x, y) = [\alpha \beta]G$ where $\alpha$ and $\beta$ are secret scalars in $\mathbb Z/n\mathbb Z$ and $G$ is the standard base point, all satisfying this equation.

If you choose uniformly among them, e.g. by choosing $\alpha$ and $\beta$ independently uniformly at random, and encode the pair $(x, y)$ into a $2 \lceil\log_2 p\rceil$-bit string, there is a trivial algorithm to distinguish the resulting string from a uniform random $2 \lceil\log_2 p\rceil$-bit string: decode it as a pair of integers $x$ and $y$ and test whether $y^2 \equiv x^3 + a x + b \pmod p$.  So not only do the encoded values of $(x, y)$ cover a tiny fraction of the space of $2 \lceil\log_2 p\rceil$-bit strings—square root of the number of all such strings of that length—but they're trivial to distinguish from uniform random.

But that's partly because for each $x$, there's only at most two values of $\pm y$, so we can compress it into a much shorter $(1 + \lceil\log_2 p\rceil)$-bit string by storing only a bit to discriminate between the two possible values of $y$.  Is that uniform random?  No!  If you decode $x$, you can test whether $x^3 + a x + b$ is a quadratic residue modulo $p$, which only about half of the integers are.

Distinguishers for the encoding of uniform random elliptic curve points were some of the first problems documented publicly in Dual_EC_DRBG[1], before everyone realized it was an obvious vector for a back door.

In general, when a random string is readily distinguishable from uniform like this, it is unfit to be used as a secret key in a cryptosystem whose contract demands a uniform random key—if you violate the security contract, it is null and void.  But if the random string, while not uniform, nevertheless has high min-entropy, you can effectively get a uniform random string by hashing it, say with SHAKE256—what this means is that the best an adversary can do is test a guess about what the input might have been.

As for the low-order or high-order bits of $x$ and $y$?  Don't bother; just hash them all.  The cost of computing a hash like SHAKE256 is negligible compared to the cost of computing an elliptic curve scalar multiplication even on a small curve like secp224r1.


Public Key Encryption with forward secrecy

One approach can be found in this paper by Canetti, Halevi and Katz.  To summarize the approach:

This generate a tree of private keys; from a node, you can generate private keys downwards (to child nodes), but you cannot compute upwards (to the parent nodes).  This achieves forward secrecy by generating child nodes and erasing parent nodes.
The public key can be used to encrypt to any private key node; if we have the private key for that node (or we can generate it because we have one of its parents), we can decrypt the message; if the private key for that node has already been erased, we cannot.
The size of the public key is constant (that is, independent of the number of time steps supported).
The size of an encrypted message is $O(\log t)$ (where $t$ is the number of time steps supported).
The size of the private key for the entire system is $O(\log t)$; this includes the number of private keys nodes stored in memory at any one time.
Encryption and decryption both take $O(\log t)$ time.
The algorithm uses a bilinear mapping that meets the BDH (Bilinear Diffie-Hellman) assumption.


Use the Index Calculus to solve for $19^x \equiv 205\pmod{337}$, using the factor base $B=\{2,3,5,7\}$

The trick is to take logarithms. The information you have above can be translated as
$$
\begin{align}
2 &= 3\cdot \log_{19} 2 + 1\cdot \log_{19} 3 + 0\cdot \log_{19} 5 + 0\cdot \log_{19} 7 \pmod{336} \\
5 &= 5\cdot \log_{19} 2 + 0\cdot \log_{19} 3 + 1\cdot \log_{19} 5 + 0\cdot \log_{19} 7 \pmod{336} \\
 & \dots
\end{align}
$$
This is basically a linear equation system modulo $336$ (the order of $19$ modulo $337$), at the end of which we obtain the logarithms of $2$, $3$, $5$, and $7$ in base $19$, which are $160$, $194$, $213$, and $6$. (This might require solving the system modulo each factor of $336 = 2^4 \cdot 3 \cdot 7$ individually and recombine with the Chinese remainder theorem).
Having those logarithms, we can use one of the other equations to find the logarithm of $205$. For example,
$$
205\cdot 19^{-1} = 2^6 \cdot 3^0 \cdot 5^0 \cdot 7^0 \pmod{337}
$$
can again be translated as
$$
\log_{19} 205 - 1 = 160\cdot 6 + 194\cdot 0 + 213\cdot 0 + 6\cdot 0 \pmod{336},
$$
from which we easily obtain $\log_{19} 205 = 160\cdot 6 + 1 \bmod 336 = 289$.


Why do 1st and 3rd key have to be the same in 2 key 3DES?

In two key 3DES two keys are equal so that key size is only 112 bits, compared to the 168 bits of full 3DES. The advantage is a smaller key size without a correspondingly large loss in security: both two and three key 3DES can be attacked in about $2^{112}$ time.

With the encrypt-decrypt-encrypt construction it clearly must be the first and last key that are equal, since having two adjacent keys equal would make the decryption and encryption cancel out. Even with EEE it would have been weak to have equal keys adjacent: it would effectively be a cascade of two 56-bit strength ciphers (DES and double-DES), which a standard meet-in-the-middle attack breaks in roughly $2^{56}$ time.

So having the first and last keys equal is the only option that makes sense.


Is there a point using GCM block chiper with Authenticated DH?

Unless you are absolutely sure that you don't need to and that the cost is going to be significant then I would absolutely say you should use authenticated encryption.
One reason is bit-flipping attacks - flipping a few bits at the 'right' point in your encrypted message might lead well to a message that is legal (the classic example is if someone learns your message will be of the form ??<misc secret unknown format stuff>???  Send Bob ???<more unknown stuff>??? then they can xor the 'Alice' section with Bob$\oplus$Eve).

Another example that could well affect you would be a replay attack where an old message is sent again, and because you are not authenticating the messages the server wouldn't realise.  There's a nice reference somewhere to an old computer game that players managed to cheat by continuously replaying the 'Killed Beast' message, but I can't find it at the moment.

You might find this question relevant.


Why is factoring $p-1$ easy when $p$ is a safe prime?

If $p=2q+1$ is a safe prime (that is, $q$ is a prime as well), then $p-1=2q$ has exactly two prime factors: $2$ and $q=(p-1)/2$.


Regarding matsui's Paper on Linear Cryptanalysis of DES

Let us denote by $x = x_5x_4x_3x_2x_1x_0$, where $x_i \in \{0, 1\}$ the input of a DES S-box and by $y = y_3y_2y_1y_0$, with $y_i \in \{0, 1\}$ its output. Basically, $\mathrm{NS}_5(16, 15) = 12$ means that for S-box #5, the relation $x_4 = y_3 \oplus y_2 \oplus y_1 \oplus y_0$, where $y = S_5(x)$, holds with probability $\frac{\mathrm{NS}_5(16, 5)}{64} = \frac{12}{64} = \frac{1}{2}-\frac{5}{16}$, which is a fairly biased value (one would expect this value to be very close to $\frac{1}{2}$ in an ideal situation).

Starting from this observation, Matsui builds the 1-round linear approximation $X_{15} \oplus F(X, K)_7 \oplus F(X, K)_{18} \oplus F(X, K)_{24} \oplus F(X, K)_{29} = K_{22}$ that holds with the same probability $\frac{1}{2}-\frac{5}{16}$. Note that, for S-box #5, $x_4$ can be traced back to $X_{15} \oplus K_{22}$, taking into account the $\mathrm{EP}(.)$ transformation as well as the key-schedule algorithm, and $y_3y_2y_1y_0$ can be propagated to bits 7, 18, 24 and 29 of the output of the round function, this time taking into account the effect of the bit permutation $\mathrm{P}(.)$.


Strength of CBC with Ciphertext Stealing

In their 2012 paper "The Security of Ciphertext Stealing", Phillip Rogaway, Mark Wooding and Haibin Zhang prove that all the NIST-approved ciphertext stealing modes provide the same level of security as ordinary CBC mode, i.e. ciphertext indistinguishability under a chosen-plaintext attack.  To quote their abstract:

  "Abstract. We prove the security of CBC encryption with ciphertext stealing. Our results cover all versions of ciphertext stealing recently recommended by NIST. The complexity assumption is that the underlying blockcipher is a good PRP, and the security notion achieved is the strongest one commonly considered for chosen-plaintext attacks, indistinguishability from random bits (ind\$-security). We go on to generalize these results to show that, when intermediate outputs are slightly delayed, one achieves ind\$-security in the sense of an online encryption scheme, a notion we formalize that focuses on what is delivered across an online API, generalizing prior notions of blockwise-adaptive attacks. Finally, we pair our positive results with the observation that the version of ciphertext stealing described in Meyer and Matyas's well-known book (1982) is not secure."

In particular, in section 3 of the paper, the authors write:

  "Turning now to the CBC-CS modes, we claim that these inherit CBC's security
  with no quantitative degradation. The needed observation is that $\text{CBC-CS1}^{IV}_K(P)$
  is just $\text{CBC}^{IV}_K(P\ 0^∗)$ (minimal padding to the next multiple of $b$ bits) with some bits excised and some bits reordered. Which bits are excised and how bits are rearranged depends only on $|P|$. Thus if $\text{CBC}^{IV}_K(·)$ looks random, so too will look $\text{CBC-CS1}^{IV}_K(·)$. The same comments hold for CBC-CS2 and CBC-CS3; these are
  just diﬀerent rearrangements of the bits of $\text{CBC}^{IV}_K(P\ 0^∗)$. The observation and proof are formalized by the proposition below."

Edit: It should be noted that all these indistiguishability results assume that the length of the plaintext (and corresponding ciphertext) is fixed and known to the attacker.  If used to encrypt variable-length messages, all the commonly used block cipher modes of operation leak information about the length of the plaintext.

As you correctly note, CBC mode without ciphertext stealing does leak slightly less information about the plaintext length than other modes (like CFB, OFB, CTR or CBC-CS), since in traditional CBC mode the message is padded to the next multiple of the cipher block size (usually 8 or 16 bytes).  However, this incidental side effect isn't really something you should generally rely on to conceal your plaintext lengths, at least unless you can be sure that just knowing whether or not, say, a message is less than 16 bytes long won't ever be the critical piece of information the attacker is looking for.  Instead, if you do care about concealing the length of the plaintext, you should pad your messages yourself to some fixed length before encrypting them.


Why is Byte-at-a-time ECB decryption a vulnerability?

The vulnerability happens when:

You send an INPUT to the server.
The server appends secret to INPUT -> INPUT||secret
The server encrypts it with a secret key -> encrypt(INPUT||secret, key)
The server returns, or you get access in some way to the resulting cipher.

Let's assume the block size is 8. Steps;

All you have to do to decrypt the first byte of "secret" is to send a block of 7 bytes (block size -1). Let's assume we send: AAAAAAA. We get a cipher back, this cipher is our "target".
Next we try AAAAAAA with every other possible bytes: AAAAAAAA, AAAAAAAB, AAAAAAAC, ... Let's assume the cipher returned at STEP1 is the same as when we send AAAAAAAw. That means we know for sure the first byte of the secret is w. We discovered the first byte, yay!
Send 6 bytes (block-size - 1 - known bytes) + w (the byte we discovered previously). Get cipher.
Brute force the last byte until you know the second bytes...  Repeat all steps until you discovered secret.

See? We never actually needed to know the key and yet we discovered secret.

A concrete scenario where this could happens:

Website creates a secret code for each user for the duration of their session, but wants to remain stateless so it saves the code in their cookie, encrypted. Except that the cookie also contains the username (which the user can control/modify). Now the encrypted cipher is username||secret_code. Given this scenario, a user can easily find out what his secret_code is.


Any course material or book with a title like introduction to cryptography (or similar) will address this topic and provide examples. Alternatives are: Frequency analysis and substitution cipher.

The basic steps are:

Decide on what you want to count: Usually first you look at single symbols first. And then bigrams. But there are other possibilities (bascially any pattern you can imagine)
Count the appearances
Put them into relation of the possible maximum count. That's a frequency.

The expression "pictogram cipher" doesn't say anything about the actual encryption mechanism. Using arbitrary symbols or pictures instead of numbers is just a form of encoding, and pretty much irrelevant, as long as you can distinguish them somehow.

However, in general we assume that it is known what kind of cipher we have. And based on that, there are different ways to do frequency analysis. Under the tag classical-cipher you can find a lot of questions to this topic. For example Possible ways to crack simple hand ciphers might be interesting to read.


How is a PRP different from PRF? Both can be inverted to get the same input

Indeed as you noted the primary difference between a PRP and a PRF is that a PRP must be bijective whereas a PRF doesn't have to. This also means that PRFs admit collisions, that is there may exist a key $k$ such that for two different inputs $x,x'$ $F_k(x)=F_k(x')$, whereas this is guaranteed to be impossible for PRPs.

  In counter mode it is said that we are using a PRF and not PRP (unlike
  CBC) i.e. we are not using the decryption capabilities of block
  cipher.

A different way to think about counter-mode is to consider the keystream blinding the message. Then on the receiving end you reproduce the blinding and unblind the message.

Whereas with other modes like CBC you actually run your message through your function, which means you need to have a bijection in order to recover your original message unambigously.


Solving Quadratic equations in Galois Field (2^163)

I'll try to give additional explanation on algebraic number and the link with EC.

Let $q=2^{163}$ the finite Field $F_q=GF(q)$, as selected by NIST has some features for doing cryptography. This field has been generated with the irreduccible pentanomial you gave in the table.
To understand what the trace of the polynomial is, it corresponds to the coefficient of monom of degré 162, which is Zero in this case. And remembering that any finite field could never be algebraically closed, we can considere all the 163 roots of p, $\{x_0..., x_{162} \}$, which are conjugate each other. The trace of the polynomial is simply the sum of all its roots.
But as they are all conjugate, only one root suffices to calculate the trace by repeating square. (Cf ref books).
Then we see, that we can define the trace of any element in $F_q$ by  $Tr(\alpha)=\sum_{i=0}^{i=162}\alpha^{2^{2^i}}$.
This define a linear map (endomorphism) from $F_q$ to $F_2=\{0,1\}$!

Now the "Trace" map, is useful to help in solving quadratic equation. if $\lambda$ is a solution in $F_q$ of $\lambda^2 + \lambda = b$, then so is $\lambda+1$. This show that the equation is solvable only if $Tr(b)=0$

And the link with EC ? As fkraiem observes it, you have nothing to do! NIST has done all the work by selecting the field of appropriate size, generating polynomial and indicates how to get the trace for any algebraic element in $F_q$. For this case of K-163 (Koblits Curve) or B-163 (random Curve), and a given $\mu \in F_q$, $Tr(\mu)=\mu_{157}+\mu_0$ snipped from the table you show us.

When we want to select randomly a point on a given standardized curve EC: $y^2+xy=x^3+a_2.x^2+a_6$, we begin by chosing the abscisse $x\neq 0$, and then try to compute the corresponding y!
setting $z=\frac{y}{x}$ gives $z^2+z=x+a_2+\frac{a_6}{x^2}$, which allow us to understand why the trace of the second member must be Zero in the algorithm 2 shown above.

The Half Trace, can be explained by the fact that in a finite field there is exactly the same number of quadratic and Non-quadratic residues.

Then the Half trace is defined by $\tau(\alpha)=\sum_{i=0}^{\frac{n-1}{2}}\alpha^{2^{2i}}$(Ref N. Smart Elliptic Curves in Cryptography), which gives the solution of the equation. There are generally 2 solutions, and you can select one to build the point, the other allow to select the opposite point.
And when a solution is chosen, the point is $P=(\alpha, \lambda.\alpha)$, and a straiforward calculation allow to check that it belong to EC!

@user3368764: I'd a look to the paper you indicate. They use a tower factorization of finite field $GF(2^{178})$. As 178=2.89, a first field extention $GF(2^{89})=GF(2)/(u^{89}+u^{38}+1)$, followed by $GF(2^{89})/(v^2+v+1)$ allow to get $GF(2^{178})$. If you plan to design a hardware for $GF(2^{163})$ it can't be used for another field. Arithmetic in Binary is simple, but unfortunaltly not flexible.

Now Let's return to Nigel Smart's book for depicting the solution of $\lambda^2+\lambda+\beta=0\cdots$!  Recall that any finite field of $q=2^{163}$ elements, field'elements are charaterized by $X^q=X$. Then with the definition of Half Trace : $$\tau(\beta)=\sum_{i=0}^{\frac{n-1}{2}}\beta^{2^{2i}}=\beta+\beta^{2^2}+\beta^{2^4}+\cdots+\beta^{2^{n-3}}+\beta^{2^{n-1}}$$
In a binary field, the square is a linear operator, which gives:
$$\tau(\beta)^2=\beta^2+\beta^{2^3}+\beta^{2^5}+\cdots+\beta^{2^{n-2}}+\beta^{2^{n}}$$
As $\beta^{2^{n}}=\beta$, it remains: $\tau(\beta)^2+\tau(\beta)=\beta+Tr(\beta)$ which mean that if $Tr(\beta)=0$; then $\tau(\beta)$ is a solution of the quadratic equation


TL;DR: GCM has been shown to be secure, which is not the case for encrypt-then-HMAC.

There are a few things to distinguish here. First is the  difference between asymmetric and symmetric cryptography. If messages are encrypted with the public key of the recipient and signed with the private key of the sender then there is a clear difference in key usage. Obviously the private keys when sending messages are kept by different parties. Now these parties could use the same key for decrypting and signing, but these keys may well have different life times. For instance, it may be that you want to decrypt messages in the far future, meaning that you need to keep the private decryption key. However, generally you don't need to keep the signing key; you can still verify messages with just the public key and replace the signing key with the new key.

However, with an authenticated cipher such as GCM we're commonly dealing with session keys. The session keys for confidentiality and integrity protection / message authentication are commonly generated at the same time. So there is no need to have separate life times or access conditions for them.

Another reason to use separate keys are algorithmic vulnerabilities. Cryptographic algorithms will always be designed to keep the key secure. However, the algorithmic proofs (or at least indications of security) generally do not consider usage of the key in other algorithms. Imagine you have a set of equations trying to show security. Now mix those equations with a whole new set of equations from another algorithm that uses the same variables, and try to show that security holds. This is generally impossible, meaning that any security reduction is likely void.

In the worst case the encryption algorithm and MAC use similar constructions. In that case it might well be that the resulting set of equations is actually insecure. A good example of this is a block cipher mode in CBC mode that uses CBC-MAC. It is easy to prove that this scheme can be insecure when used with the same key.

HMAC is a completely different scheme than any block cipher mode of operation. That makes it very improbable that re-using the key for authentication will lead to vulnerabilities. However, it will also be next to impossible to prove that there aren't any, so it is therefore still not recommended to reuse the encryption key for authentication with HMAC.

A slightly less serious issue is that keys may not be usable for different algorithms. For instance, a HMAC-SHA512 (SHA-512 is often faster than SHA-256) key cannot directly be used for AES encryption, as the maximum key size of AES is 256 bits. For software this may not be a huge issue, but generally keys are generated for a specific algorithm. This is especially an issue on hardware modules, where the key data can often not be retrieved. It would be impossible to use a HMAC key as an AES key.

So it may be easier to have one input secret that can be fed into a key derivation mechanism such as HKDF. This mechanism can then be used to derive the encryption and authentication key. This is an easy way to split one secret key into two secret keys. Obviously this option is not available in the setting that requires asymmetric cryptography.

For AES-GCM the key is only used in AES-CTR mode. This mode is both used for protecting the GMAC value (with a specific counter value) as well as keeping the message confidential. This construction is shown to be secure in a paper that is unfortunately payware. This proof has been studied by other cryptographers and shown to be valid. There have certainly have been results that have shown weaknesses in the GCM construction with regard to construction of the authentication tag and derived authentication key, but the overall security claims have withstood the issues - after some tweaking.

So unless further holes in the security claims will be found, AES-GCM should be secure even though it just requires one key.

For the scholar, here is the security claim in the original paper:

  GCMis secure in the concrete security models introduced by Bellare, Killian, and Rogaway [20] for
  message authentication, and Bellare, Desai, Jokipii, and Rogaway for confidentiality [22], against
  adversaries that can adaptively choose the plaintext, the additional associated data, and the IV
  (as long as the requirements on these inputs are respected). Its security relies on the fact that
  the underlying block cipher cannot be distinguished from a random permutation, an assumption
  which is common in cryptographic designs and which appears to be valid for the AES.

And here is a link to a freely available draft that is likely the source for the linked-to payware paper in the previous section: Flexible and Efficient Message Authentication in Hardware and Software


Do sites store login password with hash? If so, can people can use hash collision to log in?

Databases generally store hashed passwords (as they should), but some store it plaintext.  If someone were to find a hash collision that matched the stored, unsalted, and hashed password, then yes, they would be able to use that collision to login, because the client would send the password to the server, the server would calculate the hash and compare it to the one in the database. Since the two match (different input, same hashed value), login would  succeed. However, I might like to add, it's more computationally feasible that one would bruteforce the password as opposed to finding a collision, especially with the generally small size of a password.


Security of 64-bit truncated HMAC of Matrix protocol

I once had a similar question, and the answer is that: MAC forgery attack targets interacting parties, where as other types of attack such as key-guessing and message decryption targets static messages.

To attack interacting parties with MAC forgery, you can only know if you succeed after they've replied decryption success/failure indication, by which time they would probably have terminated the communication or re-keyed.

On the other hand, if you've enough money to spend on a supercomputer to crack a 64-bit key to decrypt a ciphertext, you can wait as long as you want, and each failure doesn't cause you to start all over again - you can continue where you left.


Why do these Python XTEA implementations require different deltas?

If you take a close look at line 105 of the C++ implementation, you see that it subtracts delta from the sum instead of adding it:

103            for (int32_t i = 32; --i >= 0;) {
104                    v0 += ((v1 << 4 ^ v1 >> 5) + v1) ^ (sum + k[sum & 3]);
105                    sum -= delta;
106                    v1 += ((v0 << 4 ^ v0 >> 5) + v0) ^ (sum + k[sum >> 11 & 3]);
107            }

Since $\textrm{0x61C88647+0x9E3779B9}=2^{32}$, this is equivalent to adding the "normal" delta.

A rather odd design choice, if you ask me, but it works.