Crypto system design : How to design Encryption for Zero width characters

First of all, the use of zero-width characters is what we call obfuscation and indeed stenography. The encryption part that is described seems separate from it.

Generally we don't encrypt each element separate, we encrypt the plaintext and then try to hide the plaintext. Encryption generally needs something to make the key / IV unique otherwise you would get the same ciphertext for identical messages. In your situation it is only safe to use a fixed IV if a unique salt is used for each key that you derive from the password using a password based key derivation function or PBKDF. Of course, instead of having to store an IV you'd now have to store a salt.

CTR mode only requires a nonce rather than an unpredicatable IV. The nonce is a unique value of any size. Because of that the overhead of using the IV is much smaller. Alternatively, if you're stuck to CBC + CTS, you can use a nonce as IV for CBC by encrypting that initial IV with AES to derive the actual IV. IN both cases you might need to right pad the (initial) nonce with zero bytes before you can use it.

I don't see anything about a PBKDF in your description so your design probably still needs a lot of work. However, you are seeing the problems and you ask the right questions, and at this stage that might be more important.


No, it is not collision-free. All possible sequences of 0's produce the same output:

0    --> (2 ** 0) = 1
00   --> (2 ** 0) * (3 ** 0) = 1
000  --> (2 ** 0) * (3 ** 0) * (5 ** 0) = 1
0000 --> (2 ** 0) * (3 ** 0) * (5 ** 0) * (7 ** 0) = 1

In fact, it can be seen that $f(s) = f(s||0)$, for every bit-string $s$.

This could be easily solved by initializing the exponents to 1, and not to 0.

Anyway, I'm afraid you have not discovered anything new. The Fundamental theorem of arithmetic states that any positive integer can be represented uniquely by a product of prime numbers:

$$n
= p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}
= \prod_{i=1}^{k}p_i^{\alpha_i}$$

Your idea is basically a method for interpreting the bit string as the sequence of exponents $\alpha_1, \alpha_2, ..., \alpha_{k}$.

It is also very easy to invert (leaving aside the issue of the number of trailing 0's). Let us assume that $f(s) = n$. If $n$ is divisible by 2, then the first bit of $s$ is 1. Now you divide by 2 and if the result is divisible by 2, then the next bit of $s$ is also 1. Repeat until it is not divisible by 2, and you know the next bit is 0. Repeat this process with the divisibility of 3, 5, 7, etc.

With respect to the new question you added: yes, there are collisions.

For example: $f(1) = f(2) = f(4) = ... = f(2^k) = 2$

In fact, for any integer $n$, it can be seen that $f(n) = f(n\cdot 2^k)$, for every integer $k>0$, which means that for each integer there are infinite collisions.


Signature using RSA (as described in Cryptography engineering)

The pseudocode shown is correct.

It works because  is a function in the mathematical sense; and in particular, always returns the same result for the same arguments $(n,m)$. This is possible because it internally uses a Pseudo Random Number Generator (PRNG), rather than a True RNG (wich indeed would make the signature verification fail).

The rationale for using a (P)RNG to transform the message $m$ into the message representative $s$ is that the (conjecturally hard) RSA problem is to invert the public key function $s\to s^e\bmod n$ for a random $s$ in interval $[0,n)$. If we used $s=m$, or a simple transformations (e.g. $s\ =\ (a\;m+b)\bmod n$ for some public constants $a$, $b$ ), an attack would often be tractable. The signature system proposed has some level of reducibility to the RSA problem.

RSASSA-PSS of PKCS#1v2, and RSA per ISO/IEC 9796-2 scheme 2, are signature systems which combine a PRNG and a TRNG in preparing the message representative $s$. The TRNG insures that an adversary can not predict or choose which $s$ the legitimate signer will use, even if given the opportunity to choose the messages signed. This allows stronger/simpler security reduction.


Given the information in the question and in the comments, this is pretty straightforward:

Online phase: Use any common key agreement protocol, e.g. Diffie-Hellmann key exchange to generate a shared secret.
Offline phase: Use a proper key derivation function on the shared secret and a nonce - one nonce for each key you need to generate. A counter would also work.

  I need implemented and secure solutions.

Both functionalities should be included in various cryptographic libraries.

For the security it is necessary to make sure that the shared secret is stored securely. But that's basic key management.

For the security proof you could argue that the KDF is actually a PRF or use the properties of one-way functions. A proof by contradiction should only take a few lines.


Can I change an encryption key used without decrypting first

It's important to define what you want and why. For example, if the server doing the transformation does not hold the secret key of the first kind, then this is "proxy re-encryption". However, if it does hold it, then the question is why not decrypt first. From a security perspective it doesn't matter, and sometimes not from an efficiency perspective as well.

If you are using ElGamal variant, then you can do this quite easily and it's actually more efficient than decrypting and encrypting. Given key pair $pk_2=h_1$; $sk=x_1$ and $pk_2=h_2$; $sk_2=x_2$ and given $c_1=(u,v)=(g^r \cdot m, h_1^r )$ you can compute $c_2=(u, v^{x_2/x_1})$. Check out why this works yourself...


Why isn't a table used to solve the large number factoring problem?


They are generally relevant only to symmetric-key cryptography (e.g., block ciphers, hash functions, message authentication codes).  There's no deep reason why -- it's just that differential and linear cryptanalysis tend to be effective against the sort of structure that are commonly used in block ciphers, but not very effective against the sort of designs that are commonly used for public-key  crypto.


if a hash is difference-unpredictable, will it keep unpredictable given an offset?


What is stopping someone from saving encrypted info, and decoding it later?

Decoding information within a time frame is of absolute importance.

Say X is an terrorist, the information of his attack will be useful today, not years after the attack has happened. And similarly decoding your message is important today, not years later. Also there might be a possibility that when somebody has decoded your key for future use, you might have already changed it.


Does Microsoft use Dual_EC_DRBG by default?

The September 2013 supplemental ITL bulletin released by NIST has drawn attention to NIST publication SP 800-90A, Random Number Generation using Deterministic Random Number Generation; specifically the trustworthiness of the Dual Elliptic Curve Deterministic Random Bit Generator (Dual EC DRBG) algorithm.  As a result, NIST strongly discourages the use of Dual EC DRBG until concerns with it are addressed in a future revision of SP 800-90A.

The Windows CNG cryptographic infrastructure provides an implementation of DUAL_EC_DRBG applications may use. The Windows Crypto development team has reviewed supported version of Windows and determined that no features or components included in Windows specifically uses Dual EC DRBG.

Windows has a mechanism for configuring the default RNG algorithm to be used by various parts of the system. The default configurations for Windows 8.1, Windows Server 2012R2, Windows 8, Windows Server 2012, Windows 7 and Windows Server 2008R2 do not use Dual EC DRBG as the default random number generator algorithm.  The default random number generator algorithm for these versions of Windows is AES_CTR_DRBG from SP800-90a.

DRBGs rely on entropy to provide secure random number generation.  Good entropy typically depends on hardware and other factors to ensure its randomness.  Most applications rely on the platform to provide secure random numbers. I would expect that Chrome and Firefox would use the BCryptGenRandom to generate secure random numbers on Windows; however, each respective development team is more authoritative on how they generate random numbers when their browsers run on the Windows platform.

Mike Stephens
Windows Program Manager, Cryptography


No.  What this means is that they concatenate all of this data and then SHA1-hash the concatenation.  There's no xor-ing of digests or anything like that.

The reason it's described this way is because many hashing APIs allow you to specify the data in a streaming fashion: you can specify the first few bytes of the message to be hashed, then you can specify a few more bytes (which will effectively be appended to the previous parts), then some more, and so on; eventually you tell the API that you are done and please return the hash.  You can think of the API as storing all of the data you passed to it, concatenating it, and hashing it all at the end.  However, for better performance, the API doesn't actually need to store all of that data: because of the way that SHA1 works internally, it can hash the data on the fly and avoid the need to store so much.  Anyway, the wording used to describe what is to be hashed is probably an artifact that mirrors the structure of the API for many SHA1 implementations.

This helps defend against man-in-the-middle attacks.  If both endpoints have the same SHA1 hash, then they must be using exactly the same data.  If a man-in-the-middle tries to modify any of this data while it is in transit, then the two endpoints will have different inputs to SHA1, so they will end up with different SHA1 digests.  Depending upon how the rest of the protocol is constructed, that may provide an opportunity to detect the man-in-the-middle.


Security of GCM if Implemented with Stream Cipher instead of Block Cipher

In AES/GCM, every use of AES can be expressed in terms of AES-CTR:

From the initial IV (12 bytes + counter initialized at 1), a sequence of $n+16$ bytes is generated, for a source plaintext of $n$ bytes; the first $16$ bytes are the block XORed with the GHASH output to produce the authentication tag.
The GHASH key ($h$) is obtained as the encryption of an all-zero block; this is equivalent to AES-CTR encryption of an all-zero value with an IV+counter equal to zero.

In fact, it is highly possible and even sensible to implement GCM out of an exclusively CTR implementation of AES (see my GCM code for an example).

Since AES-CTR is supposed to be a strong stream cipher, indistinguishable from a random source, we can replace it with another stream cipher, and things should still be fine in terms of security (i.e. it won't be made worse). In details, this would mean the following:

The stream cipher works over a key $K$ and a 16-byte IV.
The stream cipher would be invoked over an all-zero IV to produce $h$ (16 bytes).
The stream cipher would also be invoked, with the same key, but an IV made of the nonce (12 bytes) + the value 1 (over 4 bytes) to generate $n+16$ bytes, for the XOR with the authentication tag and the data encryption itself.

With this description, we see that AES-CTR is actually a bit lousy with regards to IV management. The specific details of IV construction are meant to avoid nonce reuse; AES-CTR for a run of $k$ blocks "burns up" $k$ successive nonces. This is the reason why counter starts at $1$ for the block to be XORed with the GHASH output, and $2$ for the data itself: that way, the values cannot collide with the all-zero block for $h$. Use of a secure stream cipher in lieu of AES might possibly relax such constraints, and in fact be more secure than GCM(*).

Of course, this raises the question of why you would do that. The GHASH part of GCM is usually the problematic one when it comes to implementation, not the AES. GHASH is very fast on hardware platforms that have dedicated opcodes (x86 with AES-NI, POWER8...) but these platform also provide an AES hardware implementation that outperforms software-based stream ciphers. In practice, you would probably be better off with Poly1305, which is commonly used in combination with the stream cipher ChaCha20, as described in RFC 7539.

(*) With the usual caveat that something can be "more secure" than AES/GCM only insofar as AES/GCM is less than ideally secure, but it is currently unbroken. We still have a few academic misgivings related to the relatively short IV, in that random 96-bit IV have a not completely impossible probability of collision.


Largest number that could be factored in milli seconds

We need a little bit of clarification or state some reasonable assumptions.  For instance, 2^n can be factored very quickly for ludicrously large values of n.  I assume that's not what you're asking.  You're also probably not looking for a rigorous worst case, as that depends on the algorithms and implementations.  Perhaps time taken for non-trivial random inputs.

"This can be yours for only pennies a day*"   (*: approximately 64,000).  By milliseconds, I'm assuming you mean something in the range 1-999.

On my computer, using Pari/GP or Perl/ntheory, looking at average time, 20 digit semiprimes take about 1ms, random input about 1/3 of that.  Random input is about 10ms at 31 digits, semiprimes at 26-27 digits.  Random input is about 100ms at 51 digits, semiprimes at about 38-39 digits.  Random input hits 1000ms at ~60 digits.

Those programs are handy, but certainly not state of the art for factoring.  Among other things, they only use 1 core.  Something like yafu would probably be a better benchmark, as its SIQS is extremely fast and uses multiple cores.  Last time I checked, the QS/NFS crossover was in the 100-110 digit range, and well over 1000 milliseconds.

As for algorithm, after simple things like trial division and maybe even a tiny bit of Rho/Brent, we're probably looking at ECM or QS.  P-1 may be in there as well.  SQUFOF is very nice for 64-bit inputs, but that's sub-millisecond timing for good implementations, and it doesn't work so well for larger inputs.

This is pretty old, but back in 2009 I did some tests on various factoring code.  On page 18 of this presentation it shows the number of digits possible for factoring semiprimes in 1 second to be 55 digits with yafu.  That was a Q6600, and yafu's latest code might be faster as well.


Why does the PAKE ideal functionallity allow the keys to be the same when the passwords differ?

The paper contains text that explains why this is OK. I quote:

The main idea behind the FKE functionality is as follows: If both participating parties are not corrupted, then they receive the same uniformly-distributed session key, and the adversary learns nothing about the key except that it was generated. However, if one of the parties is corrupted, then the adversary is given the power to fully determine the session key. The rationale for this is that the aim of key exchange is to enable honest parties to generate a key that is unknown to an external adversary. If one of the participating parties is corrupted, then the adversary will learn the generated key (because it is one of the participants), and so the security requirement is meaningless. In such a case, there is nothing lost by allowing the adversary to determine the key.

However, from your question, I think I understand what you are worried about. If the adversary $P_k$ can set the value of its key with $P_i$ and with $P_j$ then it could seemingly behave like a man-in-the-middle between $P_i$ and $P_j$. However, this is not the case. Specifically, $P_i$ knows that its key with $P_k$ is $sk$, and when communicating with this key, it knows that the communication is with $P_k$ and not with $P_j$ (and vice versa). When $P_i$ wants to communicate with $P_j$, it has a different session key.
Bottom line, the reason that this doesn't matter is that the identity of the other party is given together with the key.
One more note: it may not be absolutely necessary to allow this, but there's no reason to disallow it. Disallowing it may rule out protocols that are perfectly fine. Therefore, it's better to allow it if there's no reason not to.


Attacks on one-time pad, given a property of keys

Let's first look at the concrete case;

We already know that when a key is used more than once, one-time pad becomes insecure with this two questions and nice answers on crib-dragging.

How does one attack a two-time pad (i.e. one-time pad with key reuse)?
How to attack a “many-time pad” based on what happens when an ASCII space is XORed with a letter?

But, in your case the keys are not the same, only a relation is given by

$$k_1 \oplus \ldots \oplus k_n = 1^l $$ (message length $n$ and number of keys confuse here let $l$ be the message length)

now, let $n=2$ messages $m_1$ and $m_2$ than $k_1 \oplus k_2 \oplus 1^l $

If we x-or the two ciphertexts $c_1$ and $c_2$ of $m_1$ and $m_2$, respetively;
$$ c_1 \oplus  c_2 = m_1 \oplus k_1 \oplus m_2 \oplus k_2 = m_1 \oplus m_2 \oplus 1^l$$
then;

$$c_1 \oplus  c_2 \oplus 1^l = m_1 \oplus m_2 $$ So the solution for this is nothing but the usual two-time pad.
now let we $n=3$ messages $m_1, m_2$ and $m_3$ than $k_1 \oplus k_2 \oplus k_3 \oplus 1^l $. than we will have
$$c_1 \oplus  c_2 \oplus c_3 \oplus 1^l = m_1 \oplus m_2 \oplus m_3$$

This can be also attacked but will be harder, since we have to guess two words and see that it reveals from the third message. The expected time is the square of the $n=2$ case for the initial guesses.
When $n$ becomes bigger it will require more guess and trials.

Arbitrary $f$

Here, let's look only the case $n=2$, and only ideas;

We have $c_1 = m_1 \oplus k_1$, $c_2 = m_2 \oplus k_2$, and $f(k_1, k_2) = v$

We can't apply crib-dragging here since

$$ c_1 \oplus c_2 = (m_1 \oplus m_2) \oplus (k_1 \oplus k_2)$$ guessing $m_1$ will not give any information. An attack can be performed by guessing two words and verifying that $k_1$ and $k_2$ satisfies two relations;

$$k_1 \oplus k_2 = m_1 \oplus m_2 \text{ and } f(k_1, k_2) = v$$


ANSI X9.31 standards for generating random numbers

If you're asking why the X9.31 rng was designed the way it was, rather than some other way, I'm not certain if anyone other than the original authors could say.  The core design dates back to at least 1985 (it was included in X9.17), and it originally used DES (and was later upgraded to use 3DES).  I suspect that the original authors would not have been confident in using DES in counter mode.

As for the DT format, well, the requirement in X9.31 is that the value is distinct everytime you generate a block.  It's there to make sure that the RNG doesn't fall into a short cycle, and so it wouldn't be horrible if DT changed only occasionally (e.g. if you generated 256 values with the same DT, the probability that the cipher runs into a cycle during those 256 values is about $2^{-56}$).  A secondary reason is to feed a slight amount of additional entropy into the RNG -- it doesn't do that all that well, though.  As long as you abide by that, any format works.  In your case, it's easy enough to abide by both the spirit and the letter of the law; formulate a DT where the top 32 bits are the Timestamp you get from the system, and the lower 32 bits is just a counter which is incremented everytime you generate a block.  That way, the DT value changes everytime (because the lower 32 bits always change), and you feed the slight amount of entropy from the current data/time.

As for OpenSSL, well, it appears to be an implementation of the X9.31 (using 2-key 3DES; that is what X9.31 originally asked for, however the NIST document you gave now specifies 3-key 3DES).

Also, if you need a secure RNG, I would suggest you look at these RNGs, especially the CTR_DRBG (whose base idea is just an block cipher in counter mode just like you suggested).


Is OAEP needed when encrypting a session (random) key using RSA?

when encrypting a session key which is used to encrypt bulk data using a block cipher for example, is padding with OAEP really needed ?

No if the session key is nearly as wide as the RSA modulus, or is padded with random bits up to that size (save for one bit or few high order bits). Absent other issues, we are safe if the actual session key keeps bits from the result of RSA decryption among those that have been chosen randomly, or is obtained by another key derivation step. That's the principle in RSA-KEM.

But yes, RSAES-OAEP is useful if the session key is directly the payload, and is much smaller than the RSA modulus (which is typical for a session key). OAEP gives a security reduction to the RSA problem under the random oracle model, when direct encryption of a short key with textbook RSA (as $C=K^e\bmod N$ ) is known to be insecure in at least the following two cases.

If the public exponent $e$ is small (less than about $\displaystyle\frac{\log N}{\log K}$ bits), then decryption reduces to computing the non-modular $e^\text{th}$ root of $C$, yielding $K$. This question asks for a bound for $\log K$ allowing attack, which it is slightly larger than $\displaystyle\frac{\log N}e$.
If the key $K$ is significantly less that twice as wide as the desired security level, then there's a meet-in-the-middle attack working for the sizable fraction of $K$ that (partially) factor as $K=K_1\cdot K_2$ with $K_1<K_2$ and $K_2$ small enough to be enumerated, requiring $O(K_2)$ time and $O(K_1)$ memory.
That would be a plausible attack for 128-bit $K$ and 4096-bit RSA with $e=2^{16}+1$.

  What benefits does OAEP provide compared to simple padding with random bits up to size $n-1$ where $n$ is the size of (the) RSA (public modulus) ?

None that I see beyond

availability of some secure implementations,
recognition (including explicit by some security recommendation),
detection of accidental cryptogram corruption or using unmatched public/private keys.

Beware that implementation of decryption using "simple padding with random bits" is far from foolproof; nothing manipulating secret or private key is. In particular, testing the high-order constant bit(s) leads to disaster by padding oracle attack. Fault attacks may apply (e.g. forcing the session key to be zero with targeted and timed laser pulses). Side channels may be problematic.


Textbook RSA:

Choose two large primes $p$ and $q$.
Let $n=p\cdot q$. Choose $e$ such that $gcd(e,\varphi(n))=1$ (where $\varphi(n)=(p-1)\cdot (q-1)$). Find $d$ such that $e\cdot d\equiv 1\bmod{\varphi(n)}$. In other words, $d$ is the modular inverse of $e$, ($d\equiv e^{-1}\bmod{\varphi(n)}$).

$(e, n)$ is the public key, $(d, n)$ the private one.

To encrypt a message $m$, compute $c\equiv m^e\mod n$.
To decrypt a ciphertext $c$, compute $m \equiv c^d\mod n$.

Signing and verifying messages is also defined (omitted for brevity).

Some (Undesirable) Properties of Textbook RSA:

It is malleable. I.e., if you give me a ciphertext $c$ which encrypts $m$, I can compute $c'\equiv c\cdot 2^e\mod n$. When the owner of the private key decrypts $c'$, she will get $2m\mod n$. In other words, I can make predictable changes to ciphertexts.
It is deterministic, and thus not semantically secure. I.e., I can distinguish between the encryptions of $0$ and $1$ (simply by encrypting both values myself and comparing the ciphertexts).

Differences with Deployed RSA:

Padding
Chinese Remainder Theorem is sometimes used in deployed systems for more efficient decryption.
$e$ is often statically set to $65537 = 2^{16} + 1$ for encryption speed (since there are only two set bits in that number).
Side-channel attack mitigations can be put in place for deployed systems too.

In no way is my list comprehensive, but hopefully this helps.


Can wiping a disk writing zeros on an encrypted device be a weak point?

The output of an encrypted stream of zeros is absolutely indistinguishable from random data.

What you do is not write zeros to the block device for the drive, but for the encrypted mapping. That is, instead of writing zeros to /dev/sdx, you write to /dev/mapper/sdx_crypt. This results in the contents on the actual drive being completely randomized. Even though an attacker may know that zeros were encrypted, they would be no closer to finding the key than before. If they were, it would mean the underlying cipher is vulnerable to a known plaintext attack, and none of the supported LUKS ciphers (AES, Twofish, Serpent, etc.) are. In fact, any symmetric cipher that was badly vulnerable to a known plaintext attack would be considered fatally broken, and would be either revised or discarded.

To prove a point, you can see that many high-quality cryptographic random number generators work by encrypting a counter with a block cipher. An attacker knows exactly what was encrypted by the block cipher. They know that the nth block of output is an encryption of integer n itself, yet it doesn't make it possible for them to predict any of the output or retrieve the key. Ciphers are stronger than you think.


Variants of universal composability in security proofs

Do not take my word for it, but as far as I remember: a GUC-secure protocol is secure in the UC framework; the converse is not true since a protocol secure in the UC framework might not allow for a global setup. The JUC framework is mainly aimed toward having, in the end, a proof in the standard UC framework: a protocol secure in the JUC framework can be composed in a certain, restricted way with UC-secure protocols, and lead to a UC-secure protocol. The advantage is that JUC-secure protocols can be built more efficiently, so when this restricted composition suffices, we are fine.


What is the largest parameter broken for NTRU?

1996 - NTRU patent,

1998 - NTRU article

Lattice Attacks

1996 - Lattice attack on the Rump Session of Crypto'96

1997 - Don Coppersmith and Adi Shamir. Lattice attacks on NTRU. In EUROCRYPT, pages 52–61, 1997. No need to find the exact secret key to be able to decrypt

2008 - Nicolas Gama and Phong Q. Nguyen. Predicting lattice reduction. In Proceedings of the theory and applications of cryptographic techniques 27th annual international conference on Advances in cryptology, EUROCRYPT’08,
It has been shown in that the ability to locate a unique shortest vector
in a lattice depends on the root Hermite factor of the lattice,

2011 -  Yuanmi Chen and Phong Q Nguyen. BKZ 2.0: Better lattice security estimates. In ASIACRYPT 2011, pages 1–20. Springer, 2011.
Fastest NTRU-107. 214-dimensional lattices within $2^{42.62}$ clock cycles. Dimension of the lattice is the double of $N$

2016 - Shi Bai, Thijs Laarhoven, and Damien Stehlé. Tuple lattice sieving. IACR Cryptology ePrint Archive, 2016:713, 2016.
Best lattice attack with  $2^{0.292n}$ cost.

The below are the cost estimates from the NTRU PQC team.

N
m
b
Known Classical
Known Quantum
Best Plausible
Space Requirement

443
390
321
93
85
66
>$2^{66}$

743
613
603
176
159
125
> $2^{125}$

1024
1870
747
218
198
155
> $2^{155}$

Search attack
Searching the keyspace ${N \choose df,df}/N$  NTRU-743, we have $2^{1158}$ candidates. Impossible!
Hybrid attack
the hybrid attack is a hybrid of a lattice attack and a meet-in-the-middle search attack.

2007 - Nick Howgrave-Graham. A hybrid lattice-reduction and meet-in-the-middle attack
against NTRU. In CRYPTO, pages 150–169, 2007.

BKZ with classical enumeration, hybrid attack vs. uSVP

N
hybrid attack Cost
uSVP

443
>128
>189

743
>267
>443

1024
>811
> 590

BKZ with quantum sieving, hybrid attack vs. uSVP

N
hybrid attack Cost
uSVP

443
>84
>85

743
>163
>159

1024
>289
> 198


does TLS 1.3 use ECDSA-Sig-Value encoded signatures for Ed25519 / Ed448?

EdDSA is a family of signature schemes defined precisely on strings of bytes, including its extension to more curves like edwards448.  This generally avoids failures of security theorems in the real world arising from a mismatch between powers of an adversary on a system of strings of bytes and powers of an adversary on a system of idealized mathematical objects.  The choice was motivated by failures of exactly that type in HMQV observed by Menezes.

Any software implementing Ed25519 will generally be byte-for-byte compatible.  The TLS stack need not know anything about its mathematical structure.  It is enough to know that a secret signing key has a standard 32-byte representation, that a public verification key has a standard 32-byte representation, that a signature has a standard 64-byte representation, and that the definition of Ed25519 entails the precise relations between these byte strings.  In contrast, ECDSA leaves needlessly complicated details to the caller to sort out—or to botch with additional ASN.1 attack surface and logic to interpret the mathematical structure in ECDSA.

In this specific case, although the parts of a signature may be named by the letters ‘r’ and ‘s’ in both ECDSA and EdDSA, and although they may be represented by integers, they actually represent different types of object with different rôles in the signature verification equation.  For an elliptic curve $E/k$ over the field $k = \mathbb Z/q\mathbb Z$ for some prime power $q$, with $k$-rational group $E(k)$ of order $h\ell$:

An ECDSA signature is some representation, with whose details the caller must be concerned, a field element $r \in \mathbb Z/q\mathbb Z$ and a scalar $s \in \mathbb Z/\ell\mathbb Z$.  It is valid on a message $m$ under a public key that is a curve point $A \in E(k)$ if and only if $$r \equiv x([H(m)\cdot s^{-1}]B + [r s^{-1}]A) \pmod p,$$ where $B$ is the standard base point.
An EdDSA signature is a standard byte string representing of a curve point $R \in E(k)$ and a scalar $s \in \mathbb Z/hl\mathbb Z$.  It is valid on a message $m$ under a public key that is the standard encoding of a curve point $A \in E(k)$ if $$[8 s]B = [8]R + [8 H(R\mathbin\|A\mathbin\|m)] A,$$ where $B$ is the standard base point.


DES anti-fixed points for semi-weak keys

K = 01FE01FE01FE01FE   P = 771DF32699DF2F2A   C = 88E20CD96620D0D5
K = 01FE01FE01FE01FE   P = 668493768A3D5786   C = 997B6C8975C2A879
K = 01FE01FE01FE01FE   P = 6F52785BC50C62BE   C = 90AD87A43AF39D41
K = 01FE01FE01FE01FE   P = DFFE8B7E72E5CFED   C = 200174818D1A3012

will do. I found that by a randomized search after about $2^{34}$ DES operations, which tends to confirm the order of magnitude of the $2^{32}$ stated in the question.

Explanation:

For $i\in[1,16]$, note $L_{i-1}$ and $R_{i-1}$ the 32-bit contents of the $L$ and $R$ registers before encryption round $i$; note $R_{16}$ and $L_{16}$ the output of the last round after a swap (even if that swap is undone by an extra final swap, or equivalently is not done); note $K_i$ the 48-bit sub-key for round $i$. We have $L_i=R_{i-1}$ and $R_i=L_{i-1}\oplus F(E(R_{i-1})\oplus K_i)$, where $E$ is the expansion, and $F$ represents the S-boxes and permutation $P$ combined.

For the four keys $K$ 01FE01FE01FE01FE, FE01FE01FE01FE01, 1FE01FE00EF10EF1, E01FE01FF10EF10E, it holds that $K_i=\overline{K_{17-i}}$.

If it happens that $L_{8}=\overline{R_{8}}$, using that $E(\overline X)\oplus \overline{K_i}=\overline{E(X)}\oplus \overline{K_i}=E(X)\oplus K_i$, it follows that the input of function $F$ (S-boxes and permutation $P$) at rounds 8 and 9 are the same, thus their output are the same. By induction we get that the input of $F$ at round $i$ and $17-i$ are the same, and $L_i=\overline{R_{16-i}}$. Thus $L_{16}=\overline{R_0}$ and $R_{16}=\overline{L_0}$, thus $E_K(P)=\overline P$ for the $P$ corresponding to $L_0$ and $R_0$.

We could efficiently construct $2^{32}$ plaintexts $P$ with that property by performing the last 8 rounds of decryption and final permutation of DES, starting from the $2^{32}$ values of $L_{8}=\overline{R_{8}}$.

Unsettled: does there exist a DES key $K$ with more than $2^{32}$ anti-fixed points?


Finding the private key in Diffie Hellman

That the parties have agreed on a DH secret means the following:
$$g^4=(g^K)^Y=g^{KY}\pmod P$$
Now we can just look at the exponents:
$$4=KY\pmod{P-1}$$
Which may or may not have the unique solution for $Y$:
$$Y=4\cdot K^{-1}\pmod{P-1}$$

That is if $\gcd(K,P-1)>1$ and we know that $K^{-1}$ must exist, then it will have multiple possible values. The precise values depend on $P$ and $K$.


How does the Rijndael 192/256 bits block size mix column works?

The original Rijndael submission to the AES competition (which includes details on how to handle block sizes of 192 and 256 bits) can be found here.  The mix column operation itself is described in section 4.2.3, and that section explains it pretty well.

Since I'm not supposed to have link-only answers, I'll try to explain it myself.
The state in Rijndael is represented by a $4 \times n$ matrix of bytes (where $n=4$ for 128 bit blocks, the AES case, and $n=6$ for 192 bit blocks and $n=8$ for 256 bit blocks).  When you perform the Mix Column step, you take each column in the matrix, and multiply it by the fixed polynomial $03x^3 + x^2 + x + 02$   modulo $x^4 + 1$.  This operation is precisely the same as in AES, except that if you have a larger block size, you have more columns; you still apply this multiplication only once for each column in the matrix.


What is the meaning of $1$ in provable security?

If we write
$$\Pr[\mathcal A(g,g^a,g^b,g^{ab})=1]-\Pr[\mathcal A(g,g^a,g^b,g^c)=1]\le\operatorname{negl}(n)$$
without an absolute value, meaning that the (distinguisher) algorithm $\mathcal A$ is not good enough to breach security, it is implicit that $\mathcal A$ outputs $1$ more likely when it has recognized something special. That something special is the condition that should be near impossible to recognize for security to hold. In the context, that special thing ideally is: for input $(g,g^a,g^b,g^c)$, the condition $g^c=g^{ab}$ holds. But an algorithm that does not exactly recognize that condition is still a valid distinguisher (breaking security) if it manages to make the overall condition false.

It is often written
$$\big|\,\Pr[\mathcal A(g,g^a,g^b,g^{ab})=1]-\Pr[\mathcal A(g,g^a,g^b,g^c)=1]\,\big|\le\operatorname{negl}(n)$$
and, thanks to the absolute value, it becomes immaterial if the special condition tends to make $\mathcal A$ output of $1$ or $0$, because
$$\big|\,(1-p)-(1-p')\,\big|\ =\ \big|\,p-p'\,\big|$$
Now, the only thing that matters is that the output of $\mathcal A$ has a significantly different mean over the inputs of the form $(g,g^a,g^b,g^{ab})$ than it has over the inputs of the form $(g,g^a,g^b,g^{ab})$.


Use Initializaiton Vector as Additional Authenticated Data

You don't need to put the IV in the AAD (Additional Authenticated Data) as already indicated in the comments.

The GCM proposal as adopted by NIST (PDF) clearly specifies this in paragraph 2.1 Inputs and Outputs:

  The IV is authenticated, and it is not necessary to include it in the AAD field.

The NIST document SP 800-38d (PDF) does not explicitly specify it, it does however contain some hints to this effect, for instance in Appendix B:

  The creation of an authentication tag by the authenticated encryption function provides the mechanism whereby assurance of the authenticity of the plaintext and AAD (and IV) can be obtained upon the execution of the authenticated decryption function.

Finally, to make this a bit more general, RFC 5116 : An Interface and Algorithms for Authenticated Encryption, 2.1: Authenticated Encryption specifies the following:

  The nonce is authenticated internally to the algorithm, and it is not
     necessary to include it in the AD input.  The nonce MAY be included
     in P or A if it is convenient to the application.

So it is acceptable to store the IV in the AAD, but I don't see any reason to recommend it.

If I'd see the IV included in the AAD during a review I'd probably see it as an indication that the designer didn't know what he/she was doing.


On keyword for generators of composite moduli

The link says $n$ has a primitive root if and only if $n$ is of certain form, either $n = ap^k$ where $a \in \{1, 2\}$, $p$ is an odd prime or $n \in \{2, 4\}$

This is true.

  In particular $n = pq$ or $n = prq$ where $n, q, r$ are not all equal primes are disallowed.

Other than the minor nit that $n=pq$ where $p=2$, $q$ is an odd prime does have primitive roots, the obvious question is "what do you mean is disallowed?"

A primitive root is a value $g$ where $g^k \bmod n$ can take on all values in $Z^*_n$; what the statement says is that such a $g$ will exist if $n$ is of the form listed, and no such $g$ will exist if it's not.

  Yet in here discrete logarithms modulo such $n=pq$ or $n=pqr$ forms are defined and used.

Well, yes, the problem "given $g, h$, does there exist a $k$ such that $g^k \equiv h \pmod n$ (and if it does exist, what is its value)" is well-formed, even if $n$ is not of the listed form.  Now, as there isn't a primitive root, there's no value $g$ for which such a $k$ will exist for every $h$ relatively prime to $n$; however that doesn't make this an invalid question.

  Since generator $g$ cannot be primitive root what is the keyword for $g$ for these forms?

Well, I can't think of any better term than "generator".  Any value $g$ relatively prime to $n$ will generate some subgroup; the only distinction between "primitive roots" and "everything else" is that primitive roots generate the entire group.  I suppose you might insist on a value $g$ which generates as large of a subgroup as possible (which would be, for the forms you listed, of size $\text{lcm}(p-1,q-1)$ or $\text{lcm}(p-1,q-1,r-1)$), however I haven't heard of specific terminology given to elements that generate subgroups of that size.


Why is does the protocol of Ding et al. produce biased bits and does it relate to passive security?

The usual definition of (passive) security for key exchange requires the agreed-upon key to be indistinguishable from uniformly random. That's not the case for DXL14 because the bits of the key are biased, not uniform. You can check that yourself if you implement the DXL 14 algorithm in (for example) SageMath. It shows that bits are biased and not uniform.

Now, you may wonder: is it because it uses Polynomial instead of Vector of polynomials, because of limited domain of $\mathit{Sig}$  function (i.e. $E= {-\lfloor {\frac {q}{4}}\rfloor ,...,\lfloor {\frac {q}{4}}\rceil \}}$), or if there’s some other reason?

Well, it's simply because any deterministic map from $\mathbb{Z}_q$ to 0,1 must be biased when $q$ is odd.


I don't believe your protocol meets the standard definition of Zero Knowledge Proof, as a cheating verifier can learn more information about the secret than allowed.  In particular, suppose we have a cheating verifier (server) that has a list of one million potential passwords.  Then, he can run your protocol with a client that knows the password, run the KDF with all one million passwords, and see which one allows him to decrypt the message.  This allows the cheating verifier to check his entire dictionary of passwords at once.

If you are looking for a password verification protocol that avoids such weaknesses, I suggest you look at either the SRP protocol or the EKE protocol; both were designed specifically to avoid such weaknesses.

Now, as for your question about encrypting known plaintext, well, that's not actually a concern.  Strong encryption method (say, AES with a good mode) are designed to be strong against known (or even chosen) plaintexts.  Now, in your case, since you're just verifying knowledge of the shared key, you don't even need to encrypt anything; generating an HMAC of some standard data would be sufficient (or, at least, it would be if your protocol didn't have the above problem).


Which hash function is used for signatures ssh-rsa and ssh-dss?

In section 6 of RFC 4253 it says on page 15:

  The "ssh-rsa" key format has the following specific encoding:

  string    "ssh-rsa"
  mpint     e
  mpint     n

  Here the 'e' and 'n' parameters form the signature key blob.

  Signing and verifying using this key format is performed according
  to    the RSASSA-PKCS1-v1_5 scheme in [RFC3447] using the SHA-1 hash.

So the answer is "SHA-1" as well.


Theoretically, since the domain of SHA-256 contains $2^{2^{64}-1}$ different messages and the value set only contains $2^{256}$ different message digests, there must exist at least one possible output that has more than one possible pre-image.

Another important point is that SHA-256 is a deterministic function. This means that if you hash the same message twice, you will get the same digest both times. Hence, "almost unique" should be understood as meaning that SHA-256 will likely produce a different hash for each different input message. This might be false in an abstract mathematical sense, but it is probably true in a more practical sense:

In practice, uniqueness is not determined by the abstract theoretical non-existence of collisions, but by the practical non-existence of collisions. In order to find a collision in SHA-256, you would probably have to execute the algorithm some $2^{128}$ times. It is unlikely that this will happen anytime soon, even if you count the total number of times SHA-256 will ever be executed by anyone in the entire universe combined.

Does a message "exist" if it belongs to a well defined abstract set, or does it "exist" because it has actually been produced and has been represented by someone or something in the physical reality?


Given your ideal setup, I don't think you need anything else than plaintext authentication.

The only thing could be if the server at the end of the TLS link is not the one managing the authentication (in which case you do not necessarily want to reveal to it your password).


How to find $r$ for El-Gamal signature with known private key


How to construct a "toy" version of Gimli permutation for three (instead of twelve) 32-bit words?

According to the spec, the Gimli state consists of four columns of three rows of 32-bit words, for a total of 4 × 3 × 32 = 4 × 96 = 384 bits.  Each Gimli round consist of:

a non-linear SP-box applied to each 96-bit column individually,
on every second round, a linear mixing step that just swaps the first words of pairs of columns, and
on every fourth round, a constant addition step that XORs the first word of the first column with a 32-bit round constant.

Probably the simplest way to reduce the Gimli permutation to 96 bits would therefore be to simply drop all but the first 96-bit column and omit the linear mixing step entirely, as it's the only part of Gimli that actually mixes the columns together.  This will naturally give a 96-bit permutation that should resemble the full Gimli permutation in most respects, other than having a smaller state size.


Secure degree reduction for Shamir's secret sharing

The process is pretty simple. As you say, each party multiplies their two shares. They then use Shamir secret sharing to share the resulting value with the other parties. Once they have received a "subshare" from each other party, each party simply runs Lagrangian interpolation on the subshares they received (plus their own subshare). The result is a share of the product of the two inputs with the proper degree for the sharing polynomial.

I'll illustrate it with a simple example. Say we have shared two secrets ($5$ and $2$) with three parties as follows. Math done in $\mathbb{Z}_{11}$.

$\sigma_1(x) = 5 + 8x$
$\sigma_2(x) = 2 + 9x$

So the shares of 5 that the parties hold are 2, 10, 7.
The shares of 2 are 0, 9, 7.

So, each party multiplies their shares. The new shares are 0, 2, 5.

They each share these using new polynomials

$\sigma_3(x) = 0 + 3x$ for party 1
$\sigma_4(x) = 2 + 6x$ for party 2
$\sigma_5(x) = 5 + 2x$ for party 3

Which generate subshares: (3, 6, 9); (8, 3, 9); (7, 9, 0)

Thus, after distributing the shares, party 1 holds (3,8,7); party 2 holds (6,3,9); and party 3 holds (9,9,0).

After interpolation, the shares held by the parties are 3, 7, 0. Interpolating these to get the constant term give us 10 as expected.


How does DSA provide non-repudiation in proving a document was properly displayed (not altered or displayed incorrectly)?

I'm trying to get my head around how the crypto solves this problem.

It doesn't. You need to trust the platform you use to do the signing.

For instance, my bank has replaced the "signature" generation device that I previously used with one that displays the actual transaction, so I don't have to trust the information on the computer screen that much.


Why is Triple DES not vulnerable to meet in the middle attacks?

The computational complexity of the attack you describe is $2^{112}$, since that's how much work it takes to build the look-up table.

In fact, for standard 2-key 3DES like you describe, an attacker capable of building such a look-up table could just as well store $C = E_{K_1}( D_{K_2}( E_{K_1}( P )))$ instead of just $D_{K_2}( E_{K_1}( P ))$ in the table, allowing them to skip the second half of the meet-in-the-middle attack and just directly look up $(K_1, K_2)$ in the table, given a ciphertext block matching the plaintext $P$.

However, the attack your describe (and variants of it) is precisely the reason why three layers of DES encryption cannot provide more than 112-bit security, even though, naïvely, using 3-key 3DES with $C = E_{K_3}( D_{K_2}( E_{K_1}( P )))$ would seem to offer 168 bits of key-space.


The way $c_1$ and $c_2$ have been obtained, algebra has shown that the quantity $z={c_1}^{e_2}\,5^{e_1\,e_2}-{c_2}^{e_1}\,2^{e_1\,e_2}$ is such that $z\equiv q^{e_1\,e_2}\pmod n$, where $n$ is an RSA modulus with $q$ one of the prime factors of $n$, $e_1$ and $e_2$ are RSA exponents valid for the modulus $n$.

From $n=p\,q$, we know that $q$ divides $n$.

From $z\equiv q^{e_1\,e_2}\pmod n$, and since $q$ divides $n$, we know that $z\equiv q^{e_1\,e_2}\pmod q$. Since neither $e_1$ nor $e_2$ are zero, it holds $q^{e_1\,e_2}\equiv0\pmod q$. Therefore, $z\equiv0\pmod q$, that is $q$ divides $z$.

Hence, $q$ is a common divisor of $n$ and $z$. With $n=p\,q$ with $p$ prime, it follows that one of the following holds:

$z=0$
$\gcd(z,n)$ is $q$
$\gcd(z,n)$ is $n$.

The way $z$ was constructed gives no particular reason to believe that $p$ divides $z$, and that's highly unlikely for a random integer. It follows that $\gcd(z,n)=q$ is the only likely possibility in the above three.

The quantity ${c_1}^{e_2}\,5^{e_1\,e_2}-{c_2}^{e_1}\,2^{e_1\,e_2}\bmod n$ can efficiently be computed from givens, and that allows to compute $\gcd(z,n)$ (since the first step of that can be to reduce $z$ modulo $n$), and thus allows to compute $q$.


Understanding Baby-Step Giant-Step Algorithm and discrete logarithm

In the algorithm, $p$ is the order of group, $x$ is solution. We rewrite $x = i * m + k $, but why do we make $m =\lfloor\sqrt{p}\rfloor$, rather than something else like $\lfloor {p/2}\rfloor$?

The time taken by Big Step-Little Step is $O( m + p/m )$ (the $O(m)$ term comes from the time taken iterating through the various $k$ values, the $O(p/m)$ term comes from the time taken iterating through the various $i$ values.

It should be easy to see that that time is minimized if $m \approx \sqrt{p}$

  (a) The time complexity is $O(\sqrt{p})$. If we make sufficient large $p$, then why is it difficult for compute the discrete logarithm computation in group $G$ of such order $p$?

If $p$ is quite large, then $\sqrt{p}$ is also large (even if it isn't as large as $p$); for example, if we want $\sqrt{p} \ge 2^{128}$ so that the number of steps that Big Step-Little Step takes is infeasibly large, we just take $p \ge 2^{256}$.

Just one note: if we're working in the group $\mathbb{Z}^*_p$, then there are other attacks against the Discrete Log problem other than the generic Big Step-Little Step (and Rho) algorithms; hence we generally need a much larger $p$

  (b) It is said that the discrete logarithm computation is hard in group of prime order, particularly in subgroup (order $q$) of group of strong prime order (like order $p = 2*q + 1$, $q$ and $p$ is prime); why is that?

If we are working in the group $\mathbb{Z}^*_p$ (that is, the multiplicative group modulo $p$), well, that group has a size $p-1$; any prime subgroup will have a size $q$ which is a divisor of $p-1$.  One way (but not the only way) to make sure that there is a good $q$ is to make $p$ a "safe prime", that is, a prime such that $q = (p-1)/2$ is also prime.

On the other hand, that applies only to the group $\mathbb{Z}^*_p$; if you go to (say) Elliptic Curve groups, there is no corresponding reason to prefer safe primes (either for the characteristic or the group size).


If you look at $k' = \operatorname{HMAC}_k(m)$ as a key derivation function then you'd expect that $\operatorname{HMAC}_{k'}(mm')$ is secure, even if $m$ is also used to derive $k'$. So from a purely functional point of view then yes, this should be secure.

Also from a functional view I would wonder why there is a repetition of $m$, because as it is used to derive key $k'$ it is already included in the calculation of the MAC value, and repeating it is therefore moot; the repetition of $m$ doesn't do anything for security. You could just use $m$ for the KDF alone, so then the outer HMAC is just $\operatorname{HMAC}_{k'}(m')$

Finally, the presumption is of course that $k$ has enough bits to be used as a HMAC key; generally the same size key as the hash output is recommended.

I don't see any reason why $f_k(mm')=\operatorname{HMAC}_k(\operatorname{enc}(m,m'))$ would not work, where $\operatorname{enc}$ is a canonical encoding function. This is a more efficient MAC if $m$ is large.


Are zero knowledge proofs alternative private key encryption?

I'm not sure about what you mean for "more safe". A probable link between these notions exists when we consider a context/application: suppose we need a secure identification scheme; the adversary is listening to the channel between the identifier and the identity-server. By considering this context, we can say that an identification scheme based on a zero-knowledge proof withstands adversary attacks: eavesdrop, man-in-the-middle, replay, etc.
In this given context, an identification scheme based on private keys will fail: a secure channel is always a prerequisite to exchange private keys. Even if the private key is unconditionally unbreakable for any computational power: the adversary can tap it if no private channel exists.


How to find an element of high-order in an RSA group?

As for the question "how difficult would it be to solve a random instance of a discrete log problem modulo an RSA modulus", well, it turns out that we can give a fairly solid answer; which is essentially "about as difficult as factoring the modulus".

Here's is a demonstration that the discrete log problem is not drastically easier than factoring the modulus": if you have a procedure that solves a random instance of a DLOG problem in a composite modulus with nontrivial probability, then you have a procedure that factors that composite modulus with nontrivial probability".

This is a well-known observation; one way to arrive at that is "if you can compute DLOGs, you can compute (a multiple of) the order of a random element, and if you can do that, you can factor".

To compute this order using an Oracle that can compute random logs, you take your random element $r$, select a random exponent $k>1$ ($k$ needs to be relatively prime to $(p-1)(q-1)$, making it a large random prime works), and then query your DLOG oracle for discrete log $(r^k)^m = r$; once you know $m$, you also know that $r^{km-1} = 1$; that is, the order of $r$ is a divisor of $km-1$.

Once you have that multiple of an order $x = km-1$, you can then factor $n=pq$ by considering the odd value $y = x/2^j$, and then for random values of $s$ ($r$ works well for an initial guess), consider the sequence $(s^y, s^{2y}, s^{4y}, ..., s^{x})$.  If we see a 1 in the sequence proceeded by a value $z$ other than 1 or $n-1$, then we can factor; the factors are $gcd(n, z-1)$ and $gcd(n, z+1)$.  And, if $r$ was chosen randomly, then with high probability this procedure will find a factorization after a modest number of random $s$ values.

As for the demonstration that the discrete log problem is unlikely to be drastically harder than factoring the modulus, well, that's just the observation that the DLOG problem can be solved by factoring the modulus, and then solving the DLOG problem in the smaller groups modulo $p$ and $q$.  As far as we know, solving the DLOG problem in those smaller groups is considerably easier than factoring, hence the factorization is the main effort.

What does this all mean?  Well, it implies that it's actually safe to pick a random generator; if there is a nontrivial probability that the generator is weak, then there's a nontrivial probability that RSA is weak as well.

Now, does this mean that the extra effort that antosecret suggested is not worth while?  Well, that's actually a matter of opinion; is it better to do a simpler method (with a provably tiny chance of failing); or is it better to do a more complex method (that avoids that specific failure mode)?  Personally, I don't care for unnecessary complexity; you would need to make up your own mind.


The MAC key is not pre-owned by someone but generated in the offline phase. Each party $P_i$ chooses a random value $\Delta_i$ and the sum $\Delta = \sum \Delta_i$ is the MAC key. To ensure $\Delta_i$ is consistently used in all shares, ciphertexts of $\Delta_i$ are exchanged and zero-knowledge proofs are used to prove they are correct.

See for example the protocol in Fig 4 in the Overdrive paper.


Sure, pick any coding language of you choice and iterate over the list of links connecting to the website. You will receive the website as some kind of object. If you know what the error page looks like, just check the object contains that error page (for example check for some string).

Also, just you could try one of the tools on this website:
http://www.softwaretestinghelp.com/tools/30-top-website-link-verification-testing-tools/


Simple Electromagnetic Analysis vs symmetric cryptography

SEMA is effective against a naive implementation (e.g. using binary square and multiply) of raising to a secret value in some group. Raising to a secret value in some group is used in common asymmetric cryptography techniques, including based on hardness of integer factorization (RSA) or the discrete logarithm (DSA, ECDSA..). That's why SEMA happens to be effective against naive implementations of common asymmetric cryptography.

It would be wrong to say that only asymmetric algorithms are vulnerable to SEMA. For example, the Pohlig-Hellman exponentiation cipher is a symmetric encryption algorithm where encryption goes $x\mapsto x^k\bmod p$ for public prime $p$ with $(p-1)/2$ prime, and $k$ a secret exponent. A naive implementation would be vulnerable to SEMA just like a naive implementation of RSA is. And it is all too frequent that a very naive implementation of DES is vulnerable to SPA/SEMA.

It would also be wrong to say that all asymmetric algorithms are vulnerable to SEMA. Careful implementation of raising to a secret value can be made secure (using the Montgomery ladder or other techniques, including blinding). And some asymmetric algorithms (e.g. Lamport signature) do not raise to a secret value, and can be made immune to SEMA with careful coding and control of the underlying hardware.


Given a 128-trit state space, is a 3-symbol block cellular automaton secure against preimage attacks?

This is a not an answer, as I do not touch preimage resistance; it is comments (now removed) made into something hopefully correct, including a description per cryptographic conventions.

The proposed code implements a minimalist hash function with an internal state st of 128 trits, parameterizable message and output size (inLen 16 bits and outLen 256 bits in the illustration). At the core is a simple state transformation, iterated for 32 rounds per input and output bit, potentially changing each state trit.

At each of such round, 64 times, two state trits are selected per a simple schedule (giving potentially full diffusion after 2 rounds), and replaced according to the following transformation (an alternate expression of constant table tt and st[x] = tt[a*3+b]; st[y] = tt[b*3+a]; ):

input   output
 0 0     1 1
 0 1     2 0
 0 2     0 1
 1 0     0 2
 1 1     0 0
 1 2     1 2
 2 0     1 0
 2 1     2 1
 2 2     2 2

This transformation is reversible, therefore the 64 transformations in a round for (i=j%2; i<128; i+=2){..} are entropy-preserving.

Each input bit is injected by replacing a trit at each round, by st[0] = bits[k];. Thus each round processing an input bit looses some amount of state entropy, but not nearly as much as if the above transformation was not reversible.

The output is formed (still with 32 rounds per bit, and no input injected) by a formula combining 4 trits. Under the natural assumption that the state is about unbiased, the output is noticeably biased: a bit is set with odds $40/81<49.4\%$. That would be fixable by mixing much more trits to produce the output. Note: because there is no entropy loss during output production, it is likely that with 256 output bits, almost all the state entropy after input processing makes it to the output, which is good.

This hash can be viewed as a traditional iterated hash function à la Merkle-Damgård or sponge, with 1 bit per message block (compensating the less than complete diffusion per round), no length-strengthening (replaced by iterations in the output production, which also gives the variable-size output), and the unusual characteristic of having sizable state entropy loss per 1-bit message block processed. The later is slightly frightening compared to using an entropy-preserving message injection like st[0] = (st[0]+bits[k])%3;, but I do not immediately see that it opens to a devastating attack (nor have proof that this entropy loss is not in fact a strength); studying this seems interesting in its own regard.


The meet-in-the-middle attack on ciphers like $C=E^2_K(P)=E_{K1}(E_{K2}(P))$ works as follows.

Let's assume you're given a known-plaintext pair $(P_1,C_1)$ and a known-plaintext pair $(P_2,C_2)$
You now build a list (by brute-force) containing the pairs $(I,K1)$ for every possible value of $K1$ ($2^{56}$ for DES) with $I=E_{K1}(P_1)$.
Constructing this list takes you $2^n$ blocks of storage with $n$ being the keysize.
You now simply call the decryption function $D_{K2}(C)$ until you obtain a value of $I$ you already stored in your table. If you find this one, which takes you at most $2^n$ operations, you simply counter-check with your second pair, using the relation: $C_2=E_{K1}(E_{K2}(P_2))$. If this holds, you can be pretty sure to have found the correct key. As you have to perform $2^n$ operations to obtain the table and $2^n$ operations to find the correct key you need $2^n+2^n=2*2^n=2^{n+1}$ operations and $2^n$ storage.

Let's see, how can I use that on 3DES (3-key)?
For the meet-in-the-middle attack to work, it is not required for the $E_K()$ to be the same. So you simply define the second one to be $E_{K2}=D_{K2}(E_{K3}(P))$. Then, in the first paragraph you'll need $2^{56}$ operations to construct the table containing $2^{56}$ entries. Now you simply perform the third paragraph of the above attack and need another $2^n$ operations with $n$ being 112 in this case as it is a double-application of DES which can't be attacked by meet-in-the-middle by itself as it is part of such an attack. The attack thus requires $2^{56}+2^{112}\approx 2^{112}$ operations and $2^{56}$ storage.

Now, how's the relation with 3DES (2-key)?
3DES is defined as $C=E_{K1}(D_{K2}(E_{K1}(P)))$. You can't apply the above attack to 3DES, as you now have three encryption / decryption operations.
The best attack to 3DES is due to van Oorschot and Wiener and goes as follows.

Guess the first intermediate value, $a$.
Tabulate, for each possible value of $K1$, the second intermediate value, $b$, when the first intermediate value is $a$ using known plaintext $b=D_{K1}(C)$, for all $p$ given plaintext-ciphertext pairs.
Look up, for each possible $K2$, elements with a matching second intermediate value, b: $b=E_{K2}(a)$.
The probability of a match is $p/{2^m}$ with $m$ being the block size.

The whole attacks requires $2^{n+m}/p$ time and $p$ storage.

(the attacks can also be found in Schneier's Applied Cryptography)

Why is 3DES more secure than DES?
Because the keyspace is larger. 3DES has a keyspace with 112-bits in size whereas DES has only $2^{56}$ keys, which is brute-force-able.


They are not. First of all, $\{0,1\}^*$ and $\mathcal{G}$ are not "values", they are sets. $\times$ does not mean multiplication, but the Cartesian product of those sets. Second of all, those are not definitions of functions. All that's specified there is the domain and range of the hash functions. Specifically $H_1$ maps tuples $(a,b,c)$, where $a\in\{0,1\}^*$ and $b,c\in\mathcal{G}$ to an element of $\mathbb{Z}_n^*$.
See above. $H_2$ maps tuples consisting of two elements of $\{0,1\}^*$ and four elements of $\mathcal{G}$ to an element of $\mathbb{Z}_p^*$.
You don't need any prime numbers to define a hash function. But also there are no definitions of hash function anywhere in your question.
They have a different domain. Meaning that they accept different inputs.
The output of those functions is not a bitstring. It's an element of $\mathbb{Z}_n^*$ and $\mathbb{Z}_p^*$ respectively. The values may be encoded as a bitstring, where the canonical encoding would indeed have length at most 160 bits.


DCT Steganography - Where to embed the data

The quantization table is part of the compression or decompression stage in JPEG, but for using steganography you should not compress/decompress the image, because these operations modify the DCT coefficients.

The usual process to hide a message in JPEG files is:

Read DCT coefficients from the JPEG file.
Modify the DCT coefficients to hide the message.
Write the DCT coefficients into the JPEG file.

So, the compression needs to be done before you hide the message. And if you decompress and compress the image again you could destroy the message.


How to determine if a protocol is a Zero knowledge proof

Let's analyze the correctness, zero-knowledge and soundness properties of this protocol proving the pre-image of a group-homomorphism $(\psi(w):w\rightarrow w^e\bmod{N})$ over a group of unknown order ($\mathbb{Z}^{*}_{N}$)!

Correctness

The correctness of the above protocol is straightforward to see. If the claimed relation, $y=x^e\bmod{N}$, holds then the verifier always accepts the proof. This is because $f^e=(rx^c)^e=r^ex^{ce}=ay^c$. The first equality follows from the definition of $f$ and the last equality follows from the definition of $a$ and $y$.

Zero-knowledge

It is also quite easy to build a simulator for this protocol. The verifier can simulate the protocol transcript on its own, without interacting with a prover as follows. It chooses a random $f'\in_R\mathbb{Z}^{*}_{N}$ and $c'\in_R[0,e-1]$, then $a'=f'^{e}y'^{-c}$. Put differently, the simulated transcript $(a',c',f')$ is computationally indistinguishable from a "real" transcript $(a,c,f)$, i.e., $(a,c,f)\approx_c(a',c',f')$. They are just random integers in $\mathbb{Z}^{*}_{N}$ that also satisfy the verification equation, $f^e=ay^c$.

Soundness

Even though this was not part of the question, but still this is the most interesting part of the analysis of any sigma protocol over groups of unknown order. The knowledge error (the probability that a malicious prover can convince the verifier that $y=x^e\bmod{N}$ without actually knowing $x$) of this sigma protocol is at least $1/d$, where $d$ is the smallest divisor of $e$. Practically speaking, this means that any application relying on this protocol needs to run this protocol multiple times in order to achieve reasonable levels of soundness of the zero-knowledge protocol. For more details on this inherent efficiency, see this work by Bangerter et al.


How is Encryption Actually Used in Public Networks at This Moment?

In relation to email, Google reports regularly on the use of TLS on incoming/outgoing mails through its servers, which is significant sample size given the popularity of GMail. See below.

https://transparencyreport.google.com/safer-email/overview

You can examine the data in quite some detail to see TLS usage by domain, country etc.

They also see to have other reports on HTTPS usage etc. although I haven’t checked them out myself.


Difference between actual attacks and theoretical attacks on SHA cryptographic series

A theoretical attack is an attack strategy that was born out of “theory”, “calculation”, and — in the least cases — “simulation”. Yet, the strategy is yet to be proven in practice.

An actual attack which is practically proven and can be replicated is actual proof that a theoretical attack works. Therefore, the first is an indication of a weakness, while an actual attack is proof that that weakness actually exists.

It's actually not so much different from every regular science project. A theory is just a theory until someone can prove the theory is correct... transforming the theory into a fact.

In your SHA examples, SHA-0 is practically proven to have a weakness and - depending on available resources available for the attack - that weakness translates into "it's broken".

SHA-1 on the other hand has been proven - in theory - it's broken too, but up until now, I’m not aware of anyone having put the theory in practice. Since attackers don’t usually share the news about their efforts, chances are practical attack efforts exists but news about it hasn’t been shared with the general public.

Personally, I regard "theoretical attack vectors and/or strategies" as a warning, while I regard "practically broken" as a red alert. After all, a theory could have some flaw rendering it void, but if someone has practically broken something, statistical chances that others will do the same rise every second.


Key derivation using the main AES encryption key and some plain text?

NIST has defined some key derivation functions, which can be used to derive new key using one of NIST recommended MAC algorithms, AES-CMAC or HMAC. These functions can meet your needs.

The functions are defined in NIST SP 800-108: Recommendation for Key DerivationUsing Pseudorandom Functions.

Because you intent to use AES Encryption Key for encryption using AES algorithm, you need to pick key derivation mechanism that does not use AES algorithm in ways which may conflict with your use of the key. To do this, you may choose to use the functions with HMAC algorithm, for instance with SHA-256 hash function. (Do not choose AES-CMAC.)

When using construct (Counter Mode KDF, Feedback mode KDF or Double-Pipeline KDF) from NIST SP 800-108, the plaintext can be e.g. Label and the AES encryption key needs to be the KI. For instance:

Use KDF in Counter Mode, with

h = the length of HMAC key desired
r = 1
KI = AES encryption key
Label = the 10 digit plain text
Context = empty string or suitable identifier identifying your protocol or key use purpose.

BTW, instead of deriving HMAC key from the AES encryption key, it is more common to use key derivation key to derive all required key material, i.e., to use KDK (Key Derivation Key), which derives enough key material for both the Encryption Key and the HMAC Key. This practice is recommendable because then encryption key is not used for two different purposes: encryption and key derivation. Use of keys for multiple purposes is generally considered back practice as it increases ways possible attacker may try to get information about the key.

I.e. I would recommend you to consider this instead

AES-CTR-KDK(KDK, plaintext-key) = AES-key (first 128-bits) || HMAC-key (last 256-bits).

[These are typical key sizes, customize the key sizes according to your needs.]

Furthermore, when proposing KBKDF (key-based key derivation function) I'm assuming your use of 10 digit plaintext is not used as PIN for authentication purposes. Then be careful, as it might be possible for attacker to brute-force the key space of $10^{10}$.


Affine cipher: calculate the key from a known plaintext/ciphertext pair

Given that you have parts of the plain text and its corresponding ciphertext, this is called a known plaintext attack.

Given an affine cipher that has a key that is composed of 2 parts $a$ and $b$, you can express it as a system of 2 equations with 2 unknown.
Assuming the usual mapping $\mathtt{a} \to 0$, $\mathtt{b} \to 1$, etc., you need to solve the following system of linear equations:
$$\left\{ \begin{array}{l}
4a+b = 5 \\
18a+b = 23 \end{array}\right.$$
where the encryption function is $x \mapsto ax+b$. Solve it exactly as you would in $\mathbf{R}$, just be careful when dividing.


have a question in the book "introduction to modern cryptography"

By taking enough samples, it is possible to ensure that the majority value is the correct one with high probability. To prove this, you use Chernoff's bound. Now, the more samples that you take, the higher the probability that the majority value is the correct one (when plugging into Chernoff). So, this is a parameter that you can choose however you want. We choose $1-\frac{1}{2n}$ since this is what we need to finish the proof. There is nothing special at all about it; and you can also get much higher probability by sampling more (but it's not needed). I hope that this is clear now.


Security of (2,2) Shamir's visual secret sharing scheme : How are the 2 shares random?

First of all, coin tossing represents a uniform random generator. Therefore, the selections are assumed to be uniform.

In order to create a share for a pixel, as you mentioned, a pixel split into two subpixels. A share for

a white pixel can be $[(B|W),(B|W)]$ or $[(W|B),(W|B)]$
a black pixel can be $[(B|W),(W|B)]$ or $[(W|B),(B|W)]$, where in $[(x,y)]$, $x$ represents the color of left pixel and $y$ represents the color of right pixel.

or, one can see from the image;

The superposition is putting the images on top of each other. White shares construct a half white and half black square and black shares construct a black square. When the selection is random, the shares are indistinguishable from being white or black.

How a share is constructed

For each pixel, toss a coin to select a row. For example, assuming that when the toss result is Tail, we select the first rows;

for white pixels, select $[(B|W),(B|W)]$ and
for black pixels, select $[(B|W),(W|B)]$.

Similarly, for Head result, we select the second rows.

for white pixels, select $[(W|B),(W|B)]$ and
for black pixels, select $[(W|B),(B|W)]$.

The confusion

If we toss a coin for the second share (instead of selecting the share together), then for example; for a white pixel after a Tail (select first row $(B|W)$), we may select the second row with a Head then the white pixel will be shared as $(B|W)$ and $(W|B)$. In superposition, however, this constructs a black pixel $(B,B)$. Therefore, they must be selected together.

Share 1 and share 2 are random in group-wise.


Are there any asymmetric key encryption/decryption algorithms?

You are mistaken that there aren't any cryptographic standards that describe asymmetric encryption / decryption. You name RSA as an example and then you just show the modular exponentiation. However, in PKCS#1 - the predominant RSA standard - there are methods described to encrypt with a public key and decrypt with the private key. Currently it contains PKCS#1 v1.5 compatible padding (official name RSAES-PKCS1-v1_5) and OAEP (official name RSAES-OAEP). In the standard there are also some links to older standards that these schemes have been derived from.

In principle you can simply split up the blocks and encrypt each block. However, the input block size is indeed smaller than the output block size. Furthermore, modular exponentiation is way too expensive for the private key operation. There is simply not much reason to choose just RSA over hybrid encryption. You could say that you could rearrange the RSA blocks as they always would decrypt even in the wrong order, but AES-CBC doesn't provide any integrity or message authentication either, so I've always seen this as unfair. If you require integrity or message authentication then you'll have to sign the encrypted blocks (or sign before encryption, depending on the use case).

For DSA and therefore ECDSA there is no good encryption method. There is El Gamal encryption, but because the sizes of the keys are relatively small for ECDSA, it is even less efficient than RSA encryption.


$P \ne NP$: a proof relating complexity theory to block ciphers

and the elf model proves a secure block cipher exists

It is worth mentioning that lower bounds in computationally limited settings do not "lift" [1] to lower bounds in computationally stronger settings. For example, there are lower bounds of $\Omega(\sqrt{|G|})$ on DL in the generic group model. This does not prove that DL is hard in "real life" though (and in fact, finite-field discrete log has $o(\sqrt{|G|})$ algorithms).
Secure block ciphers are not known to exist unconditionally. I don't know if your post precisely says this anywhere (this is the impression I get of the insight of your post though), but a proof that a secure block cipher exists immediately proves that $\mathsf{P}\neq \mathsf{NP}$.
This is because:

Secure Block ciphers are Pseudo-Random Permutations (PRPs)
PRPs imply One-Way Functions (is this HILL89? Idk its one of those old results)
The existence of One-Way Functions directly shows $\mathsf{P}\neq\mathsf{NP}$ (the problem of inverting a poly-time computable function is easily shown to be in $\mathsf{NP}$. The function being one-way means this can't be done in $\mathsf{P}$, and therefore we've found an $\mathsf{NP}$ language which is not in $\mathsf{P}$.

[1] There are areas of complexity theory which try to do exactly this though. Look up "lifting theorems" in communication complexity in particular, where lower bounds in weak models (generally things like decision trees) are "lifted" to lower bounds (for slightly different problems generally) in stronger models. This all being said, I do not expect lifting theorems to be useful for your application.


Decrypting message as MSB in regev scheme

You have some errors on the definition of the Regev's Scheme

Keygen($1^n$):

sk : choose $t = (1,s)^t \in \mathbb{Z}_q^{n}$ where $q$ is an prime between $n^2$ and $2n^2$
pk = $B \in \mathbb{Z}_q^{m\times n}$ random except $[B \times t]_q$  "small"

$Encryption(B,\mu \in \{0,1\}$:  For random $r \in \{0,1\}^m $ output and $\mu \in\{0,1\}$
$$c \leftarrow (\mu,0,...,0) \cdot \frac{q}{2} + r \times B$$

$Decrypt(c,t)$ : Compute

$$\langle c,t\rangle =  \mu \cdot \frac{q}{2} + r \times B \times t = \mu \cdot \frac{q}{2} + \text{ "small"} \pmod q$$

Recover $\mu$ as MSB$([\langle c,t \rangle]_q)$

Details

the secret key is a $n$ dimensional vector in $\mathbb{Z}_q^{n}$ where the first component is $1$

The public key is a matrix except that when you multiply with the secret key $t$ you will have a vector in $q$ that hash small values $[B \times t]_q$

The random $r$ is a bit vector of size $m$, $r \in \{0, 1\}^m$.

The message It is a bit, yes you encrypt either $\mu \in \{0, 1\}$, and  for a vector of size $n$, $(\mu,0,...,0)$

Encryption :

$$c \leftarrow (\mu,0,...,0) \cdot \frac{q}{2} + r \times B$$

Decryption :

\begin{align}
\langle c,t\rangle &= \langle (\mu,0,...,0) \cdot \frac{q}{2} + r \times B ,t\rangle\\
 & = (\mu,0,...,0) \cdot \frac{q}{2} \times t + r \times B \times t \\
 & = (\mu \cdot \frac{q}{2},0,...,0) \times t + r \times B \times t \\
 & = \mu \cdot \frac{q}{2}+ r \times (B \times t)
\end{align}
remember $[B \times t]_q$  was chosen as "small" and  $r$  was a bit vector. If you consider the final integer in $\mod q$.
$$\mu \cdot \frac{q}{2} + \text{"small"}$$
The "small" in the beginning is adjusted so that $r \times B \times t$ never exceeds $q/2$.
Now, calling the MSB on the result will provide the $\mu$ since $\mu \cdot q/2$ makes the MSB 0 or 1 depending on the $\mu$.
Correctness
The small term is also called the error $e$ term. The correctness requires that $|e| < \lfloor q/2 \rfloor /2 $

Note: I did not go to verify the example, since $q$ is so small to work. The bounds must be carefully controlled.
The below sageMath code is working, however, one needs to tune the "small", that is left!

q = 129 # n^2 < 129 < 2n^2
R = IntegerModRing(q)
n = 10 # vector size
m = 10 # random vector size

def randSecretKey(R, size):
    v = vector(R,sample(range(q), size))
    v[0] =1
    return v

def randPublicKey(R,m,n):
    m2 = random_matrix(R,m,n)
    return m2

def randomBitVEctor(R,size):
    v = vector(R,[randint(0, 1) for i in range(size)])
    return v

def smallPKSK(R,m,n,sk,q):
    trials = 0
    small = false
    while not small:
        trials += 1
        inrange = true
        pk = randPublicKey(R,m,n)
        c = pk*sk
        for i in c:
            if i > 50:
               inrange = false
        if inrange == true:
            print( "number of =", trials)
            return pk

def encodeMessage(R,bit,m):
    mu = zero_vector(R,m)
    mu[0] = bit
    return mu

def encrypt(R, q, mu, r, B):

    return mu * R(64) + r * B

def decrypt(R, c, t):
    return c*t

sk = randSecretKey(R,n)
print("\nsecret key = ", sk)

pk = smallPKSK(R,m,n,sk,q)
print("\nPublic key\n")
print(pk)

pk*sk

r = randomBitVEctor(R,n)
print( "r = " , r)

mu = encodeMessage(R,1,m)
print("mu = ",mu)

c = encrypt(R, q, mu, r, pk)

print("ciphertext = ",c)

p = decrypt(R, c, sk)

print("plaintext = ",p)
Integer(p).digits(2)


The key you wrote down contains a mixed alphabetic and digit symbols because it is written in its hexadecimal representation: i.e. using symbols from 0 to 9 and from A to F. More on this topic on Wikipedia page.
You can easily convert hexadecimal to decimal using software as python, sage, Pari/GP and many others.
An online converter could be found here: Hexadecimal to Decimal Converter

About the key generation, the process is the same you described but with bigger numbers: a standard RSA key uses primes of about 1024 bits. The real different part is find a prime number of such size: there are some algorithms that outputs a number of wished size and (with high probability) prime.


How to collect, process, and transmit data securely?

This question comes up often enough in the context of cryptography that it probably is relevant in a practical sense. I suspect we'll hear even more about it if homomorphic encryption raises interest in "computation in an adversarial setting".

It's not just theoretically unsolvable. A great many software development organizations have tried to keep data secure on someone else's computer and they have all failed. The only exceptions are when no one cares enough about the data to give it any effort, but this is not reliably predictable in advance.

Consider the great effort online game software companies go to in order to discourage cheaters. Yet still, cheating is sometimes a problem even with closed (and continuously online) systems like the PlayStation 3. Even trusted hardware modules fall to reverse engineers with "hardware-based liquid chemical and gas technologies in a lab setting to probe with specialized needles to build tungsten bridges".

The only reasonable goal is to deploy enough obfuscation and misdirection that it delays the inevitable long enough to be worth its cost. As you say in the comments, perhaps you can make it more worthwhile for someone to pursue the contest legitimately.

Obfuscation may occasionally be worthwhile, but its costs and benefits are notoriously difficult to quantify in advance. For one thing, it's somewhat antithetical to your goal of "complete transparency". How can the participants know that the obfuscated code is something they should trust to run on their own computer? Furthermore, it's likely that some would find the challenge of hacking to be more interesting than the competition itself.

That's why every hard-core security professional will advise you not to attempt this when it really matters. Here are some things not to do:

Don't have the application initialize a PRNG from a wide variety of build-dependent data (e.g., a key supplied at build time) as well as system-dependent data. Don't incrementally mix into the PRNG data from intermediate processing steps. E.g., all program inputs, their timestamps, and the arguments of every function call. In the transmitted results, don't include all the runtime-specific data used to initialize the PRNG, the raw input, the timestamps, and some amount of final PRNG output. Don't use self-modifying code. Don't take hashes of the executable memory pages at various points in time. Don't fork the process periodically and take a crash dump which is then included in the submitted data. Don't make a custom gcc back-end targeting a custom VM runtime that is revealed only at the time of the competition. Don't include a bunch of other misdirecting code that ultimately amounts to meaningless random junk in the output. Don't use hardware exceptions and signals to effect ordinary control transfer. Don't develop another program to verify the results produced by the official build, the source of which is revealed only after the competition has closed.

You don't want to do any of that because it can all be defeated in only a few hours or days, max, against a skilled reverse engineer.

Read the history of Microsoft PatchGuard, a software-only system of preventing unauthorized modifications to a running kernel. Version 3, for example, held out for exactly one weekend.


Message security and also program copy detection

The goals stated can't be met according to the requirements defining traditional cryptography (including, public-key cryptography); most importantly, that all methods used except secret keys are public, and communication channels can be eavesdropped and altered (as routinely occurring on a pwned computer, or one fully under control of its rogue user).

The current question remains unclear on if the client computer(s) contain some initial secret/private key (and a certificate, if that secret is not initially also known to the server). I assume they don't. If they did, and could be trusted, and operated by trusted parties, the problem becomes trivial (see also butlast paragraph of this answer).

Goal 1

If the software is public, and there is no initial secret on the client side, then from a cryptographic standpoint, the only goal SSL/TLS (or cryptography) can reach is confidentiality of messages to the server, and authenticity+integrity of messages from the server.

For other directions: we face the problem that without an initial secret tied to a determined entity, we can't make a secret tied with a determined entity, thus can not encipher to or determine origin from a determined entity, in the sense these things have in cryptography; among the best that can be obtained:

A reverse-engineering of the software is required (and hard to some varying degree), in order to compromise the confidentiality of messages from the server that the software does not otherwise output in clear, or to compromise the authenticity+integrity of messages generated by the software itself (rather than accepted as input); otherwise said, the software is considered obscure enough to hold some secret making it a cryptographically identifiable entity.
On a trusted computer (thus excluding one pwned or under full control of a rogue user), after first running an unmodified copy of the software performing an appropriate protocol (that could be a key exchange protocol, or a certification request protocol), this computer/software can hold a secret and become a determined entity, which messages can be authenticated+integrity checked, and which can receive confidential messages that no other computer beyond the server can decipher. Notice that the server can practically not distinguish between this desired situation, and a different reality where the secret ends up shared among many rogue users (for example, the software can be run in a single VM, and the usage of that VM allowed to several rogue users one at a time, including with that VM running on their computer, and the server seeing a single IP thanks to a VPN; see also last paragraph of this answer).

Goal 2

If the software is public, and you assume that the original machine is operated (or pwned) by an adversary (including remotely), then from a cryptographic standpoint, there is no way to detect that a copy of the software is running. Among the best that can be obtained:

It is detected/prevented simultaneously running unmodified copies of the software on two machines.
It is detected/prevented alternatively running unmodified copies of the software on two machines that are not both cooperating and communicating with each other.
Reverse-engineering of the software is required (and hard to some degree) in order to run, unknown to the server, a modified copy of the software that is largely equivalent to the original program, except for functionalities that the server performs and local software cannot; in addition, the required reverse-engineering can be made cryptographically impossible (by encrypting the corresponding code) for functionalities that have not been observed running at least once on an instrumented authorized software.

The method in the question seems to be able to meet 1 and 2 for goal 2. But

The devil is in the details; in particular, the system should work reliably in case of message loss in the "server will send some random number to client" step, which can happens by accident, or be induced in many ways external to the software (as in issue #1 in this answer to a related question). Thus the server will sometime have to tolerate two distinct values in the next interaction with the client. It is hard to get that working reliably and not open to fraud allowing simultaneous use of two copies, especially by an adversary controlling both computers.
In real life, there's software cracking, thus assumptions made that the software is unmodified are unrealistic.
Pwned machines can cooperate and communicate with each other unknown to their respective honest users.
Rogue users of any machine they fully control can make these cooperate and communicate, and even pretend being pwned as an excuse if caught.

If "ignoring software cracking etc." for some wide definition of that (which can match some real-life situations where there is no competent and determined adversary with access to a working instance of the software); and, for goal 1 in both directions, an initial secret unique to each client, and usable for authentication of the client (e.g. because it is the private key to a public key system, and the corresponding public key is certified, and the private key is in trusted hardware like a TPM); and tweaking the protocol in the question as explained; then yes the protocol outlined in the question can achieve goals 1 and 2, at least within the limits I stated.

People who never wrote an hello world! program in any compiled language can install software in the free Virtualbox software in order to circumvent software copy protection. That would be applicable even if the software allowed use only on a machine with a valid SSL certificate and matching private key (which would be highly unusual, and inconvenient to normal users). The technique in the question will not prevent these people from putting that VM on a USB drive that they can move around or lend, or "put in the cloud" with some caching making it quite usable. The technique in the question will prevent multiple instances of that VM to run, and thus discourage the original owner from allowing multiple instances, for fear of being unable to use the software. In that sense, the technique is practically useful. However this is not crypto, which is on topic on CSE; this is security by obscurity, which is not.


Does frequent key change weaken encryption?

Strictly speaking, it does make a brute-force attack more likely to recover a key for any message pair, but the impact of recovering a single key is minimized by frequent re-keying, since that key can't aid the adversary in decrypting any other messages. If you don't re-key, a brute force attack is only marginally more difficult but success gives you everything instead of just one message.


Which is the best AES mode of operation?

There are 2 major types of mode of operation:

The mode requires an initialization vector, which is subdivided into

1.1. a random IV. AES-CBC falls under this category, and

1.2. a unique nonce. AES-GCM and AES-CCM falls under this category.

For either of these subcategory, you should use a mode that provides authenticity guarantee (ideally choose an AEAD mode), so you should go with AES-GCM, or less preferably AES-CCM.

The mode is a DAE (deterministic authenticated encryption), which many may not had encountered.

The AES-KW specified in NIST-SP-800-38-F is one such example, but it sometimes expands the ciphertext. I would recommend you look at AES-SIV in RFC5297.

For the other modes I've not mentioned, ECB simply eats your privacy for breakfast and you won't be able to implement XTS mode that interoperates with other mainstream systems.


Requirements for attacker-controlled ECDSA identity point signature

The reason for that check is not one of security, but of definition. The verification algorithm entails computing the point $u_1 G + u_2 Q_A$, and use its $x$ coordinate to compare it with the value $r$ (modulo $q$). The "point-at-infinity" (the neutral element on the curve) does not have any coordinate $x$ or $y$, since that point is not part of the plane. Thus, what should happen when a point-at-infinity is obtained is unclear; the rule you cite solves the issue by mandating a signature rejection.

If you remove that rule, then what happens depends a lot on the implementation: rule or not rule, the point-at-infinity still has no coordinates $x$ and $y$. A correct implementation should still refuse to output any value in such a case, and report an error. An incorrect implementation may do... about anything. Including accepting the signature as "valid".

In practice, signature verification is done as:

$w = s^{-1} \mod q$
$u_1 = h(m) w \mod q$
$u_2 = rw \mod q$
compute the point $u_1 G + u_2 Q_A$

The values $u_1$ and $u_2$ can be recomputed by anybody. Thus, in order to produce a signature $(r,s)$ such that the point-at-infinity is obtained, one of the two following must hold:

$u_1 = u_2 = 0$
$u_2 \neq 0$ and $u_1 = -x_A u_2$ (with $x_A$ being the private key)

The second case thus requires knowledge of the private key $x_A$, which is, by definition, unknown to the attacker. And, for the first case, it requires $h(m) = 0 \bmod q$, and simply finding a message $m$ that fits that property is a preimage attack on the hash function, with average cost $O(q)$, thus nominally unfeasible with existing technology.

What might happen with a real-world careless implementation is the following:

The computations on curve points are done with projective coordinates. Each point $(x,y)$ is represented by a triplet $(X:Y:Z)$ such that $x = X/Z$ and $y= Y/Z$. This is a classic representation that allows the use of efficient formulas. The point-at-infinity is then represented by $Z = 0$.
The inversion of $s$ during verification ($w = s^{-1}$) is done with modular exponentiation ($w = s^{q-2} \bmod q$). This is not the fastest possible inversion algorithm, but it is easier to implement than an extended GCD.
The implementer, having obtained the point in projective coordinates $(X:Y:Z)$, instead of computing $x = X/Z$ and then comparing it with $r$, finds it smart to check that $X = Zr$, which avoids an inversion.

Under these three conditions, the "signature" $(r,s) = (0,0)$ will be accepted as valid, systematically, for all public keys and all messages! Note that this entails an implementation that gets it wrong twice:

the implementation gleefully computes $1/s$ for $s = 0$ (and obtains $0$);
the verification on the final $x$ is done without checking that the point is not, indeed, the point-at-infinity.

It is an unfortunate fact that such implementations have existed (I won't give names).


Determining collision resistance of a function?

As I understand it, preimage resistance means that it is hard for an adversary to find two messages that produce the same digest

Nope: collision resistance means that it is hard for an adversary to find two (distinct) messages that produce the same digest.  Preimage resistance means that, given a hash output, it is hard for an adversary to find a message that hashes to that value.

  second preimage resistance means it is hard for an adversary to find a message that produces the same digest for a given digest.

Close; second preimage resistance means that, given a message, it is hard to find another message that hashes to the same value.

  Is this function: preimage resistant...

Let's consider this; suppose we get a target value $M$; how hard is it to find inputs $x_1, x_2, ..., x_n$ with $f(x_1, x_2, ..., x_n) = x_1 \oplus x_2 \oplus ... \oplus x_n = M$ ?  Hint: suppose we select $x_2, ..., x_n$ to be 0, how difficult would it be to find an $x_1$ with $f(x_1, 0, 0, ..., 0) = M$?


Encrypting and MACing different data with same key

It depends on how you encrypt and mac.

If you can still choose then you should use an authenticated encryption with associated data mode (AEAD) like Galois/Counter Mode. If all data you want authenticated in a message has to be transmitted in the clear then just leave the encrypted part empty. These modes have the advantage that they were designed to use just one key and have solid security proofs.

For any other combinations it depends on what algorithms and modes you use for encryption and mac. Mostly this analysis is not worth the trouble, as deriving two keys from one master key is pretty simple (HMAC(masterKey,"Key one"), and HMAC(masterKey,"Key two") for example, or AES(masterKey,0x0…01) and AES(masterKey,0x0…02)). Also any custom crypto (and using the same key twice this way is non-standard) has the disadvantage that code and security reviews get way more complicated and any error is on you.

If you use two algorithms with completely different roots (for example Sha256-HMAC and AES counter mode) you are probably on the safe side, but that is just my feeling with no rigid argumentation behind it.


Background for modular arithmetic function

As discovered by D.W., this is in fact part of recommended IDEA implementation.  IDEA uses $a\cdot b \bmod (2^{16}+1)$, with a special case of handling $0$ as $2^{16}$.  From the Handbook of Applied Cryptography, note 7.016:

  Note (implementing $ab \bmod 2^{n}+1$) Multiplication $\bmod 2^{16}+1$ may be
  efficiently implemented as follows, for $0 \leq a, b \leq 2^{16}$ (cf. §14.3.4).
  Let $c = ab = c_0·2^{32} +c_H·2^{16} +c_L$, where $c_0 \in \{ 0, 1\}$ and
   $0 \leq c_L, c_H < 2^{16}$. To compute $c' = c \bmod (2^{16} + 1)$, first
  obtain $c_L$ and $c_H$ by standard multiplication. For $a = b = 2^{16}$, note
  that $c_0 = 1$, $c_L = c_H = 0$, and $c' = (−1)(−1) = 1$, since
  $2^{16} \equiv −1 \mod (2^{16}+1)$; otherwise, $c_0 = 0$. Consequently,
  $c' = c_L − c_H + c_0$ if $c_L \geq c_H$, while $c' = c_L − c_H + (2^{16} + 1)$ if
  $c_L < c_H$ (since then $−2^{16} < c_L − c_H < 0$).

Which is exactly consistent.

This of course leaves me with some greater questions, such as how IDEA is secure with only linear operations, and where I can read more about it (there's precious little deep discussion online), but those are for a different post.  One other interesting thing is that, unlike other ciphers with constant tables, it's not trivial to look at binary code and recognize IDEA.  You can scan for $2^{16}+1$, but that's not as certain as for instance finding the md5 table.


Well, the normal rules apply, i.e. $(aG + bG) = (a + b)G$, so as long as you add $a$ and $b$ correctly, everything should work fine. Note that you don't actually have to reduce the result of the addition for the point multiplication to give the same result, however your implementation may require the number to be smaller than the order.

Also make sure that you are working mod the order of the curve, and not mod some other number (e.g. the order of the underlying finite field).


Should I delete cryptographic data from memory?

The book Cryptography Engineering devotes part of a chapter to this topic. Overwriting sensitive data with zeroes is a good start, but there are lots of other considerations.

If you rely on a language's default object destruction behavior to zero the memory, it's possible for an unexpected error to prematurely halt the program's execution without it cleaning up after itself. In Java, exception handling can discard object references without cleaning up the objects themselves. [Not sure if this is still the case]
Sometimes compilers will optimize away the code used to overwrite the memory because it's acting on a piece of memory with no other uses in the program. There are a few ways to trick the compiler into not performing this "dead store elimination".
OS memory management can foil your attempts to delete data by paging it to the system's hard disk. There are ways of preventing this but they are language- and platform-specific.
If the OS does a context switch the values in the registers are stored elsewhere in memory until execution resumes. This can cause sensitive data to end up in strange places. Modern processors also have multiple caches where sensitive data can be held.
In languages where memory management is automatic it's even more difficult to know where exactly in the system your allocated memory is (and for how long). In Java, objects all live on the heap and are reference-counted as a part of garbage collection. When there are no more references to the object, it can be deleted by the next pass of the garbage collector. However, short of calling System.gc() there's no way of knowing when garbage collection will occur. And even if you force garbage collection it still might not execute immediately. This SO question talks a little bit about System.gc behavior.
Cold boot attacks happen when keys are always written to the same physical region of a computer's memory. Over time, the electromagnetic forces can cause the memory to retain a state after the power is shut off.

This probably isn't all in scope for your application, but it should give you a good idea of the capabilities of an attacker with physical system access. The most important thing you can do is know your language and platform very, very well. For further reading, this Wikipedia article should give you a good start.


There's no practical difference between zero IV and any other constant IV here.

With some older ciphers that have a small enough keyspace (or weaknesses that allow reducing it) you could have a rainbow table for the encryption of the zero vector which might make zero IV a weaker choice in some cases, but that would be impossible for AES with its 128-256 bit keys.

Note that when a key is only used to encrypt a single plaintext, a constant IV is secure.