What algorithm to use to rotate values in a predefined manner and be able to decrypt them back to the original?

As SEJPM suggests in the comments, you could simply derive each successive value by encrypting the previous value using a block cipher (in "ECB mode", i.e. using the raw block cipher directly), with your "seed" as the key:

$$\begin{aligned}
v_0 &= \text{"abc123456"} \\
v_{i+1} &= E_K(v_i)
\end{aligned}$$

where $E_K(x)$ denotes the encryption of the block $x$ using a block cipher with the key $K$.

It's possible that the iteration above might get caught in a small loop, although if the block size of the cipher is reasonably large (and 128 or even 64 bits should be more than plenty), the probability of this happening within any reasonable number of iterations is negligible; the expected cycle length for an $n$-bit block cipher is $2^{n-1}+1$.

That said, if you want to guarantee that your values will cycle through all possible cipher block values before they repeat, you can use the following scheme instead:

$$\begin{aligned}
v_0 &= \text{"abc123456"} \\
v_{i+1} &= E_K(D_K(v_i)+1)
\end{aligned}$$

where $D_K$ denotes block cipher decryption with key $K$, and $+$ denotes $n$-bit modular addition, when $n$ is the block size of the cipher in bits.

Note that, since $D_K(E_K(x)) = x$, this recurrence can also be equivalently written as:

$$\begin{aligned}
v_0 &= \text{"abc123456"} \\
c_0 &= D_K(v_0) \\
v_i &= E_K(c_0 + i).
\end{aligned}$$

That is, each output value $v_i$ is the encryption of a counter $c_i = c_0 + i$, where the initial counter value $c_0$ is the block cipher decryption of the first output value $v_0$.

Of course, if you don't care about the first output $v_0$ having some certain prescribed value, you can simply set the initial counter value $c_0$ directly to some arbitrary starting value (and, if you never use the same key $K$ twice, you could even just always set $c_0 = 0$):

$$\begin{aligned}
c_0 &= \text{whatever} \\
v_i &= E_K(c_0 + i).
\end{aligned}$$

This is very similar to the counter (CTR) mode of block cipher operation.

If you do want to generate multiple output sequences with the same key $K$, one option is to set, say, $c_0 = k \times 2^{64}$ (for a 128-bit cipher block size, like AES has), where $k$ is a unique 64-bit number identifying the output sequence.  This way, you can have up to $2^{64}$ distinct output streams per key, and can generate up to $2^{64}$ output values for each stream without risking overlap with another stream.

This also lets you, given an arbitrary output block, easily identify both the stream the block belongs to (given by the upper 64 bits of the decrypted counter value) and the position of the block in the stream (given by the lower 64 bits).

(Of course, if you don't need quite that many streams or blocks per stream, you could also use a cipher with a 64-bit block size like Blowfish, and $c_0 = k \times 2^{32}$, to shorten your output values by 50%.)


AES-256 will double the size of photo after encryption?

No, AES is a block cipher that encrypts precisely one block of plaintext and results in a block of ciphertext.

The amount of overhead depends on the mode, but it is usually limited to one block for the IV and one block of padding at most. When an authenticated mode is used such as GCM then you may have one block of authentication tag as well.

Adding to that is any kind of meta data to keep the structure intact, salt for password based key derivation etc. You would not expect an overhead more than 100 bytes or so, where AES and it mode only takes 32 bytes max (as padding and an authentication tag usually aren't used together).

So what can cause this overhead? The most likely culprit is encoding of the bytes. Many libraries output base64 instead of bytes if "raw" output is not specified. Base 64 adds an overhead of about 33% (4 characters for each 3 byte, plus one or two padding characters). This would be in line with your result.

Note that "hex" encoding is not the same as "raw" encoding of the bytes. Hexadecimals is a direct representation of each byte value in text using two hexadecimal digits 0-9 and A-F per byte. If you save these two characters they become a byte each, doubling the size in bytes of the ciphertext. Or, if you are unlucky and save in UTF-16 (the braindead default of .NET) you get a quadrupling in size.

It is of course also possible to wrongly implement the AES, even given a high level API. For instance you could read the input data in blocks and then encrypt each block separately. This could in principle more than triple the size (IV and padding or IV and authentication tag). Instead it is wise to look for a streaming option or update function in the library.


libsodium vs gnupg curve25519 compatibility

Found the solution. All that was needed was to reverse the bytes in the curve25519 secret point. Apparantly PGP uses little-endian for this, while ed25519 uses big-endian.


What are the curly brackets in this cryptographic hash function definition?

This has little to do with cryptography or hash functions. It's slightly abused standard mathematical notation.

$\{0,1\}$ is the set consisting of $0$ and $1$, so the set of all single bits.
For any set $S$, $S^n$ for any natural number $n$ refers to the set of $n$-tuples of Elements from $S$, e.g., $S^2 = S \times S$.
So strictly speaking $\{0,1\}^n$ refers to the set of $n$-tuples of bits, however we generally call these "bitstrings of length $n$".

Finally, $\{0,1\}^*$ is defined as $$\{0,1\}^*=\bigcup_{n\in\mathbb{N}_0}\{0,1\}^n.$$ I.e. it refers to the (infinite) set of all finite length bitstrings.


Why are password database breaches bad if cryptographic hashes can't be reversed?

Users have a habit of choosing passwords badly so that they can be guessed much more easily than cryptographic keys, requiring (say) only a trillion ($10^{12} \approx 2^{40}$) guesses on average instead of a duodecillion ($10^{39} \approx 2^{128}$, or thousand sextillion in the long scale) guesses on average.  Users also have a habit of reusing passwords from site to site, like using the same password for Facebook and Gmail.

Suppose I'm trying to break into your Gmail.  There's only a limited rate at which I can test guesses for your password.  Even if I can narrow your likely passwords down to a trillion possibilities, I can't try more than a few passwords every second at Gmail—even if I had a colossal botnet around the world to avoid IP-based rate limits, and even if I did it in bulk to many targets to avoid account-based rate limits, I'd still be limited by network bandwidth.

But if Facebook's password database gets breached—even if they do everything right like using salts to thwart rainbow tables, using argon2id to raise the computational cost of testing a guess, using OPAQUE to thwart adversaries on the network—then I can try guesses without using the network.  No more rate limits to work around.  No more network bandwidth to worry about.  No more botnet to manage.  I can try guesses offline using my supercomputer cluster tucked away in my evil lair built into the simmering underbelly of a volcano powering my machinations with geothermal heat while sipping at my martini and cackling evilly.

And once I have confirmed a guess for your Facebook password I can try it at Gmail.

There are some mistakes that Facebook could do to make it worse:

Facebook could fail to salt their password hashes uniquely per user.

Then I can search for one of many passwords given their hashes even faster using multi-target attacks like rainbow tables[1] in parallel[2]; if the cost to find one password given its hash is $C$, the cost to find the first of $t$ passwords given their hashes is $C/t$, and the time to find them can be as little as $C/tp$, as long as my volcano supercomputer lair is parallelized $p \geq t^2$ ways.
Facebook could fail to use a costly password hash like argon2id, and instead use MD5.

Then the offline computational cost to test a single guess is as cheap as computing MD5, which costs a few hundred cycles on a typical CPU and negligible memory, in contrast to argon2id which can be scaled to cost billions of cycles and gigabytes of RAM and multiple CPUs in parallel according to the legitimate user's available resources.  This lowers the cost $C$ to find one password and the cost $C/t$ to find the first of $t$ passwords.

In practice, Facebook probably doesn't offload the password hash to the user's computer, so they probably won't use argon2id with billions of cycles of CPU time and gigabytes of RAM and multiple CPUs in parallel, but they will probably use something more expensive to compute than MD5.
Facebook could use a hash that fails to have preimage resistance.

This one is a stretch because essentially no major hash function with advertised preimage resistance has ever been broken[3] (archived).  But if Facebook—for some inexplicable reason—used 2-pass Snefru to hash passwords, then in principle there may be a shortcut to finding a password given its hash more cheaply than just trying passwords until one works[4].
Facebook could just accidentally log their passwords in cleartext.

Well, this one actually happened[5], but Facebook swears that the logs were visible only inside Facebook and that nobody breached Facebook and that nobody inside Facebook would ever dream of abusing insider information like that[6] (archived 2019-06-19), and disclosed it on a night of big news of a long-awaited drama in United States national politics[7].


Is the discretization of the Guassian distribution on torus still a discrete Gaussian distribution?

There are two ways to discretize: rounding and conditioning.
The first discretization you use to define $D_{\mathbb Z,s}$ from $\rho_s$ is using conditionning.
The second one defining $\bar \Psi_s$ from $\Psi_s$ is using rounding (the density at integer $x$ of the former distribution is given the total density of the interval $[x-\frac 1 2, x+ \frac 12]$ of the latter distribution).
So, because of this, the two distributions are not the same. However, for large $s$, they would be very close to each other, because they would both be very close to uniform.
To summarize: the moding (ie going from R to the torus) and discretizing do commute, but only if you use the same discretization on both path.


Distinguishing between a Polynomial and a Laurent Polynomial

Is this possible

Unless querying $g(0)$ gives you a distinguishable error for a Laurent polynomial, and assuming that the values $a_0, …, a_d$ are equidistributed (for both the Laurent and normal polynomial cases), it's not possible if you are limited to $d$ queries.

The question is equivalent to asking "you're given Oracle access to a Laurent polynomial $g(x) = \frac{a_{-1}}{x} + a_0 + a_1 x + \dots a_dx^d$, can you determine whether $a_{-1} = 0$?" [1]

Well, for any fixed value of $a_{-1}$, the $d$ queries can result in any of the $p^d$ possible sets of responses with equal probability (because there exists a unique polynomial $a_0 + a_1 x + \dots a_dx^d$ that results in the $d$ required $g(x) - \frac{a_{-1}}{x}$ values).  Because this is true for any value of $a_{-1}$, we cannot gain any information on its value (including whether or not it is 0).

[1]: Along with the convention that $\frac{0}{0} = 0$


The seminal paper on timing attacks is Paul C. Kocher, ‘Timing Attacks on Implementations of Diffie–Hellman, RSA, DSS, and Other Systems’, CRYPTO 1996, Springer LNCS 1109, 1996 (alternate link in case you hit a paywall).  This is also the standard reference, and it's quite approachable—I recommend reading it.  Here's a coarse high-level overview.

The basic idea for RSA and DH is to measure how long modular exponentiation takes as a function of a secret exponent.

How do you do this with RSA encryption?  Find an automated system that decrypts and sends an answer back to you, and send it a long sequence of messages, and measure how long it takes to decrypt each one.  Any timing variation in the crypto computation itself—once you've isolated noise from the network and other sources—is likely to be dominated by the timing variation in modular exponentiation to compute $m = c^d \pmod n$ for secret $d$, in naive RSA implementations.  (Here $n$ is the public key, $c$ is the ciphertext representative, and $m$ is the padded plaintext representative for (say) RSAES-OAEP, or secret key seed for RSA-KEM.)

How do you do this with RSA signature?  Find an automated system that signs and sends a signature back to you—not a signature on any document you want, only a signature on documents that the legitimate signer wants to sign.  For example, an HTTPS certification authority like Let's Encrypt will do this.  Send it a long sequence of requests to sign, and measure how long it takes to sign them.  Again, the timing variation is likely to be dominated by timing variation in modular exponentiation to compute $s = h^d \pmod n$ for secret $d$, in naive RSA implementations.  (Here $h$ is the message hash, and $s$ is the signature.)

How do you do this with Diffie–Hellman?  Find an automated system that performs DH key agreement with a static key, and ask it to do a long sequence of key agreements with public keys of your choice.  Once again, the timing variation is likely to be dominated by timing variation in modular exponentiation to compute $k = B^a \pmod p$ where $a$ is the static secret and $B$ is the attacker's ephemeral public key.

How do you do this with AES?  It's a little different, and the Kocher paper doesn't go into much detail beyond a casual mention.  The standard reference here is Daniel J. Bernstein, ‘Cache-timing attacks on AES’, Document ID: cd9faae9bd5308c440df50fc26a517b4, 2005-04-14.  It is also fairly approachable.  The coarse high-level overview is that the time it takes the CPU to load an element of an array depends on whether that position in memory is already cached.  By studying which elements of the S-box are typically not cached at some point in the computation yielding $S[k_i \oplus p_i]$, and studying which plaintext bytes $p_i$ cause the computation to take the most time, we can deduce the key byte $k_i$, and repeat for all the others.

There are also side channel attacks on other parts of RSA-based cryptosystems than modular exponentiation, such as Bleichenbacher's attack on PKCS#1 v1.5, which exploits side channels for the bytes that make up valid padding of a secret message representative to enable an adversary to decrypt or sign messages without the private key.  This side channel may manifest as a different error message, or as variation in the time it takes to respond, which extended the idea to RSAES-OAEP (paywall-free preprint), the successor to PKCS#1 v1.5 encryption.  Attacks in this class of side channels, padding oracle attacks, apply in other contexts as well, such as the Lucky Thirteen attack on CBC modes of block ciphers in TLS.

And there are, of course, other variations on the theme of timing attacks: e.g. exploiting cache-sharing in hyperthreading to recover keys from one hyperthread in another on Intel CPUs via the L2 cache, flush+reload attacks to recover keys via the L3 cache, cache-timing attacks that thwart naive RSA timing countermeasures, acoustic cryptanalysis using a microphone to hear variations in the spectrum of sound produced by secret-dependent timing in crypto algorithms, and so on.


A pepper is similar to a salt, but it is kept secret. So while the salt is stored in the DB the pepper is kept elsewhere, for instance in the code that verifies the password hashes.

A pepper can be used anywhere where a salt is present - mainly PBKDFs: password based key derivation functions. It makes somewhat less sense for KBKDF's: key based key derivation functions as the input secret of KBKDF's is already a key and you would expect it to be kept secure as it is.

The pepper is not really a method, it is just an addition to the salt. The salt is still required as the pepper is generally static. That would mean that identical passphrases would generate the same password hash or symmetric key.

The pepper doesn't increase the work factor / iteration count (much) but it does make it impossible for an attacker to perform the calculations while the pepper is not known. Basically the pepper acts as a secret key that is required to perform the calculations.

Stretching the password using an iteration count is a different way of protecting the password. These are two different ways of making a PBKDF more secure; they do not directly influence each other.


Can a zero knowledge proof be faked through http?

Yes, you are missing something. :)

The trick is that the prover commits to the number in each square individually.

The verifier doesn't always get a row, column or block. The verifier choses to see one of those or the permutation of the original puzzle.

If the verifier choses the permutation he can check if the revealed number are indeed a permutation of the original puzzle, if he choses a row or column he checks if all the numbers from one to nine are in it.

Since the prover does not know what is requested he has to commit to a valid filled Sudoku field to make sure that the numbers in each row, column and block are the numbers from one to nine. Since the permutation could be selected it must also be a solution to the initial problem.

Note that you have to repeat this process many times to get security because the prover could guess what the verifier will ask for. In every iteration a new puzzle must be chosen and the verifier must select which part to query independently at random.


ANSI X9.31 AES pseudocode or algorithm explanation

Lets go through the steps in detail:

I = ede*K(DT)

K is a long term secret key; that's a random value which is the key of X9.31; it's selected somehow (X9.31 doesn't specify how), and the security of the random numbers depends on it.  Because you are using AES, this would be a random 128 bit value.

When it says 'ede*K(X)', what X9.31 means is 'take the value X, and send it through the block cipher operation (in the encrypt direction).  X9.31 calls it ede because it was written in terms of 3DES (which is done by doing 3 DES operations, in ede mode); for you, you'd just replace it with a single AES encryption operation.

DT is the current date/time (which is updated for every iteration); for you, this would be a 128 bit value, and the format you select for how to express the current time doesn't matter.

The result is placed into a temporary location (called I)

R = ede*K(I XOR V)

V is the X9.31 current state (which also needs to be kept secret); for you, this is a 128 bit value.

In this step, you take the current state V, exclusive or that with the temp variable I generated in the previous step, send that though AES.

R is the 128 bits of output that X9.31 generates this iteration.

V = ede*K(R Xor I)

Here, you take the two values generated in the previous two steps, exclusive or them together, send them through AES; that's the updated X9.31 state you'll use for the next iteration.

And, remember, when you've done this, R contains the 128 random bits that you asked for...


Can tweaking a cipher have the same or similar effect as changing the key?

Well it'll change the output for sure.  But it's not a great idea.  I don't know what exact arrangements you have in mind, so I'll think of my own along those lines and throw some numbers at you:

Possible number of 128 bit keys = 2^128 ~ 10^38

Possible number of ShiftRows tweaks = P(4!,10) ~ 10^13 -> 42 bits

So  better than I expected (42 bits) but still wholefully inadequate today.  However I'm not sure how you'd actually exchange the tweaks.  Little tables of shifts that you enter into a program that enters them into AES?  Clearly you can't use a password + standard key derivation function.

I'm always messing around primitives to create weird stuff.  But one thing that I've learned from this forum is not to mess with their internals.  They are carefully designed (some might say evolved over time) to be secure and efficient.  By tweaking them you can unwittingly fall foul of the law of unintended consequences.  What if a pattern is created?  Or some form of weak shifts?  Recall totally unforeseen RC4 weak states.  I'm not aware of any crypt-analysis of AES with your ShiftRow arrangement.  How do you know it's secure, just because you can't break it?

So in summary it's not like changing the key to standard AES as that's how it's meant to be used.  You might enter a particular ShiftRow permutation and just break the thing security wise.


What does this step in this protocol for the Yao's Millionaire Problem mean?

In here, it is 1-2 oblivious transfer meaning that for each $i$, the receiver gets $A'_{i1}$ or $A'_{i2}$ but the sender does not know which. The length of the elements $A'_{ij}$ is not important as long as you choose a correct oblivious transfer protocol.


How to perform authentication without central server in P2P?

For P2P authentication, you can go for web of trust concept. Simply this means, if someone is trusted by people you can trust, you can also trust that unknown person. In OpenPGP, a certificate can be signed by other users who trust the association of that public key with the person or entity listed in the certificate. So trust relationships can be propagated.
In addition This presentation discusses about P2P authentication, including authentication methods without central server. It proposes web of trust and few other concepts. Also I found a survey about this topic. You can choose a method according to your requirements. Hope this helps.


Asymmetric Cryptography Confusion - 'Sign' a file to guarantee its source

You should resort to digital signature to solve your problem. If RSA is used to generate digital signature, private key is first used to "decrypt" the file that you want to sign. The software can verify the "decrypted" file comes from you since it was "encrypted" using your public key.


How to combine pepper in random string generation

First of all, you should just trust the random source that the OS provides and call it via os.urandom(n). Not only is it generally safe, but if your OS is unsafe you may have bigger problems on your hands.

If you really do want to use your pepper as an input to the random bytes that are generated, the obvious way would be to encrypt the OS's stream using a block cipher. You then use the ciphertext as your new random source.


Why are these specific values used to initialise the hash buffer in SHA-512?

The initial hash values for SHA-512 are the 64-bit binary expansion of the fractional part of the square root of the 9th through 16th primes (23, 29, 31, ..., 53). That is:

$$I_0 = \left \lfloor \mathrm{frac} \left (\sqrt{23} \right ) · 2^{64} \right \rfloor$$
$$I_1 = \left \lfloor \mathrm{frac} \left (\sqrt{29} \right ) · 2^{64} \right \rfloor$$
$$\cdots$$

And obviously the reason they use primes is that their square root is always irrational, which makes for a nice, random-looking number. Taking the square root of four would be less interesting, as it would give 0. It also means the constants are relatively independent from each other, as none of them can be easily expressed in terms of any other, which might be a weakness - but that probably doesn't matter as much.

They are chosen this way because while they generally don't need to be anything in particular, as long as the chosen numbers don't have some special properties (i.e. setting them to zero might be a bad choice), the designers of SHA-512 wanted people to know that the numbers weren't chosen so as to stealthily introduce a backdoor in the algorithm (for instance, if a certain combination of initial values were chosen, it may have been possible for the NSA to break  the hash function more easily) which would be very difficult to confirm or refute as it would require months, perhaps years of cryptanalysis.

Using publicly available numbers that anyone can recreate, here the fractional parts of some prime square roots, solves this problem - there is no way anyone can change these numbers (nobody can change the square root of 23, for instance), and it is considerably harder to design an algorithm to have a backdoor under set constants, than to design the algorithm first and work out those constants later on.

The first few digits of $\pi$ or $e$ are popular choices too, but only if you use the first digits. If you were using, say, the digits starting at position 94858991, I would get very suspicious.

See Nothing up my sleeve number, also this similar question.


How does Web Cryptography API produce secure PRNG?

How does Web Cryptography API (eg window.crypto.getRandomValues) produce secure PRNG?

Like the specification says:

  Implementations should generate cryptographically random values using well-established cryptographic pseudo-random number generators seeded with high-quality entropy, such as from an operating-system entropy source (e.g., "/dev/urandom").

If the OS gives sufficient entropy and the PRNG is cryptographically strong, that is a secure PRNG setup.

  How can the method be trusted? Or is it event trustworthy?

If you don't trust the browser vendor to not be malicious, you can't do crypto in the browser, period.

E.g. WebKit-based browsers (Chrome1, Safari) seem to use an ARC4-based RNG that drops the early keystream and mixes in OS entropy every ~1.5MB. That can be secure, if correctly implemented.

1 Nowadays Chrome and Chromium use Blink, which does not use ARC4, but uses OS RNGs directly.


BCrypt, Argon2 and scrypt are all "binary-safe".

That is, there is nothing inherent in the algorithms (and their reference C implementations) that would require the "password" input to have any structure.

The only exception maybe being that bcrypt has a 72 bytes input limitation, but that can be worked-around using pre-hashing.

However, particular APIs may wrap things differently and "help" the programmer by cutting off at \0 bytes or similar things. If this is the sort of info you need, you need to consult the documentation / the source code of the relevant wrapper.


If the output size of SHAKE128/256 is variable, why is the security fixed at 128/256?

The inner functions have been specifically designed to only support 128 bit or 256 bit security: it's half of the capacity of 256 or 512 bits. The underlying functions or structure do not change.

You can see this from the following picture, taken from the Noekeon site about generic sponge constructions (SHA-3 / SHAKE / Keccak is a sponge construction):

the capacity is $c$ on the left hand side.

So the output is generated at the squeezing stage, while the capacity (as input for $f$ stays 256 or 512 bits).

This may not matter as much as you think, 256 bit security is considered enough to protect against analysis with a quantum computer. The security won't decrease even if large output is generated.

More information can be retrieved from the Noekeon site:

  When using a random sponge as a security reference, one considers the success of a particular attack. Such a success probability depends not only on the nature of the attack considered but also on the chosen parameters of the random sponge, i.e., its capacity, bitrate and whether it calls a random permutation or a random transformation. The flat sponge claim is a simplification in the sense that we consider only the worst-case success probability, determined by the upper bound on the random oracle differentiating advantage [Bertoni et al., Eurocrypt'08], which depends solely on the capacity of the random sponge. Hence, it flattens the claimed success probabilities of all attacks using a single parameter: the claimed capacity $c_{claim}$.

Later it is mentioned that $c_{claim} = c$.


Most cryptosystems based on elliptic curves can be broken if you can solve the discrete logarithm problem, that is, given the point $P$ and $rP$, find the integer $r$.

The MOV attack uses a bilinear pairing, which (roughly speaking) is a function $e$ that maps two points in an elliptic curve $E(\mathbb{F}_q)$ to a element in the finite field $\mathbb{F}_{q^k}$, where $k$ is the embedding degree associated with the curve. The bilinearity means that $e(rP,sQ) = e(P,Q)^{rs}$ for points $P, Q$. Therefore, if you want to compute the discrete logarithm of $rP$, you can instead compute $u = e(P,Q)$ and $v = e(rP,Q)$ for any $Q$. Due to bilinearity, we have that $v = e(P,Q)^r = u^r$. Now you can solve the discrete logarithm in $\mathbb{F}_{q^k}$ (given $u^r$ and $u$, find $r$) in order to solve the discrete logarithm in the elliptic curve!

Usually, the embedding degree $k$ is very large (the same size as $q$), therefore transfering the discrete logarithm to $\mathbb{F}_{q^k}$ won't help you. But for some curves the embedding degree is small enough (specially supersingular curves, where $k <= 6$), and this enables the MOV attack. For example, a curve with a 256-bit $q$ usually offers 128 bits of security (i.e. can be attacked using $2^{128}$ steps); but if it has an embedding degree $2$, then we can map the discrete logarithm to the field $\mathbb{F}_{q^2}$ which offers only 60 bits of security.

In practice the attack can be simply avoided by not using curves with small embedding degree; standardized curves are safe. Since pairings also have many constructive applications, it is possible to carefully choose curves where the cost of attacking the elliptic curve itself or the mapped finite field is the same.


Is it possible to actually verify a “sponge function” security claim?

After spending more than two weeks reading well over 750 pages while checking the following (PDF) documents…

Sponge Functions
Cryptographic sponge functions
Security Analysis of Extended Sponge Functions
Cryptographic Hash Functions: Recent Design Trends and
Security Notions
On the Implementation Aspects of Sponge-based
Authenticated Encryption for Pervasive Devices
On the security of the keyed sponge construction
Keccak and the SHA-3 Standardization
Computer Science and Its Applications: Csa 2012

…it turns out that the probability of the claim can only be "proven" theoretically. In other words: currently, there is no way to actually and/or practically verify the probability of the claim.

The current status quo states that collisions are theoretically proven to be very unlikely in a cryptographic sense. I guess that — as with all cryptographic theories — only time can tell if that actually provides a problem or not.

But, getting back to my question: no, it can't actually be verified currently.

I don't expect this to change anytime soon either, as the theoretical proof that collisions are very unlikely in a cryptographic sense, seems to be strong enough to regard sponge functions as (let's just call it) "secure". In fact, if you check the linked documents, you will find ample information on how to replicate the theoretical proofs in relation to collision probabilities using sponge functions under a multitude of conditions. As far as I checked, cross-checked, and even practically used those formulas to verify things myself, I got convinced that collisions are indeed very (very) unlikely.

I hope you don't mind that I'm sparing you a copy-and-paste job of more than a dozen of pages full of math code. Those who want to dive in deeper, can fetch the multitude of related formulas and a truckload of additional, interesting information from the linked documents I listed above.


How to convert from curve25519 33 byte to 32 byte representation

The second link you provided actually contains all the information you need:

  Note that ECPoint.point differs from the definition of public keys in [Curve25519] in two ways: (1) the byte-ordering is big-endian, wich is more uniform with how big integers are represented in TLS, and (2) there is an additional length byte (so ECpoint.point is actually 33 bytes), again for uniformity (and extensibility).

Beside of those two difference, the rest is the same.

Now, from BouncyCastle code, you can see that:

PO[0] = (byte)(normed.getCompressionYTilde() ? 0x03 : 0x02);
System.arraycopy(X, 0, PO, 1, X.length);

So, you are right, it will always begin with 0x03 or 0x02 and the actual $X$ value is contained as being the 32 last bytes on the getEncoded() return value.
(According to the draft you linked, it will probably be in big-endian, so you might need to convert them into little-endian depending on why/how you need them.)


Relying on a private public key for authentication

What do I need to look for in a crypto library to achieve this?

There are multiple options for this (from most to least desirable):

You want any public-key encryption scheme and any MAC algorithm and distribute as your public key, the encryption scheme's public key and the MAC key. Then you enforce that every message either has the MAC applied on the ciphertext correctly (proving possession of the key) or on the entire message and the MAC is then also encrypted.
You could also use static-authentication and a CCA2-secure public key encryption sheme (like DHIES, ECIES, RSA-KEM, or RSA-OAEP) and prepend a static secret to each message encrypting it as well. This heavily relies on the fact that an attacker cannot change encrypted messages meaningfully with CCA2-security and is "less clean" than using a MAC.
You can use a scheme that naturally hides the public key, e.g. DHIES or ECIES where one may only learn the group but no the public element from ciphertexts without breaking the encryption. Of course this is a much less common security notion, so one has to be careful whether a given scheme naturally satisfies it.


Does this description of verifiable random functions seem accurate?

Sure VRFs can be used for sortition. One can say that a party is selected if the output of his VRF satisifies some property.

The VRF outputs two things - a random output and a proof that the output is computed correctly. It is not always the case that if the output of a VRF is f(x) the corresponding proof is x. For example, the VRF could simply output a pseudo random function $PRF_{sk}(x)$ along with a zero knowledge proof that the PRF was computed correctly.

"but impossible for them to figure out how the function actually operates in general" :
This would not be accurate, everyone knows how the VRF operates, else how would one verify that the output is actually correct. In cryptography the working of a protocol is never hidden (Kerckhoff's principle)

You can find more information on VRFs here. This is a working IETF draft to standardize the construction of VRFs. They have some interesting constructions there.

Welcome to the community!


Which type of non-basic cipher works better with microcontroller which has no interface and keyboard connected to it?

That's a 32 bit ARM chip (M4), but without any hardware based crypto capabilities. That means that the best choice of a cipher is one that runs best on 32 bit CPU's, e.g. ChaCha20, SOSEMANUK or NORX (taken from this answer by Thomas). Of course for transport security you may want to use authenticated encryption, but you can always bold that on (this seems to be an assignment after all).

Above ciphers are good ciphers to try to implement yourself. However, if there are ciphers available in libraries then you may want to use those and safe yourself a lot of time. Before implementing a cipher, make sure that this is the purpose of the assignment!

Note that a cipher in itself does not offer security. You need a security design for your system for that.


RSA cipher: ambiguous or break by eth root?

Due to poor use of notation, the question uses an incorrect (or at least incomplete) definition of textbook RSA encryption, which actually defines ciphertext $c$ for a given $m$ as:$$c=m^e\bmod n$$This can be read as: “ $c$ equals [pause] $m$ to the $e$th power reduced modulo $n$ ” where power or/and reduced can be left implied, and the pause emphasizes that $c$ is the result of the final modular reduction. It means that $c$ is the remainder of the Euclidean division of $m^e$ by $n$, which unambiguously defines $c$ for given $m\ge0$, $e>0$, and $n>0$. It equivalently means that $0\le c<n$ and $c\equiv m^e\pmod n$, as defined below.

The notation $c\equiv m^e\pmod n$ can be read as: “ $c$ is equivalent to $m$ to the $e$th power [pause] modulo $n$ ” where the pause emphasizes that modulo pairs with the earlier equivalent, rather than with an implied reduction. For non-zero $n$, it means that $m^e-c$ is a multiple of $n$. There are infinitely many $c$ matching this.

Notation rule: when $\mod\;$ is without an opening parenthesis immediately on its left, and without an $\;\equiv\;$ sign anywhere on its left, it means reduction modulo, or equivalently remainder. Otherwise, it tends to mean equivalence modulo. The later is unambiguous when $\mod\;$ is with an opening parenthesis immediately on its left, and with an $\;\equiv\;$ sign somewhere on its left.

Indeed, in order to avoid guess of $m$ as $\sqrt[e]c$, it is necessary that $m^e\ge n$ holds, at least with overwhelming odds. The recommendable method to ensure this is not to directly avoid small $m$; rather, it is to pick $m$ essentially as a random integer with $0\le m<n$. It is safer, and practiced, to choose $m$ in the later way, and then use $m$ as a key to a symmetric cipher protecting the confidentiality of the actual message. Other methods exist that allow conveying with $c$ a small message $M$ reversibly turned into an integer $m$ that is random enough, see PKCS#1 encryption schemes.


Ok, I found the answer.

The answer is yes, singular submatrices may happen in a Vandermonde matrix. Look at this paper for an approach to avoid singular submatrices while creating a generator matrix:

http://oatao.univ-toulouse.fr/2176/1/Lacan_2176.pdf


Your approach seems to have a lot of unneeded complexity and limitations. For example, you must decide the mapping between features and keys in advance. Here are some simpler approaches with more generality:

One key per bootloader: Let's call this the client key. Then to send firmware to a particular bootloader you encrypt/authenticate it using that bootloader's client key.

One key per bootloader, one key per release: You can save compute/bandwidth/storage by avoiding wastefully re-encrypting the same firmware with different client keys. With this approach you generate a release key for each firmware update, and encrypt/authenticate the firmware with the release key and then encrypt/authenticate only the release key using each bootloader's client key (of course, only for those bootloaders that you want to allow to install this update).

One master key: You can also use a single master key and give each bootloader a unique ID. Then, when releasing a firmware update, you can include metadata that lists the bootloader IDs that are allowed to install it. This metadata would be encrypted/authenticated with the master key along with the firmware itself. Then the trusted part of your bootloader checks that its ID is in the list before allowing the write. Note that with this approach if someone manages to read out the master key through a reverse engineering effort, they can easily mass-produce updates for all bootloaders, an un-feature that is not present in the approaches that have one key per bootloader.

To map your "features"-based approach to this, you can consider mapping the different feature sets in your bootloaders to different IDs. So the IDs need not be uniquely identifying each device but only each feature set if you want.

One master public key: Like the above approach, but using public-key cryptography to sign the firmware updates. A break of a single device will allow an attacker to read all future firmware updates, but at least they won't be able to generate homebrewed updates.


Is it necessary to use single hash function for signature generation and HMAC?

As both of us recently learned, the public key signature hash algorithm is negotiated completely separately from the MAC algorithm. DSA and RSA use SHA-1, ECDSA uses SHA-2, and Ed25519 uses, um, Ed25519.

I'm skeptical that SSH crypto performance will be a serious issue for you. I suspect you would have to be transferring a lot of data on a really bad CPU for it to be a problem, that any performance issues you have will probably be elsewhere, and that tinkering with SSH won't make a big difference. Nonetheless, HMAC-MD5 should be the fastest HMAC variant. On the other hand, SHA-1 or SHA-2 are only like twice as slow as MD5, and using one of them may save you from having to implement two different hash functions.

SSH supports other MAC schemes that don't use HMAC at all, and are likely faster. OpenSSH supports UMAC, and there are two AEADs available as well: the standard AES-GCM (implemented incompatibly by OpenSSH) and the new and OpenSSH-only ChaCha20-Poly1305. Without hardware support, ChaCha20-Poly1305 would probably be faster than AES-GCM, and definitely easier to implement safely.

I'd also caution you that writing crypto code is extremely dangerous, with many sharp edges and ways to shoot yourself -- and, worse, your users -- in the feet. It would be better to rely on well-vetted, preexisting software if at all possible.

(Hi e-sushi. :-)


Do Export Restrictions Still Apply To The Key Length of RC4?

Afaik, the general export restrictions on keylengths of common ciphers were lifted during the Clinton administration. Here's the relevant wiki article.


Definition
In the Damgard-Merkle construction for hash functions the compression function takes as input:

a message block and
a chaining value.

For the very first block there is not previous "chaining value". Instead a particular value, called an initialisation vector (IV) is given.
A freestart collision is a collision where the attacker can choose the IV.
In particular in their paper (page 3, Table 2-1), authors found two, slightly, different IVs (only two bits are different):

$IV_1:$ 50 6b 01 78 ff 6d 18 90 20 22 91 fd 3a de 38 71 b2 c6 65 ea
$IV_2:$ 50 6b 01 78 ff 6d 18 91 a0 22 91 fd 3a de 38 71 b2 c6 65 ea

Their attack, as they claim in their work, is the first one to break the whole 80 rounds of the SHA-1 compression function.
Effect
Even if a freestart collision does not immediately give a standard collision, it could be used in multiblock collision search. The chaining value indeed is the compression function output of the previous block.
It is not clear (or at least not to me) how easy the path from a freestart collision to a standard collision is.
As an example: It took 8 years for MD5. The first freestart collision for MD5 was found in 1996 (Dobbertin, Eurocrypt Rump Session) but the first standard collision on MD5 was published only in 2004.
Future work [Next step (from a freestart collision to a full collision)]
Finding out a freestart collision on an hash function does not break completely the function but shows a great weakness. With a freestart collision researchers exhibit the second half of two colliding messages. One could say that we now know how the path leading to the collision but we do not know, yet, where it starts.
Last step left to research is find out a block message $m_0$ which $SHA$-$1(m_0)$ is equal to the freestart IV.
When such message is found, the collision is served. It has to been said that finding out a message that is hashed into a given value is infeasible (it is still an hard problem for the broken MD5 hash function).
UPDATE: The full collision has been found: https://shattered.it/


RSA prove $a^{\varphi(n)/g} \equiv 1 \pmod{n}$

Hint: try to prove that $a^{phi(n)/g} \equiv 1 \pmod p$ for all $a$ satisfying $gcd(a, n) = 1$.

Metahint: $phi(n)/g = (p-1) \times (q-1)/g$; is $(q-1)/g$ an integer?


How calculation over $GF(2^2)$ is executed?

Summary: Addition is bit-wise xor. Multiplication (which you denote as $\&$), is polynomial multiplication in the field $\mathbb{F}_{2^m}$, i.e. modulo some irreducible polynomial of degree $m$ over $\mathbb{F}_2$.

We construct $\mathbb{F}_{(2^m)^2}$ in such a way that it contains an element $x$ such that $P(x)=0$. Since this is a polynomial of degree 2, and it splits in $\mathbb{F}_{(2^m)^2}$, there exist also a $y\in\mathbb{F}_{(2^m)^2}$ such that
$$X^2+X+\phi=(X-x)(X-y),$$
where $P(X)=X^2+X+\phi$ is a polynomial in $\mathbb{F}_{2^m}[X]$.

It follows that $xy=\phi$ and $x+y=-1$, hence $y=\frac{\phi}{x}$ and $y=-x-1$. Therefore
\begin{align}
(a_0+a_1x)^{-1} &= (a_0+a_1x)^{-1}(a_0+a_1y)^{-1}(a_0+a_1y) \\
                &= (a_0^2+a_0a_1y+a_0a_1x+a_1^2xy)^{-1}(a_0+a_1y) \\
                &= (a_0^2-a_0a_1+a_1^2\phi)^{-1}(a_0+a_1y) \\
                &= (a_0(a_0-a_1)+a_1^2\phi)^{-1}(a_0-a_1x-a_1) \\
                &= (a_0(a_0+a_1)+a_1^2\phi)^{-1}(a_0+a_1+a_1x). \\
\end{align}
This is how you arrive at the inverse.

Now note that $a_0,a_1,\phi\in\mathbb{F}_{2^m}$, so all operations to compute $(a_0(a_0+a_1)+a_1^2\phi)$ are in the field $\mathbb{F}_{2^m}$. In other words, addition is just bit-wise xor. Multiplication is polynomial multiplication modulo an irreducible polynomial over $\mathbb{F}_2$ of degree $m$.

Moreover, this means that the inversion $(a_0(a_0+a_1)+a_1^2\phi)^{-1}$ is also computed in the field $\mathbb{F}_{2^m}$, hence we have reduced inversion in $\mathbb{F}_{(2^m)^2}$ to an inversion in $\mathbb{F}_{2^m}$ plus some cheap stuff.


Why is the strength of an Elliptic Curve Cryptography (ECC) half the size of the prime field size?

This is essentially because the best known generic algorithms for discrete logarithm, e.g., baby step giant step, have complexity $$O(\sqrt{G})=O(2^{n/2})$$
where $n$ is the number of bits to represent the elements of the elliptic curve group $G$.

If the eliptic curve group is carefully chosen, that is. So, avoid anomalous curves, for example.


A slight correction about terminology:

The key is constant when you use CTR.
The IV/counter affect the cipher input and so the keystream varies.

The reason this can be decrypted is that the decrypter knows both the key and the IV/counter. They can calculate exactly the same function as the encrypter did, resulting in the same keystream block, which a XOR then cancels out.

The images on the wiki page for block cipher modes show how both sides compute the same thing.


How AES treat string input to encrypt data and what will happen if the cipher key is less than that expected?

How the cipher key is scheduled if it is less than 128 bit (for AES 128), or less than 192 bit (for AES 192) or less than 256 (for AES 256)?

That is undefined; the AES specification does not address that possibility.  The AES 128 algorithm assumes that you give it 128 bits of key (and tells you exactly what to do with that key); it says nothing about what you should do if you're initially starting with less keying data.

The AES block cipher takes a 128, 192 or 256 bit key, and uses that to define a reversible mapping between 128 bit plaintext blocks and 128 bit ciphertext blocks.  However, we often want to do other things than mapping 128 bit strings to 128 bit strings; so we use AES in some sort of "mode of operation" which can perform more versatile functions (such as CBC mode, which with padding, can handle arbitrary sized plaintexts).  As modes such as CBC can handle odd sized plaintexts, and thus might be considered an answer to your first question.  I suppose a mode of operation could also define how to handle an odd sized key (I haven't heard of such a thing, but it wouldn't be inconceivable).


How secure is Shamir's Secret Sharing for password sharing when attacker has t-1 shares?

Shamir secret sharing is information theoretically secure. This holds as long as the attacker knows fewer than $t$ shares. So, even with $t-1$ shares, the attacker still knows nothing about the secret. So a brute force attack given $t-1$ shares is impossible, even an attacker with infinite computing resources could not brute force the secret.

Using a deterministic (yet known to the attacker) transform on the secret to get it to be 512 bits, then secret sharing that value is just fine for protecting the length of the secret.

Yes, you could encrypt the secret with a symmetric cipher like AES-256, though you still have to pad the secret to hide the length. Then you could share the encryption key with SSS. This does lose information theoretic security, however, as AES is not information theoretically secure. In practice I don't believe this to be a major issue, however.


Ephemeral key is held constant in ElGamal

One thing Eve can do is compute the modular division of any two messages.

That is, she is given both $c_2 = mL^k$ and $c'_2 = m'L^k$; she can then compute the value $c_2\cdot c'^{-1}_2 = m\cdot m'^{-1}$.

Whether this, in itself, is sufficient to recover the messages depends rather on the distribution of Doug's messages.  However, what this means (independent of the distribution) is that if Eve has a guess for the plaintext for any of the messages, she can immediately deduce the plaintext for all the other messages.

Note that this similar system IES doesn't share this problem; if Doug repeats all the parameters, well, it will leak if he resends identical plaintexts; however it will still be secure otherwise.


You'd have to move to 9DES rather than 6DES as undoubtedly 6DES would still fall to the meet in the middle attack that can be performed on 2DES, now with the two 3DES block ciphers as parts. That means that (given a large amount of memory), the attack only adds a single bit of security, 113 bits.

Even then, just like 3DES has only 112 bits security for 3 different keys, 9DES would seem to max out to 2 x 112 = 224 bits of security rather than 9 x 56 = 504 bits that you would expect. However, it might well be that the meet in the middle attack on 3DES now doesn't work anymore giving you 2 x 168 = 336 bits of security instead. You might want to prove that.

Of course all the other nasty properties of 3DES are kept. Weak keys, parity bits, small block size and horrible speed all have to be endured. However, now it adds huge keys and additional calculations for this ad hoc fix of an ancient, insecure cipher.

The 5DES scheme probably has 168 bits of security if you use a meet in the middle. DES and other modern ciphers cannot be split in two after all; they are protected against meet in the middle by design (it might be the first thing to fall when a cipher is designed by a well willing amateur that at least gets some things right).


The "s2k" options correspond to the String-to-Key specifiers. An s2k transform turns a human-compatible symmetric secret (a password or passphrase) into a symmetric key suitable for a symmetric encryption or MAC algorithm.

Turning passwords into keys is tricky business because passwords that human can remember and accept to type tend to be weak with regards to exhaustive search (often called "dictionary attacks" in that context, since we are talking about words). Thus, we need a "strengthened" process which is often called "password hashing" or "password-based key derivation". To be brief, a good password hashing process must:

be unique to each case, to prevent precomputations and cost sharing;
be awfully expensive, in a configurable way.

Read this answer for an introduction to the relevant concepts of password hashing.

The s2k-count parameter is used only when the s2k method is "3", i.e. Iterated and Salted S2K in OpenPGP terminology. This password hashing method basically hashes together multiple copies of the salt and the password, concatenated, until the total byte count reaches the specified value. With the maximum value (65011712), about 65 MB worth of data are thus hashed; a modern machine (even a "small" one like a smartphone) should be able to do that in a fraction of a second (say, less than half a second), so this is tolerable from a user interface point of view. However, the attacker will also need to do that heavy hashing for each trial of a potential password; and for him, there is a huge difference between half a second and a millionth of a second, because he has many potential passwords to try.

Now that S2K is not the best in town, because smart attackers will get a substantial boost in their attack by using some GPU (GPU are very good at running hash functions like SHA-1). But this is the best one defined so far in the OpenPGP format.

The --s2k-cipher-algo is about informing the S2K transform about the kind of key it must produce: while symmetric keys are mostly bunches of bits, their length still depends on the intended algorithm (e.g. a key for AES-256 must have 256 bits in length).


Select a single message without showing which one has been selected

Disclaimer: I'm not by any means an expert on this, and my answer is based on things I've read, which may only be the surface of the iceberg. Comments are welcome.

You can create oblivious transfer from any public key encryption scheme for which there is an algorithm that can output strings indistinguishable from real public keys or the same with ciphertexts instead.

Basically, Bob sends $(p_1, \ldots, p_n)$ to Alice where $p_j$ is his real public key and the others are "fake" public keys. Alice sends back encryption of each $M_i$ under the key $p_i$, and Bob is only able to decrypt $M_j$. Moreover, by the properties of the "fake" keys, Alice does not learn which message Bob picked. Of course, this is only secure against passive adversaries that follow the protocol.


Why do we need asymmetric algorithms for key exchange?

Say you encrypt a message with a key $k$.

With symmetric encryption (ie. symmetric ciphers), $k$ must be secret. The sender and recipient must agree (somehow) on $k$. No-one else can be allowed to find out $k$. Anyone else who finds out $k$, can decrypt all the messages encrypted with $k$. For that reason, symmetric ciphers are often called "secret key" ciphers - you have to keep the $k$s secret!
Conversely - somewhat against common sense - with asymmetric encryption (ie. asymmetric ciphers), the encryption key $k$ is not secret. The recipient (not sender) chooses a so-called "public key" $k$, and a so-called "private key" $p$. Then they publish $k$ for all to see - perhaps on their website - but keep $p$ secret. Senders use $k$ to encrypt their messages to that recipient. You'd think, why can't other people use $k$ to decrypt all those messages? The answer is, that with asymmetric encryption, the public key $k$ will only encrypt - it won't decrypt. Only the private key $p$ will decrypt. And the recipient keeps $p$ secret. Since $k$ is not only public - but has to be public for all of this to work - asymmetric ciphers are often called "public key" ciphers.

The critical difference is this. Say you want to send me a message:

With symmetric encryption, either (a) you choose a key, and send it securely to me, so I can decrypt the messsage with that key; or (b) I choose a key, and send it to you, so you can encrypt the message with that key. Either way, we need a secure communication channel, to get the key from one of us, to the other. But if we do have a secure communications channel, why  encrypt the message at all? Why not just send it via that secure channel? If that channel is secure, we don't need to encrypt the message at all. But if that channel isn't secure, we can not safely share the encryption key $k$! This is called the "key exchange problem".
With asymmetric encryption, we do not have that problem. I publish my public key for all to see. You encrypt your message with that key. Decrypting needs the private key. And only I have that! So we don't need a secure communication channel to exchange the encryption key.

In summary, symmetric encryption requires the sender and receiver to share a secret key. Achieving that safely, can be a real problem. Asymmetric encryption only requires the sender and receiver to share a public key. Achieving that safely, is much more straightforward.

Finally, as mikeazo said, asymmetric encryption is enormously slow, compared to symmetric encryption.

So, say you want to send me a very long message, using asymmetric encryption. Here's what you'd actually do:

(1) Pick a random key for use with a symmetric (fast) cipher. Encrypt your message using that (fast) cipher and key. Send me that encrypted message.

(2) Then use asymmetric (slow) encryption to encrypt the following message and send it to me:

 "Hi, I just sent you a message encrypted using the BLAH
  symmetric cipher with key ABCDE123456."

Now I (the recipient) use my private key to decrypt (2). This gives me the information necessary to decrypt (1) - voila! Only a small amount of information was encrypted using asymmetric (slow) encryption. The bulk of the data was encrypted using symmetric (fast) encryption. And none of this data needed a secure channel. You could publish all of this data on the front page of the New York Times, with no loss of security.


Reference for the Security Analysis of Ring-LWE

You should visit the Homomorphic Encryption Standardization web page. There you can find Homomorphic Encryption Standardization.

Also, there is a workshop The Second Homomorphic Encryption Standardization Workshop there you can find this document

Homomorphic Encryption Standard see section 2.0.3

I hope, all this will help in your research.


Security analysis of this one time password based scheme for copy protection

Is the motivation for this a copy protection scheme?

If so, the most obvious problem is that if $K[n]$ is transmitted by the server but not received by the client, then synchronisation is lost.

This could happen if there is a proxy in between as is often the case in corporate networks with HTTP (or more controversially HTTPS) traffic. The updated value could be transmitted to the proxy but not downstream to the client. At this point, the application is irreparably broken.

Is this one-time password being transmitted over a secure channel? If not, then the following problems also apply:

How does the client authenticate that the $K[n]$ really came from your server and not someone else?

How does the server authenticate that the $K[n]$ provided to it, came from the client and not some third party?

If the one-time password is used to authenticate a message came from a valid host, how do I stop the message being modified in transit?


A method for creating distributed public key for ECDSA, what are the risk factors?

Suppose Bob watches Alice publish $A = [a]G$.  Bob then picks $b$ and publishes $B = [b]G - A$ as his share of the public key.  Now the combined public key is $A + B = A + [b]G - A = [b]G$, so Bob can unilaterally sign messages without Alice's consent.


May I use Random Oracle for Inversed Look-up?

Yes, that is standard usage of a random oracle. The simulator gets to simulate the interface to the random oracle so it can record all queries made by the adversary and use this information to "invert" the random oracle.

In your example you must be sure that the simulation does something reasonable when the adversary outputs a value $r$ that is not the result of any call to the oracle.


What are the potential security impacts of using CRAM-MD5 for Emails, when not using an SSL connection?

CRAM-MD5 is a protocol to demonstrate knowledge of a password. In the context of email, it is sometime used by an email client to authenticate to a POP, IMAP, or/and SMTP server. Basically, the password is used as the key of HMAC-MD5 in a challenge-response protocol.

Among positive things there are to say about CRAM-MD5:

The password is not exchanged in clear.
The protocol is not vulnerable to replay.
HMAC-MD5 stands strong (even though MD5 is broken as a collision-resistant hash); thus if the password was unguessable, CRAM-MD5 would provide strong protection against logging by an adversary using passive wiretapping.
The password can be long and contain arbitrary characters as far as the protocol is concerned, making the above if at least feasible.
It is conceivable to use an irreversible transformation of the password, rather than the password itself, to perform the protocol (by keeping the output of the first round of each of the two MD5 hashes in HMAC-MD5); thus a server using  CRAM-MD5 does not really need to keep the password in clear, nor any mean allowing direct derivation of the password (the excuse reportedly given for "storing password in a database in plain text" likely reflects practice, but is wrong from a strictly cryptographic standpoint).
MD5 Rainbow Tables can not help to crack the password from intercepts by passive wiretapping: the challenge defeats that.
Implementation is simple.

On the negative side:

CRAM-MD5 does not in practice meet its primary objective of keeping the password secret from a passive eavesdropper (e.g. using WireShark), because testing a particular password is fast (it requires a single HMAC-MD5, that is typically 4 MD5 rounds), and passwords chosen by anyone except a few paranoids security-conscious persons are guessable by a password cracker. For example this beast reportedly performs 180 billion MD5 per second, that's perhaps 235 passwords tested per second, translating to less than 5 minutes on average to crack the strong (44-bit) variant suggested by the obligatory XKCD reference; the weak (28-bit) variant, which is already very much above average password practice, is vulnerable to a script kiddie using John-the-Ripper.
CRAM-MD5 authenticates one party to the other, not the other way around; in email practice, the client does not ascertain to which server it connects to receive or send email.
Using CRAM-MD5 does not protect the confidentiality or integrity of the data exchanged after login: email can be read by a passive eavesdropper, an active adversary can insert commands in an existing session.

In summary: CRAM-MD5 provides strong protection against disclosure of an exceptionally strong password by way of wiretapping, symbolic protection for real-life passwords, and almost no other security functionality. In the context of email service provided by an ISP, some will consider the issue moot: email exchanged in this way (without end-to-end security as provided by e.g. GPG) is insecure in many other ways.


Is this JS library using openssl genrsa -rand improperly?

I ran the command under dtruss on OSX, with it pointing to a static file. Even then, it appears to use this as an additional source of randomness to /dev/urandom.

It's distasteful and almost certainly pointless. But assuming it only mixes the data into an already cryptographically-secure source of randomness, it's not actively harmful. That said, I can only see the syscalls being made — it's possible this is not what's happening at all under the hood.


Yes, this is a way to establish authenticity through the use of a so-called "shared secret".

In practice you could do it using the HMAC algorithm and a shared key between the server and clients.

Notice that here, there is a problem with shared keys: that is that the whole system is not secure as soon as one client is breached.
There are also other ways to establish authenticity of messages without this problem by the mean of public key cryptography.
In this case your server would be the only one knowing the secret key, and would sign its messages with it, so that the clients, knowing the public key of the server could verify the authenticity of the messages.
Typical algorithms to do so are ECDSA or Ed25519.

Edit

As requested, here are more details regarding how these would work in practice:

HMAC

This is almost exactly as you described in your own edit.

You create a secret HMAC key, which you store on both the server and the clients.
You have a message which you want to authenticate, so you just "HMAC" it on the server using the secret HMAC key, and you send both the message and the HMAC digest to your client(s).
The client receives the message and the HMAC digest and computes the HMAC digest of the message, and then verifies it matches the one it received.

There is just one slight caveat I have with your way:
you pass the value str(payload["key"]).encode("utf-8") as the msg in your HMAC call, but what is contained in your payload["key"] value?
You would rather have your payload itself being passed to the HMAC and then append the hexdigest to the message, thus you'd have a structure a bit like this for your messages:

{
"payload": {
    "boolean": true,
    },
"mac": {
    "hmac-digest": "6eb6a866856dc7ea74c0d6bd41993106f696cc5091f88f188efbb23def6d248b"
    }
}

Now, as you said in your edit, HMAC values being deterministic, if you authenticate twice the same message, you'd get twice the same digest.
But HMAC is about protecting authenticity of the messages, not confidentiality. (Notice that with HMAC, you get both authenticity and integrity of the message.)

Also, it is true that HMACed messages are trivially vulnerable to replay attacks, but so are public-key signed message.
Adding a replay protection to your protocol is not that easy, and usually requires being stateful.

To have replay attack protection, you'd typically need to have a message index value, and keep track (thus being stateful) of the said index on each clients. (And reject any message that does not increase the index value.)

{
"payload": {
    "boolean": true,
    "index": 12
    },
"mac": {
    "hmac-digest": "a1b0271d1eea012c81f06488645ce026914e095d9d770d7d213efbd968be3fe2"
    }
}

But notice that this is still vulnerable to replay attacks between clients, if all clients are not getting the same message at the same time...

Thus, you might want to include sender and receiver data in your payload, so that these are authenticated as well... as you can see the complexity of your protocol is increasing relatively fast!

Public key crypto

So, if you are to use public key crypto to authenticate your messages, the process would only differ slightly from the previous workflow:

You create a private key and its corresponding public key on the server and store them there.
You store the public key of the server on each of your clients.
You have a message which you want to authenticate, so you sign it on the server side using the private key, and you send both the message and the signature to your client(s).
The client receives the message and the signature and uses the public key of the server to verify that the signature was indeed produced by someone knowing the server's private key.

There a multiple algorithm to do so:
- ECDSA
- Ed25519
- RSA-PSS

Notice that the same caveats as with HMAC applies here: you might need to authenticate more than just the message to avoid replay attacks and any other abuse of your protocol.


AES CBC with fixed or predictable IV, what are the risks?

You are hoping to get integrity protection by applying CBC mode; the problem with this is that CBC mode isn't great at providing integrity protection.

One way an attacker can exploit this, if he guesses what the plaintext is, he could modify block N of the plaintext to anything we wants by changing block N-1 of the ciphertext.  This will modify block N of the resulting plaintext to be exactly what the attacker picked; this also has the side effect to setting block N-1 of the plaintext to be something random.  However, the attacker might not care about what block N-1 is (alternatively, he might just hope it results in an innocuous value).

Also, if an explicit IV is given (so that the attacker can freely modify it), he can modify the IV to make the resulting first block of the plaintext be anything he wants, without any other changes anywhere in the resulting plaintext.

Given that you do have a CBC mode primitive, the obvious thing to try is to implement CMAC; this would involve taking the plaintext message, padding it out, computing the CBC mode encryption of that padded message (with a fixed IV), and throw away the entire encrypted message except for the last block.  Then, you'd send the original plaintext message, along with that last encrypted block.  On the receiver side, it would take the received plaintext message, pad and encrypt it in exactly the same way, and see if that results in exactly the same last block.

The advantages of this approach is that it does give you real integrity protection (in that no one in the middle who doesn't know the keys can modify the message in a way that would not be immediately be rejected, except for deliberate replays); and it does all this using only a CBC primitive.


Post-Quantum Public Key Cryptography with EC math properties

Is there any quantum resistant public key cryptography with similar properties of elliptic curves?

Not at the level you're asking about.

The issue is that Shor's algorithm can generically solve the problem "given $A, x \times A$, recover $x$" for any finite group (and going to an infinite group looks problematic for large $x$).  Hence, we'd need to base the algorithm on a different hard problem, and I don't know of any suitable one that fits in the framework you're looking for.

In any case, basing things on a different hard problem would imply that the crypto would look quite different (even if it happens to satisfy the identities you're looking for)

  How existing solutions map to the same properties?

They don't satisfy those identities; instead, they use different properties to provide public key encryption and signatures (and more advanced primitives, such as IBE and PAKE).


Hashing a uuidv4 + time to create a unique id

You know, technically an uuidv4 is already designed to be unique. That's what it's for. In other words, the probability of you generating the same uuidv4 is supposed to be virtually zero. So why are you checking for duplicates?

The whole point of uuid's is to make sure nobody ever gets assigned the same one even if they all do their own separate thing without going through a central authority which keeps track of where each uuid is. So if you're using an uuid, it's questionable to expect that you will ever generate the same one twice.

Which leads me to believe that you haven't correctly identified your actual need. Do you need to bind this uuid of the item to the conversation somehow? If so, you want something similar to a deterministic hash of the item name, which will make sure that if you ever delete, say, "Item57", and then eventually add "Item57" back, you will still know which conversations are associated with this item (and no other). This way every item references only the conversations concerning it, even after they are deleted.

If you just need uniqueness and don't want (or care about) dangling references then uuidv4 already provides that, you should trust it rather than cobbling together your own scheme. If you don't trust proven algorithms, how can you ever trust your own?

Briefly, what are you trying to battle against, exactly, from a high level point of view?


Proving membership of a group without revealing identity?

Look at group signatures (but use one of the more modern schemes; they are proven secure). The signature can be applied to a running counter, or a random challenge. Group signatures also give you a lot of "management" options which can be useful depending on the application. If you don't need them, then you can use ring signatures (but the verifier has to check that the ring includes only members of the set, or someone else can easily join).


Is $F(x) =Ax+b$ a pseudorandom function or not?

I have searched the similar question in network and drawn a solution as follows:

Let's consider the distinguisher $D$ that queries its oracle $\mathcal{O}$ on arbitrary. At first, let $x=0^n$, we can get $b=\mathcal{O}(0^n)$. Then, we access the $\mathcal{O}$ with $x_1$, $x_2$, $x_1+x_2$, output $1$ if and only if $\mathcal{O}(x_1 )+\mathcal{O}(x_2 )-b=\mathcal{O}(x_1+x_2)$.

If $\mathcal{O}=F$, $Pr\left[D^F{^{(\cdot)}}  (1^n)=1\right]=1$.
If $\mathcal{O}=F$ for f chosen uniformly from $Func_n$, $Pr[D^{f(\cdot)}  (1^n )=1]=2^{-n}$.

The difference is $|1-2^{-n}|$, which is not negligible. Therefore, F is not a pseudorandom function.


If P256 ECDH shared secret contains ~128 bits of security, does using first half of the secret (= 128 bits) contain only 64 bits of security?

First of all, generally, the shared secret is split in half because it consists of an X and Y coordinate. It is after all the point resulting in multiplying a public key point with a private key / vector, resulting in another point on the curve. Now the X and Y coordinate are related, so generally, only the X coordinate is used as a shared secret.
Currently, you are assuming that the total result is 256 bits. However, for Elliptic Curves, each coordinate of the curve is 256 bits, making a total of 512 bits. So generally you would be left with 256 bits - not 128 bits - once you split the full outcome of the ECDH key agreement. I'd make sure if that's not what is meant because it would make a whole lot more sense. Please make sure that the result is precisely 64 bytes in that case (if it is more then the header should be removed in such a way that a 64-byte X-coordinate is left - how depends on the format of the point that is generated).
Furthermore, the (classic) security of ECDH with a key size of 256 bits is 128 bits because that's what level of security finite field will produce. It is an indication of the security in bits (compared to e.g. AES) that ECDH produces. However, that doesn't mean that the X-coordinate is not well distributed; to my knowledge it is. So even if you would split the X-coordinate in half you'd still be left with 128 bits of security. Finally, even if there would be an algorithmic weakness then the one-way property of the KDF would, with a very high degree of certainty, remove such weaknesses.
All that said: if indeed 128 bits are used instead of 256 then the protocol doesn't make all that much sense. Using the full 256 bits of a (constant sized) X-coordinate should be preferred.

Notes:

I'd use AES-256 instead of AES-128 and also generate a random IV where required;
256-bit curves only provide 128-bit security against classical crypto-analysis, full-fledged quantum computers would certainly reduce that by a significant amount, rendering the algorithm insecure.


GGM PRG construction: Why do we need to change keys all the time with underlying PRG

Short answer: I'm pretty sure that your suggestion would "work," but I don't think that it would be better than the GGM approach from either a performance or a security point of view.

Long answer: As Mikero suggestions, we have to be careful about the intput and output lengths of the PRGs. So the GGM problem starts with a family of pseudorandom generators whose output length is 1 more than its input length:

$$ G_n : \{0,1\}^n \to \{0,1\}^{n+1} $$

The goal is to produce a family of PRGs with bigger expansion. For the sake of concreteness, let's say that you want a new family of functions that doubles the length of its input:

$$ F_n : \{0,1\}^n \to \{0,1\}^{2n} $$

The GGM construction accomplishes this by using $G_n$ a total of $2n$ times to produce the corresponding $F_n$. It sounds like you want to do things slightly differently. If I understand your question correctly, you want to apply $G_n$ to the input in order to get $n+1$ bits, and then apply $G_{n+1}$ to that in order to get to $n+2$ bits, and so on. Thus, you'll set

$$ F_n (x) = G_{2n-1}(G_{2n-2}(\cdots(G_n(x)\cdots)).$$

I'm pretty sure that you could prove this secure through a simple hybrid argument. However, from a theoretical point of view, I think that I'd prefer the GGM method for a few reasons:

The PRGs with bigger-input-lengths, like $G_{2n-1}$, could be much slower than the initial PRG $G_n$. Remember, each function in the family runs in time polynomial in its own input length.
The hybrid argument will have a rather large error term in the indistinguishability claim. With the GGM approach, you're using $n$ pseudorandom bits each time and you're claiming that they are indistinguishable from $n$ random bits. With your suggestion, things are worse: you're using more pseudorandom bits each time ($n+1$, $n+2$, and so on) and claiming that they are indistinguishable from the corresponding number of random bits.

In practice, it is unlikely that you'd want to use either the GGM construction or your own when building a PRG. However, if for some strange reason you wanted to do so, I think the GGM method is better again, but for a more subtle reason. I'm not sure what initial PRG you'd use in the construction, but I'm assuming it would be something like the assumption "I'm willing to believe that SHA1 is a PRG when used on 159-bit inputs." (HUGE caveat: I'm not suggesting that you should actually make this assumption! It just seems like the most logical way to use a GGM-style approach in practice.) What this really means is that you think

$$ SHA1 : \{0,1\}^{159} \to \{0,1\}^{160} $$

somehow is part of a mythical family of PRGs, even if you don't know what the other members of this family are. Under this assumption, I suppose you could use the GGM construction on SHA1 in order to make bigger PRGs. Your method wouldn't work though, because we don't know the other members from this "mythical family" so we cannot use them in a construction.

Sorry for the long-winded answer; I hope it made sense.


What kind of ECDSA signature encoding is this?

ANS X9.62–2005 states in appendix E.8:

  When a digital signature is represented with ASN.1, the digital signature shall be ASN.1 encoded using the following syntax:

ECDSA-Sig-Value ::= SEQUENCE {
    r INTEGER,
    s INTEGER
}

I found no issue with the DER encoding in the question.

Implementing this is a pain in the neck if there's no library for it (from a painful experience: a common language runtime once accepted invalid encoding with more zero bits in the high order bits of $r$ and $s$ than allowed by ASN.1, then became more strict, breaking invalid but working code calling it).

Update: the standard also states:

  X.509 certificates and CRLs and CMS SignedData represent signatures as a bit string. Where a certificate, CRL or SignedData is signed with ECDSA, the entire encoding of a value of ASN.1 type ECDSA-Sig-Value shall be the value of the bit string.

But AFAIK this is only for certificates.

Now this looks like a purely programming issue, largely off-topic. Best option seems to be: dig documentation or test case for mbedTLS.


Can error be bigger - as in uniformly random? (Learning with Error)

In fact you can sample $Y$ from uniform in $Z_q^n$. An example of such schemes is the NTRU modular lattice signature scheme [1] but it is not the case here. There are mainly 3 reasons that BLISS family of schemes [2] uses discrete Gaussian distribution.

Firstly,  the signer need to prove that he knows the trapdoor (a short basis) namely

$[S, -I],$

to the lattice

$L = \{(u,v): uA+vT = 0 \mod q\}$

Anyone can find vectors of length $q$ for this lattice, i.e., $(q,0,0,...,0)$; but only the signer can find vectors significantly smaller than $q$. This is known as the Ring Short Integer Solution (R-SIS) problem.

Now, if
the vector $Z$ has uniform coefficients in $Z_q$, an attacker is able to find a large vector in $L$, namely $U$, that is a multiple of $C$, i.e., $U = S'C$ for some $S'$. This $U$ is large but it doesn't matter to the verification procedure now, because every legit signature has large $SC$. If required, he can repeat it enough times to ensure that $Z' = Y+S'C$ is uniform in $Z_q^n$. Then $Z'$ will look like a legitimate signature.

In a nutshell, the signer is not able to prove the knowledge of the trapdoor if $Z$ is large. And if both $S$ and $A$ are uniform in $Z_q^n$, there is in fact no trapdoor in the lattice to authenticate the signer.
On the other hand, this attack will not be possible, if $Z$ and $Y$ are small and discrete Gaussian, in which case $SC$ must be small too.

(NTRU modular lattice signature uses a different approach to prove the knowledge of the trapdoor so $Z$ doesn't need to be short.)

Secondly, you still need to perform rejection sampling even if $S,A,Y$ are uniform in $Z_q^n$. Because even if $Y$ is uniform in $Z_q^n$, $Z = Y+SC$ will be somewhat uniform in a different range, which is more or less $Z_q^n$ shifted by $SC$. So if you publish $Z$ with out rejection sampling, each transcript will leak partial information on $SC$.

The third reason of using discrete Gaussian distribution, as you have mentioned, is that $Z$ is also a discrete Gaussian which allows for compression. For example, in BLISS [2], to store an discrete Gaussian vector in $Z_q^n$, you only require $n(log q-2)$ bits, rather than $nlogq$ bits as if the vector were uniform in $Z_q^n$.

[1] https://eprint.iacr.org/2014/457.pdf

[2] https://eprint.iacr.org/2013/383.pdf


How to multiply two Public Keys in Elliptic Curve in Go

Now my question is to how to implement $g^{a*B}$ which are both public keys?

Just given $g^a$ and $g^B$, this is a hard problem (or so we hope); if that is feasible, the strength of the entire system falls apart.

However, both Alice and Bob can compute: for Alice, she computes $(g^B)^a$ (given the value $g^B$ from Bob and her secret $a$).  Similarly, Bob computes $(g^a)^B$ (given the value $g^a$ from Alice and his secret $B$)

Both computations yield the common value $g^{a\cdot B}$


Is using 7-8 random words from all words of a language as password a good idea?

The Bitcoin Bip-39 dictionary with 2048 words can create $\approx 2^{263}$-entropy by tossing the coin 256 times to choose the words randomly. The random bits are converted into 24 11-bit blocks and every block is mapped into one of the 2048 words by ID. Since the random choice allows repetition, we need $n^r$ not $P(n,r)$;

$$2048^{24} \approx 2.9642774844752946\mathrm{e}{+79} \approx 2^{264}$$

If we assume that English has 171,476 words. Then with 8 words;

$$ 171476^{8}  \approx  7.475267765296064\mathrm{e}{+41} \approx 2^{139}.$$ Therefore you will have lower entropy the Bip-39, again. With 7 words;

$$ 171476^7   \approx  4.3593667716158903\mathrm{e}{+36} \approx 2^{121}.$$ Therefore you will have lower entropy than the Bip-39.

As one can see, the choice 2048 and 24 in Bip-39 is clearly designed to reach $2^{264}$ entropy. If you use 16 words as passphrase ( as noted by Dan Neely)

$$ 171476^{16}   \approx 5.587962816287441\mathrm{e}{+83} \approx 2^{278}.$$ that will exeed the Bip-39. 15 words reaches $3.258743390496303\mathrm{e}{+78} \approx 2^{260}$.

  Is it still considered secure

Yes, it is still secure and beyond the reach of any collective power, like the total power of bitcoin miners that can reach $2^{92}$ double SHA256 hashes in a year.

Note: I used to round a lot. I've decided to use full numbers since that changed at least one bit. So, here the Python;

import math

def prinPowInBase2(b,p):

    print(b,"^",p)
    print("\t", math.pow(b,p))
    print("\t", math.log2(math.pow(b,p)+1))
    print("\t", math.floor(math.log2(math.pow(b,p)+1)))

prinPowerInBase2(2048,24)


Deriving AES key and HMAC key from shorter master key

Would these steps result in a suitable pair of keys for AES-encrypt-then-HMAC-authenticate?

Yes. That would be fine. It almost is HKDF-Expand, in fact.

However, as you note, by deriving the two 256-bit keys from a 160-bit key your effective security will "only" be 160 bits, since an attacker could brute force the intermediate key. That is not at all a problem realistically, but if you had strict requirements from e.g. some regulations you would want to fix that.

One way would be to derive 320 bits using PBKDF2 (requiring twice the iterations you pass it) and then deriving the two 256-bit keys from that.

The idea of using every other byte of 512-bit PBKDF2 output that poncho mentioned in comments would also work, but there is a slight weakness in key separation. If one of the final keys – the AES or MAC key (or just a byte of either) – leaks somehow, an attacker can look for the other in less time than expected by only calculating one of the PBKDF2 calls for each password.

Again, that is probably not a real problem, because you will want to keep both keys secret and it is only a factor of four in attack time. It does seem a bit untidy, though, and using HMAC/HKDF for key derivation instead is an easy solution.


Should I split a 3MByte block into smaller blocks if using XXTEA?

You should not use XXTEA, especially in its large-block variant. It's reported as broken, and that seems very credible. Some of the problem is with the overly aggressive $6+52/n$ rounds, but beside this, the cipher has not attracted wide review.
This question discuss other variants of TEA.
Except in the specific cases that you need an all-or-nothing bijection of a block (because you can't afford that encryption makes the ciphertext any larger), or code space is extremely scarce, my recommendation is to use a standard authenticated encryption cryptographic primitive such as AES-GCM. Libraries for that are available in most major languages.


What is 'order' in More Modular Exponential (MODP) Diffie-Hellman groups?

Order here is not anything to do with how you might "order" a row of pencils in order of height (or some similar behaviour) -- but the number of elements in the group in question.


Authenticating code securely and generating a certificate

My question is how do I authenticate my App to the CA, to prevent something else to request these Client Certificates?

There is generally no way to authenticate the client code. Any secret you embed in the app could be extracted. You must assume an attacker can send requests that an authentic client would.

Instead, what you can do is authenticate the user. You can give each legitimate user a secret license key and only allow a single client certificate to be signed per valid license key. (Probably with the ability to reset for reinstall, etc.)

As an example, such a scheme could look like:

User buys app, downloads client and receives a license key.
App asks user for license key. Sends a certificate-signing request to server that proves the license key.
Server verifies the license key is valid and unused, signs certificate, stores the fact that it is now used.

The certificate signing request could be e.g. licence_key||certificate encrypted with the server's public key (which is embedded in the app). As long as an attacker cannot generate valid license keys on their own, they cannot get extra certificates signed.


Brute-force breakability in practice determined by recognizability of plaintext?

If yes, doesn't this mean that if the plaintext is not easily and
  quickly recognizable as such (as for example ASCII-encoded English
  prose might be), brute-force is in practice MUCH harder than the
  so-much-time-on-such-hardware description suggests?

If the plaintext is not recognizable at all (random numbers (from a good generator)) and if the attacker has no other way to test if it is the real data, you are right, just brute-forcing solves nothing.

But, other than good random numbers, what kind of data is not recognizable for someone knowing a bit about computers? Text no, Images no, any file format from known programs no, any file format from unknown programs no (eg. low entropy and many more things), sometimes there are checksums as part of the data, and so on...

  And if yes, doesn't this mean that a trivial (but unknown)
  "pre-encryption", e.g. ROT13 or base-64 encoding makes a brute-force
  attack hugely more difficult?

No, ROT13, data compression and other preprocessing steps (other than good encryption with a different key) do not add security.

Because, even if the attacker doesn't know about the preprocessing step (which should not be assumed, listen to Kerckhoff), such things can be detected easily. Eg. ASCII text with ROT13 is still ASCII text (ie. A-Z), just not as readable. Getting an output with mostly english letters when trying AES keys is unusual => time look at it closer.

  The practical scenario I have in mind is the encryption of one's own
  files on disk, using a standard algorithm, e.g. AES.

Lets take a disk with 1TB. The chance that, with 2^128 keys, multiple keys lead to a sane output (each one of size 2^(8*1024*1024*1024*1024)), is pretty small. And content of a HDD with OS and music and whatever on it is easily recognizable.


What are the characteristics of a quantum secure protocol?

Quantum computers don't attack the protocol, they attack the cryptographic primitives used in the protocol. You need to avoid primitives that can be broken by quantum computers.

Quantum computers don't break all computationally secure cryptography, so you don't have to resort to information theoretic algorithms (one-time-pad).
Symmetric encryption is secure if the keys are big enough (256 bits). Hashes are secure if the output is big enough (256 bits might be enough). Popular asymmetric crypto including RSA, Diffie-Hellman and DSA (including elliptic curve equivalents) will become totally insecure, but there are replacements.

The biggest problem QCs pose for bitcoin is that it uses ECDSA to control ownership of coins. Since QCs can break DSA, everybody who learns your public-key can compute the corresponding private key and steal your coins. Keeping single-use public-keys secret until use can help somewhat, but it's still problematic.

Grover's algorithm might cause some additional issues, including faster mining, $2^{80}$ pre-image attacks against the 160-bit hashes used for bitcoin addresses and faster cracking of weak passphrases for password derived keys.


A solution from the top of my head:

Bob will end the server $(Enc(m), h(m))$ where $h$ is a collision resistant hash.
Now, Bob will interact with the server and provide a zero-knowledge proof that $m$ is the same one in $Enc(m)$ and $h(m)$.

We note that this verification is in NP (the certificate for the verification is the key used to encrypt $m$). Therefore, it is feasible to do the zero-knowledge proof part in polynomial time.


How to compare the order of elements in cyclic groups?

By this definition is there any known algorithm based which one can
  compare the order of two random elements of the group $P_1$ and $P_2$?

No, such an algorithm would allow for an easy break of the elliptic curve discrete logarithm problem. But as this problem is assumed hard for secure curves like secp256k1 us knowing such an algorithm is impossible.

To see this fix the reference generator $G$ to the standard one for the curve with the generator having order $q$. Furthermore let $P=xG$ be the challenge point for which we want to recover $x$. Now define $a=1$ and $b=q-1$.

Compute $m=\frac{a+b}{2}$ and $M=mG$.
Check whether $M=P$ and if so, return $m$.
Check whether $M<P$ using the conjectured algorithm. If this is true, set $a\gets m$, otherwise set $b\gets m$.
Go to 1.

This is a standard binary search as you may have recognized and it will find the discrete logarithm in about $\log_2 q$ scalar point multiplications and algorithm evaluations which is quite efficient.


How would a side channel attack be carried out in a real life situation?

In hardware, most of the implementations for AES are constant time. My experience is that the current is generally too far into the noise floor to get any real data out; however, I've attacked my AES implementation and a commercial hardware implementation as well with success.  In any software implementation of AES (or ones that I know), I can HALT the system, and dump the core via JTAG and get the keys.

To do a power attack on system, it helps if you know something about the system, but the math you are looking at on a per transistor basis is

$$I_{f,r} =I_{thn}\ln^2 \left[1+ e^{\left[{\left(\kappa \left(V_g-V_{thn}\right)\right)- \left(V_{s,d}\right)}\right]/\left({2 U_{T}}\right)}  \right]$$

$$I_{f,r} =I_{thp}\ln^2 \left[1+ e^{\left[{\left(\kappa \left(V_b -V_g+V_{thp}\right)\right)- \left(V_{b}-V_{s,d}\right)}\right]/\left({2 U_{T}}\right)}  \right]$$

for the N and P FETs respectively.  This model is called the compact EKV model, and if you push through the Taylor expansion, you'll get the subvt and abovevt currents.  Generally, you will see the nFETs to be stronger than the pFETs, which lets you get a feel for what the bit states of the system are.  Having said that, on 14nm SOI (this process is wonderful), my pFETs and nFETs are identical, except for a difference in threshold mismatch.  If you drive the voltage down to get the systems running in subthreshold and control the clock, you can get a really good picture of the circuits.  Once you know the circuits, you can then get the keys.

I use a Keithley 2000 DMM and Keithley 6485 picoammeter that are controlled through MATLAB and I can pretty much get anything I want out of the little black boxes.  (I also have a copper box to isolate noise)


help understanding part of Wiener's attack on RSA w/ small d

The previous part of the proof in that paper already shows that $\left|\frac{e}{N} - \frac{k}{d}\right| \le \frac{3k}{d\sqrt{N}}$. As $k < d$ we estimate this by $\frac{3d}{d\sqrt{N}}$, where the $d$'s cancel to get $\frac{3}{\sqrt{N}} = \frac{3}{N^{1 \over 2}} = \frac{3}{N^{1 \over 4}}\frac{3}{N^{1 \over 4}}\frac{1}{3}$.

As $d < \frac{1}{3}N^{\frac{1}{4}}$ we also get that $\frac{1}{d} > \frac{1}{\frac{1}{3}N^{{1 \over 4}}} = \frac{3}{N^{{1 \over 4}}}$.

Combining we get that $\left|\frac{e}{N} - \frac{k}{d}\right| \le \frac{1}{3d^2}$, which is even a better bound (the 2 might be the constant in the continued fraction convergents theorem, so that might explain it presence).


Basically, there are two ways of doing this: the symmetric and the asymmetric way.

For the symmetric way: you put in a secret key, which can be derived from a master key. In that case it makes sense to have a static, unique UID per card, which you can use to derive a key for the tag with the master key. Then that key is put on the card, and you can then create e.g. a challenge-response protocol for it. The inspection system needs to have the master key and do the derivation as well, so to be able to verify the challenge-response.

Of course somebody being able to steal an inspection system and/or retrieve the master key from it is of course the weak point of the system. A lot of these systems have methods of using a new master key / derived key in case a master key gets stolen (and this is detected).

Of course you can also put on a private key and (card verifiable) certificate, signed by a higher level certificate. That way the inspection system can first read out the certificate, verify it using a parent certificate in a trust store, and then again verify a challenge signed with the private key. Of course, a smart card chip costs more than a chip that implements challenge-response, doubly so if it contains a private key - and therefore an asymmetric co-processor (Montgomery multiplier), because these CPU's are too slow and possibly too vulnerable against side channel attacks.

This is the asymmetric way, and it only requires a trusted public key to be present in the inspection system.

As always, with NFC tags or contactless (smart) cards, the more complex / secure the more expensive. Prices quickly go down on higher volumes though.


Why is this homomorphic encryption correct?

Note that $h\in R_q$, which hides the parity of $2g/f$ since $q$ is a prime. For example, $h=[2x^2-6x-8]_{17}$. In addition, all the operations (including addition and multiplication) to compute $c$ are done in $R_q$.


Would using perfect S-boxes in F function of an unbalanced Feistel network produce a simple and secure cipher?

Almost perfect nonlinear permutations of $\{0,1\}^n$ are the best known designs for addressing both linear and differential cryptanalysis simultaneously. However $n$ needs to be odd. Such sboxes could be used in an SPN or feistel setup, but since one usually likes not just even length but power of two sbox bitlengths, for efficiency and implementation considerations, it is not common.

For your $(n-1)$ to one bit, very unbalanced feistel idea, the two issues I see are:

Extremely slow diffusion due to the single bit.
Bent functions are not balanced.

There are balanced quadratic functions which are almost perfect one can use, however, to address 2.

This is an active area of research.

See here, for example, for more discussion of sboxes which are permutations.


There are certainly public key schemes where this is possible. The recent CurveBall exploit was essentially able to switch out public keys on an elliptic curve and thus forge signatures. The same trick could be pulled with the elliptic curve El Gamal encryption scheme. It would be trickier to do with RSA (you have to construct a very special public key), but far from infeasible.


How do I find an actual value for that point so I can manipulate it

You don't, because the articles you read are right, there is no affine representation for the point at infinity. The usual approach is then to have a flag or something in your point class that indicates whether it currently holds the point at infinity and trigger special behavior on the additon and doubling routines when this flag is set.

  that it has coordinates of (0,1)

This is true for curves in so-called Edwards form with $c=1$ (which is quite usual).

  how would I implement point multiplication?

In serious implementations projective coordinates or jacobian coordinates are used for these calculations and the point at infinity does have a representation using these coordinates with which you can work more easily.


Sending the nonce in ChachaPoly1305 with the ciphertext

Yes, it is acceptable to send the nonce over the network when using ChaChaPoly1305.  The nonce needs to be unique for every message encrypted with the same key, but the nonce does not need to be secret.

However, the RFC referenced in the question take a different approach.  It does not suggest using a counter.  That RFC uses information from the protocol that is available to both parties to construct the nonce.  This allows a unique nonce to be constructed without additional protocol overhead and without requiring the sender to keep track of the counter separately.  It does not harm the security of ChaChaPoly1305 if the protocol fields used to construct the nonce are sent in the clear.