Time and Space complexity of MiniAES I am currently doing my masters research on security of wireless sensor networks, the topic is "ENHANCING THE SECURITY OF WIRLESS SENSOR NETWORKS BY COMBINING GEOENCRYPTION AND LIGHT WEIGHT CRYPTOGRAPHIC HASH FUNCTION (LOCHA)"
The encryption process will use MiniAES which IS same as normal AES with all component reduced while maintaining the same structure and security of normal AES. So, i am finding a justification on MiniAES computational time and space complexity when use to show the gab the research will bridge in terms of space and time complexity compared with other existing encryption algorithms to work with limitations of sensors. Though MiniAES is not that popular i do not know if some have an idea or come across such thing.
Thanking you in anticipation for your answers.

The encryption process will use MiniAES which IS same as normal AES with all component reduced while maintaining the same structure and security of normal AES.

MiniAES most certainly does not have the same security as normal AES.  To quote the original paper:
It is meant to be a purely educational cipher and is not considered secure for
actual applications.

Indeed, it has essentially zero security:

It has a 16 bit key.  It is trivial for an attacker to try all 65536 keys to search for the correct one.

It has a 16 bit block size; that means you'd hit he birthday bound after 512 encrypted bytes.

It doesn't reach full change propagation; an output nybble is a function of the key and two of the input nybbles (the other two input nybbles being irrelevent).  Hence, it can be characterized as two 8 bit block ciphers interleaved (hence you hit the birthday bound after encrypting only 32 bytes...)

It's sole reason for existence is to serve as target practice for budding cryptographers.


Impact of distinguishing between random text and cipher text? In theory, distinguishing cipher text from random text is considered insecure for any PRP algorithm.  Say for example - due to Patarin's proof with about six rounds of Feistel Network - the attacker can distinguish cipher text from random text after about $2^{(n/3)}$ queries to the encryption oracle, where $n$ is input size. For example, if the input domain is 32 bits, after around 1552 queries the attacker can distinguish cipher and random strings.

In practice, what does this mean and what exactly is the impact? How will the cipher text look after say 1553 in above example? Will the attacker get to know the key too or will he be able to guess the next few cipher texts?

Patarin's proof isn't about distinguishing ciphertext from "random text", it's about distinguishing a Feistel cipher from a random permutation.  That proof is also in the information theoretic world, which means that the Adversary is computationally unbounded, and as such can deduce everything about the cipher (the 'key', all remaining ciphertexts, etc).

In the more 'practical/useful' sense (i.e. against bounded Adversaries), if the Adversary can efficiently distinguish a cipher from a random permutation then they can usually mount efficient key-recovery attacks against the cipher structure (guessing part of the key in order to 'peel off' rounds, and using the 'wrong-key randomization' hypothesis).  Once you know the key then you can deduce all future ciphertexts.

I should also add that any permutation, whether truly random or pseudorandom, can be distinguished from "random texts" /"random strings" with the following Advantage (probability of success):
$$\mathbf{Adv} \leq \dfrac{n(n-1)}{2^{\ell+1}}$$
Where $n$ is the number of requested chosen plaintexts and $\ell$ is the blocksize of the permutation in bits.  This is because if you select $n$ distinct plaintexts you will always get $n$ distinct ciphertexts if the Oracle is a permutation.  But if the Oracle is returning random strings then there might be a collision in the outputs (and the probability of collision grows with the amount of requested plaintexts, becoming essentially $1$ when around $2^{\ell/2}$ requests have been made).


Determining strength of a crypto algorithm - clarification with the salsa paper I am reading through the salsa family paper and on the second page DJB says this -- One can reasonably conjecture, for example, that every function that encrypts data in 0.5 Core-2 cycles/byte is breakable.

Why is this so obvious/easily conjectured? Also, does 0.5 Core-2 cycles/byte mean that the algorithm take 2 cycles to encrypt a byte using 0.5 core? Is there a table or some paper that talks about the timings of algorithms in Core-Cycles/byte? I am guessing this is implementation dependent as well, though the algorithm design also sets lower bound on this.

In the next sentence he says -- One can also conjecture that almost every
function that encrypts data in 5 Core-2 cycles/byte is breakable.

Again, its not obvious to me. Can someone explain these two sentences to me?

Here is a link to the paper

One can reasonably conjecture, for example, that every function that encrypts data in 0.5 Core-2 cycles/byte is breakable.

This is wrong. OTP is below 0.5 cycles/byte, and as we know it's very secure. Now, the author probably meant proper encryption, like functions that actually take key that doesn't have to be longer or equal to message length.

  Also, does 0.5 Core-2 cycles/byte mean that the algorithm take 2 cycles to encrypt a byte using 0.5 core?

There isn't such thing as 0.5core. Core 2 Duo is architecture of Intel processors, and this means that on such processor, you can encrypt 2 bytes of ciphertext per processor cycle (but keep in mind that operations on ciphertext are usually done on 16-byte blocks, so this means that you do 8 operations on ciphertext).

  Is there a table or some paper that talks about the timings of algorithms in Core-Cycles/byte? I am guessing this is implementation dependent as well, though the algorithm design also sets lower bound on this.

It is implementation dependent, but authors usually give performance they were able to get using optimized implementation, and usually only include time it takes to execute some core function, without padding, key setup etc. Cycles/byte are usually calculated by measuring time it takes to execute algorithm, because for many years now, there isn't set time in which CPU operation finishes.

  Again, its not obvious to me. Can someone explain these two sentences to me?

Well, to achieve avalanche effect, you have to mix data. And author assumed that you cannot do this in 5cycles/byte. But actually Chacha20, variant of Salsa optimized for modern CPU's instructions, seems to be able to get to about 3-4cycles/byte. See here


What is the security strength of an n-bit HMAC? HMACs depend on preimage resistance, or so I have read. The security strength of hash function with an $n$-bit output against collision attacks is $2^{\frac{n}{2}}$. Against preimage attacks, it is $2^{n}$. What is the security strength of an $n$-bit HMAC?

See NIST SP 800-107, section 5.3.4:

  The effective security strength of the HMAC key is the minimum of the security strength of $K$ and the value of $2C$. That is, security strength = min(security strength of $K$, $2C$). For example, if the security strength of $K$ is 128 bits, and SHA-1 is used, then the effective security strength of the HMAC key is 128 bits, since for SHA-1, $2C = 320$. Note
  that, in this example, even if the security strength of $K$ is greater than 320 bits, the effective security strength of the key is limited to 320 bits (the value of $2C$ for SHA-1). In general, there is no benefit in generating $K$ with more than $2C$ bits of security. In particular, it is not sensible to generate $K$ with a bit length that exceeds the input block size of the approved $L$-bit hash function employed in the HMAC construction. Such a $K$
  is hashed, and the resulting $L$-bit value is used instead. Returning to the SHA-1 example, suppose that the key $K$ has a bit length greater than 512 (the input block size for SHA-1). Instead of using $K$ directly, HMAC replaces $K$ by its 160-bit SHA-1 hash value, and so the effective security strength of that choice of $K$ is no more than 160 bits.

Note that $C$ is defined as the size of the chaining value in above, which is generally equal to the output size without any reduction (so 256 for SHA-224 and 512 for SHA-512/256).

This of course doesn't mean that the security of the HMAC isn't related to the output size. The above description shows the security of the key, not the security of the final hash. You won't get 512/1024 bit security when you only generate a 256 bit result. In general though the final strength should therefore be min(keysize, output_size).


Exchanging Keyspace and Message space in PRF Suppose there is a secure PRF $F: K \times X \to Y$. Then is $F': X \times K \to Y$, defined by $F'(x,k):=F(k,x)$, a secure PRF?

In my opinion it should be because exchanging the keyspace with the message space shouldn't effect the security. As we were choosing a random key from the key space, similarly we can choose a key from message space randomly and can use to compute $F'$. However, I am not sure about my intuition.

In general this is not the case. Consider a PRF F which ignores the first bit of the key. Then you can distinguish F'(k,.)=F(.,k) from a random function (and thus break its security as a PRF) by querying it on inputs x and x', where with x' we denote x with the first bit flipped. Note that the outputs of F'(k,.) will collide on inputs x and x' as F(x,k)=F(x',k).


What algorithm would give the shortest ciphertext for very short plaintexts? I have to encrypt some very short messages (approx. 5 characters) and I would like the ciphertext to be as short as possible.  I am currently using AES but the initialization vector (IV) is making my minimum cipher text be 32 bytes, even for plaintext of 1 byte.

Can I do better than 32 bytes?

There is a technique called "format preserving encryption", which could be called an "arbitrary-size block cipher". This would allow to map your set of 5-character strings onto itself. Of course, this can't really get too secure, as it has still the limitations of ECB mode: encrypting the same string with the same key always gives the same ciphertext.

Your idea of using a mode with initialization vector helps, but bloats the message size, of course.

Since your effective message is sufficiently smaller than the block size, you could use a kind of "random padding" (similar to how it is used for asymmetric ciphers like RSA). For example, if your actual message is 5 bytes (and always this size, so we don't need to encode the size), you could add 8 random bytes and three zero bytes (as an integrity check), and pass the whole 16-byte-string to AES (as a block cipher, i.e. one-block-ECB).

On the decrypting side, you check that the last three decrypted bytes are zero, and then ignore the random bytes.

Now the ciphertext is different each time a different random value is used, independently of the actual plaintext, making it secure if the cipher is secure. (Of course, you should not use the same key for more than about $2^{32}$ messages.)

The protection against existential forgery is not that high, though, as three check bytes mean only 24 bit protection (in average 4 million tries necessary before a message is accepted). You can make this higher by using a smaller random part and bigger check part (meaning you should use the same key even less often).

If your protocol is serial, you can include a message number instead of a random value and check value, which also helps against replay attacks.


SHA-1 hash where each of the first 16 bytes is even Is it possible for a SHA-1 hash to have the first 16 characters with a character code $c$ where $c \bmod 2 = 0$?

So given the hash, hash[i] % 2 must be 0 for all 16 characters.

An input with the property you are looking for can easily be found by brute force:

#!/usr/bin/python

from hashlib import sha1

def good(s):
    for c in sha1(s).digest():
        if ord(c) & 1:
            return False
    return True

for n in xrange(10**7):
    if good(str(n)):
        print n
        raise SystemExit

To double check the correctness of the result I used this command:

printf 1014746 | sha1sum | grep '^\(.[02468ace]\)*  -$'


Encryption with "constant" initialization vector considered harmful I try to get the full reasoning behind the above statement. First, after reading articles here and at wikipedia i understand that using an IV only once is good practice.

For stream ciphers not doing so will result in compromising security because of

Cipher1 xor Cipher2 = Plain1 xor Plain2

For block ciphers using the same IV will degrade to ECB mode.

But, is there a real attack like with the stream cipher (or does the stream cipher reasoning apply, too)? E.g. if i have two (short) messages, create a single IV, encrypt both using AES and save the three values for later decryption - what is a concrete attack?

A concrete example from a fictious "preferences vault" implementation. Having an xml like

<vault>
    <items>
        <item iv="" name="f2e342435" value="2034b324">
        </item>
                ...
    </items>
</vault>

where iv is the initialization vector for encrypting both name and value properties, would this add any vulnerability in comparison to having two iv's (always assuming AES).

For block ciphers, it depends on which mode of operation you're using — nobody uses just a plain block cipher for anything, at least not unless all their messages are shorter than a single cipher block (typically 8 or 16 bytes).

ECB mode, which just amounts to chopping the message up into blocks and feeding each block through the cipher, does not use an IV.  As you correctly note, it's also insecure: it leaks information about duplicate blocks in the plaintext.
OFB and CTR modes turn the block cipher into a synchronous stream cipher.  Thus, they have the same security issues as other stream ciphers: if the same key+IV combination is used for two messages, an adversary that captures both can take their difference to eliminate the keystream, leaving only the difference of the two plaintexts (which is often enough to recover at least parts of both of them).  It gets even worse if they can capture more than two messages using the same key+IV.
The CBC and CFB modes are somewhat more resilient to simple IV reuse.  As with all other common operating modes, though, using the same key+IV to encrypt two messages sharing a common prefix (of one or more blocks) will reveal the presence and length of that prefix, since the ciphertexts will be identical up to the point where the first plaintext difference occurs.  CFB mode also leaks the difference of the first non-identical plaintext blocks in the two messages.


Cryptocurrency serving as hash breaking? There are many people mining for Bitcoin right this second.[Citation needed]

Bitcoin's proof-of-work mining system is based on a hash function (SHA-256, I believe), and there are ASICs built specifically for mining this.

Would it be possible to engineer a cryptocurrency such that the calculations of the mining process could be used to break hashed passwords? Without the miners knowing?

And, assuming a worldwide mining community approximately equivalent to Bitcoin's and with dedicated hardware for the purpose, would this be a feasible way of breaking hashed passwords?

Maybe

First let's say what you got correct:

ASIC is indeed used to mine, and mining is more or less calculating SHA-256 over and over (password hashing schemes use some things to make it somewhat harder for ASICs, but this won't be problem here - miners will use whats best).
If large-enough mining community formed, breakage of passwords could be eased.

However, there would be some problems that could prevent acceptability of such cryptocurrency:

It won't be possible to make it really without knowledge of miners, or at least some suspicions: To claim that you found block X, you would need to publish what password it was. It would be highly suspicious that some solution would be "Password123" "admin1" etc.
You would need database of passwords to break. Normally, this is done by some kind of mathematical rule. You instead would publish a large database and claim it is random. This again would be suspicious. And if you allowed yourself to add more hashes to database, then it would be suspicious, as you had a way to easily mine any amount of this cryptocurrency for yourself (you can generate password, upload it and then immediately solve it yourself - you can however put that aside when you pay for blocks).

So in the end, it doesn't look that easy, but if people somehow didn't realize these red flags, it should be fairly easy to do (not including trust problems - only one cryptocurrency is widely-accepted so far - bitcoin).
Also, if some password was really strong, whole bitcoin mining processing power won't help you - it just will be far too hard.


Differential Privacy: is the bound for group privacy tight? Suppose mechanism $M$ is $(\epsilon, \delta)$-differentially private. For datasets $x$ and $x''$ that differ by 2 elements, we have
$$
Pr[M(x)=y] \le e^{\epsilon} Pr[M(x')=y] + \delta \le  e^{2\epsilon} Pr[M(x'')=y] + (1+e^\epsilon)\delta
$$
where $x$ and $x'$ are adjacent, $x'$ and $x''$ are adjacent. This bound is the one from group privacy. Is this bound tight? If so, can anyone give me a specific example of the mechanism to illustrate that this bound is tight? I'm thinking of randomized response but seems doesn't achieve the $(2\epsilon, (1+e^\epsilon)\delta))$-indistinguishability for $M(x)$ and $M(x'')$.
Thanks a lot!

Yes, this bound is tight.
The optimal partition selection mechanism introduced in this paper achieves the bound: every step "uses up" all the $(\varepsilon,\delta)$ budget available, and for the particular case of $k=2$, the probability of releasing the partition is exactly $(1+e^\varepsilon)\delta$, while this probability is $0$ for $k=0$. The recurrence relationship gives you a tight bound for any $k$.
(Disclaimer: I'm one of the authors of this paper.)


Negative correlation in image cryptography I am working on an algorithm to encrypt images and I am getting a negative correlation between the encrypted image and the original image. Ideally correlation should be zero but what should I infer from a negative value?

A negative correlation simply implies that your encrypted image resembles the negative of the original image more than one would expect if the two images were completely unrelated.

Of course, the measured correlation between any two random sets of data is rarely if ever exactly zero, even if the values are actually completely independent.  However, if the correlation appears consistently and/or is large enough (in absolute magnitude) to be considered statistically significant, it indicates that your encryption scheme leaks information about the original image, and is therefore not secure.

(Also, note that zero correlation between the original and the encrypted image is not, by itself, sufficient to demonstrate security.  For example, an encryption scheme that simply inverted the colors of every second pixel in the image would achieve very close to a zero correlation for most typical images, but would be trivially easy for anyone to decrypt.)


What are some restrictions when converting Montgomery Curves into Weierstrass Curves? I want to represent a Montgomery Curve (curve25519) in Weierstrass form as a personal exercise.

After doing some math and referencing the conversion equation at http://en.wikipedia.org/wiki/Montgomery_curve, several of my terms contain decimals, which I believe is incorrect. Namely,

(3-A^2) / (3*B^2)

is a decimal, when A = 486662 and B = 1 and doing it directly.

Note that (3-A^2) is negative, so I added the modulus to it to make it positive, which then enables the division by 3 properly as shown here, b

Are there restrictions on which Montgomery curves can be converted to Weierstrass curves?

My comment already gave you the answer; I'm submitting an official answer to give you something to upvote :-)

An elliptic curve is defined within a field; in the case of curve25519, it is defined within the field $GF(2^{255}-19)$; this is a prime field, because $2^{255}-19$ is prime.

So, when we get to the conversion formulas such as $\frac{3 - A^2}{3\cdot B^2}$, this formula is done within the field the curve is defined in.

Because this is a prime field, addition and multiplication can be implemented by addition and multiplication modulo $2^{255}-19$.  However, division is trickier; it's typically done by computing the modular inverse of the divisor.

As for your question:

  Are there restrictions on which Montgomery curves can be converted to Weierstrass curves?

No, there are no restrictions; all Elliptic curves are isomorphic to some curve in Weierstrass form.  The Wikipedia page you gave gives an explicit mapping from a Montogomery curve into Weierstrauss form.

The one glitch is converting the Curve25519 generator, which is defined as $x=9$; they omit the y-coordinate, and hence corresponds to two elliptic curve points (as there are two different solutions on the curve equation with $x=9$).  This translates into two different points on the Weierstrass curve (which share the $x$ coordinate as well); you can either say that the conversion is that translated $x$ coordinate, or arbitrarily pick one of the valid $y$ coordinates.


Security level difference: supersingular vs non-singular elliptic curve In some evaluation of elliptic curve cryptography, it says that for same security level

In supersingular curve over $F_p$ with group of prime order $q$, p=512, q=160 bits

In non-singular curve , p=160, q=160 bits.

How to know such difference?

The reason why to achieve the same security level a supersingular elliptic curve requires to have a greater field size is due to the MOV attack.

In the MOV attack, for a curve $E(\mathbb{F}_p)$ you use a Weil Pairing to move the discrete logarithm from $E(\mathbb{F}_p)$ to $\mathbb{F}_{p^k}$ where $k$ is called the embedding degree of the curve.
The discrete logarithm in multiplicative groups is easier to compute due to Index Calculus methods (e.g. the NFS for logarithms).

In the MOV paper the authors showed the value of $k$ for supersingular curve must be $k\le6$ so you should choose your original field accordingly in order to land in a cryptographically strong $\mathbb{F}_{p^k}$ after the application of the Weil's pairing.

To address the question specific parameters, supersingular curves over fields with characteristic not equal to $2$ or $3$ must have embedding degree $k\leq3$.

Assuming the more conservative option is selected (i.e. $k=3$) then with your parameters $\log(q)=160$, $\log(p)=512$ an attacker applying the MOV attack will need to solve a DL in $\mathbb{F_{p^3}}$, whose order have size $512*3=1536$ bit.

Thus in this settings the curve's generator assumed solving a DL over a $1536$ bit group as complex as solving an ECDLP over $160$ bit group (unless the curve had $k=2$ in which case DL would have been over a $1024$ bit group).

The values of $k$ for general curves are, in general, much larger so that the MOV attack is less efficient than the ECDLP computation (however it is a value that should be checked when generating new curves). SafeCurves have a list of embedding degree of evaluated curves.

Edited to address the edit in the question


Java's SecureRandom & plaintext attack? Java's SecureRandom is meant to be cryptographically secure, and I know part of that means that the output should not be usable to predict further output.
Though, admittedly, my knowledge in the area is limited, and I'd like to test the limits to get an idea of how secure Java's SecureRandom really is.

So let's say I do this: I seed a SecureRandom with a secret long value (8 bytes) and then use it to encrypt 100 bytes of data by generating 100 bytes with the SecureRandom (right after seeding) and adding them to the original 100 bytes. Very silly of me, however, the original 100 bytes are all zeros, and you know this. Could you use some variant of a known-plaintext attack (or anything similar) to break my encryption? That is, could you determine the initial seed or predict the next values?

Okay, I need to specify it a bit more. I'm going to assume - as a worst case scenario - the SecureRandom implementation uses SHA1PRNG (that is SHA-1) as a mixing function. I know that this algorithm is considered to have some flaws, so then my question is whether - in the given circumstance - these flaws would allow for an easy break on the encryption; meaning one could determine the initial seed without great difficulty from the output. Meanwhile -in a better scenario - the mixing function would be SHA-256, and I still wonder if this situation would allow for vulnerabilities with that algorithm as well, other than brute force.

This answer has been updated a lot, again, after being accepted. I now base my analysis on simple functional equivalent source code to the deterministic PRNG used.

The cryptosystem proposed works, in the sense that it allows decryption. The best cryptanalytic method there is to predict further output is enumerating the 64-bit key by brute force. That's in the realm of feasible for a governmental organization: testing a key guess merely requires computing the SHA-1 of the key; then the SHA-1 of that; and comparing to the first 20 octets of known pad. Modern suitable resources are GPUs, FPGAs, or ASICs. I'm told that some commercial GPUs do 2.6G SHA-1 per second. That allows testing like 1.3G keys per second per GPU. On a farm of 1000 such GPUs, an attack is expected to last less than 3 months. I expect that a competent standard-cells ASIC design allows to improve that by a factor like 100 at constant power and cost, disregarding NRE that can be amortized over multiple other projects with similar requirements, such as password search, an industry that siphons untold budgets and power.

On first reading of Java's specification for SecureRandom, I thought that the proposed scheme would not allow decryption by the legitimate key holder, because of the "SecureRandom must produce non-deterministic output" fragment of that specification. However it turns out this is not a promise to a user, but a constraint, implying that "any seed material passed to a SecureRandom object must be unpredictable". My guess is now that the design intend is that the generator is deterministically seedable for conformance testing, and is seeded with true random in normal use, including automatically when not explicitly seeded.

SecureRandom does not by itself define either an algorithm or implementation, it is designed to support various named algorithms and allow access to various crypto-providers (such as HSMs, Smart Cards, or native OS implementations), with a default software-only crypto-provider implemented by an unspecified combination of Java bytecode on top of a JVM and possibly native primitives. As documented, SecureRandom's constructor "traverses the list of registered security Providers, starting with the most preferred Provider. A new SecureRandom object encapsulating the SecureRandomSpi implementation from the first Provider that supports the specified algorithm is returned".

I have experimentally verified that on a default installation of jdk-7u51-windows-x64, new SecureRandom() and SecureRandom.getInstance("SHA1PRNG") are the same deterministic generator when deterministically seeded before having produced any output (and appear non-deterministic whenever they have been used unseeded). The pseudo-random pad used in the question (which first 100 octets are known in the context) are as produced by:

// Produce a pseudo-random pad from a key using "SHA1PRNG" of the default provider,
// (which also is the default SecureRandom algorithm)
private static void orgSHA1PRNG (byte key[], byte pad[]) throws GeneralSecurityException {
    SecureRandom rng = SecureRandom.getInstance("SHA1PRNG"); // or: = new SecureRandom();
    rng.setSeed(key);
    rng.nextBytes(pad);
    }

Based on the source code available here, I wrote a minimal piece of Java code that I verified produces the same output:

// On a default install of jdk-7u51-windows-x64, the following is equivalent to
// orgSHA1PRNG above, with reference only to SHA-1. Distilled from code found at
// http://www.docjar.com/html/api/sun/security/provider/SecureRandom.java.html
private static void eqvSHA1PRNG (byte key[], byte pad[]) throws GeneralSecurityException {
    // initial state is the SHA-1 hash of the key
    byte state[] = MessageDigest.getInstance("SHA").digest(key);
    // while there is output to produce..
    for(int j=0; j<pad.length+19; j += 20) {
        // compute new output as the SHA-1 hash of the current state
        byte hash[] = MessageDigest.getInstance("SHA").digest(state);
        // copy the hash (possibly truncated) to the pad
        for( int i = j+20<pad.length?20:pad.length-j; --i>=0;)
            pad[j+i] = hash[i];
        // The documented INTEND is to perform
        //    state = (state + output + 1) % 2^^160,
        // with an increment of the first octet of state if the whole state is unchanged.
        // This is performed considering variables as little-endian, and with a minor
        // mess in carry propagation, due to the signedness of the  byte  type in Java.
            int c = 1<<8;     // turns into the + 1 of the above formula
            boolean z = true; // true when state is unchanged
            for (int i = 0; i < 20; i++) {
                c = (c >> 8) + state[i] + hash[i];  // partial result; can be negative !
                byte t = (byte)c;                   // truncation to byte
                z &= state[i]==t;                   // z becomes false when state changes
                state[i] = t;
                }
            if (z)          // occurs with low odds
                ++state[0];
        }
    }

Simplified pseudo-code:

compute state = SHA-1(key)
while output is needed

compute hash = SHA-1(state)
use hash as up to 20 additional output octets
state = state $\boxplus$ hash
if the previous operation did not modify state, then

increment the first octet of state.

where $\boxplus$ is some internal law on the set of 20-octet strings, remotely similar to addition $\bmod 2^{160}$ (the neutral element is the all-0xFF octet string, and most importantly a = x $\boxplus$ b always has a unique solution; $\boxplus$ is commutative; I'm uncertain about if $\boxplus$ is associative, but that's of secondary importance). More precisely, $\boxplus$ is addition performed by scanning octets from first to last (that's the reverse of addition within 4-octet words in SHA-1), and with a carry that is initially 1 then either -1, 0, or 1 (because the octets are considered signed two's complement). This is odd, but unlikely to introduce a cryptanalytic weakness.

There are two obvious weaknesses (none of them really exploitable in the context of the question):

the generator enters a cycle with odds $p\approx(b/20)^2\cdot2^{-161}$ after $b\ll2^{84}$ octets;
there is an attack recovering the state (thus allowing prediction of future output) with odds $p$, from $b\ll2^{84}$ octets of output, with expected effort less than $p\cdot2^{161}\cdot20/b$ hashes, and less than $b$ octets of memory.

The attack sketch goes:

from the $b$ octets of output get $\lfloor b/20\rfloor$ values of hash and organize that for quick search
repeat

choose an arbitrary state (an incremental counter works)
if SHA-1(state) is among the hashes

if SHA-1(state $\boxplus$ SHA-1(state)) is among the hashes

stop and output the guess state, which is correct with overwhelming odds.

I'm critical on the rationality of testing that state did not change (except, perhaps, when considering the possibility of malicious reseeding, using means not shown here), for that test and associated action does not significantly decrease the odds of entering a cycle (it only makes it impossible to enter a cycle of length 20, 10, 5, 4, 2, or 1 octets).

Even accounting for the known weaknesses of SHA-1, brute force for keys significantly less than $16$ octets might remain the least inefficient purely cryptanalytic attack for decades, considering $b=100$ in the question's statement. I'm discounting attacks on implementation, like compromise of the software integrity, side channels, and induced faults.

A quick search on SHA1PRNG returned an analysis report of 2009 (in French) hosted by usually serious officials, studying Java SE 6, with mention of substandard cryptographic post-processing and unexplained statistical anomalies in SHA1PRNG of the default Sun provider, reportedly detected using a standard entropy test of 500 MB output; leading to a JAVASEC rule #36 intended to mean: the developer should not use SHA1PRNG of the Sun Provider. I second the substandard cryptographic post-processing, but conjecture that the unexplained statistical anomalies are an artifact of the test method (the other option is that a standard entropy test managed to distinguish SHA-1 from a random function, which is next to unbelievable).


Negative time complexity? Just finishing an investigation into Shor's algorithm, and the following equation,
$$
O\big(\big(\log N\big)^2 \big(\log \log N\big)\big(\log \log \log N\big)\big)
$$
is given for its time complexity. However, this is negative for most small values, becoming 0 at $1\cdot 10^{10}$.
Why is this?

The big O notations describes the complexity when $N$ approaching infinity, it is not a formula giving you exact running time for all $N$.

Roughly, let $f(N)$ be the function for the running time of the algorithm, the big O notation says that there exists $n$ and a constant $c$ such that
 $f(N)<c\cdot (\log N)^2(\log\log N)(\log\log\log N)$ for all $N>n$.


Software implementation of a commutative cipher? I've got an application (detailed below) that calls for the use of a cipher that is commutative.  I've been doing some googling & reading, and there are two algorithms that seem to get mentioned in these discussions--SRA (not RSA) and Pohlig-Hellman exponentiation.  (Supposedly SRA is a variant of RSA?).  I need something strong, so XOR will not serve.

I'd hoped to run across some actual software that implemented one of these guys so I could play around with them & demonstrate a scheme I have in mind, but I have not been able to find any.  It looks to me like these things are not in the source code that comes with Schneier's Applied Cryptography, frx. Can anyone recommend a source for implementations of either SRA or Pohlig-Hellman?

Here's how I'm thinking to use this tech if I can get my hands on it.  I work for a healthcare provider A, which operates in the same geographic area as our colleague/competitor provider B.  We know that we share some patients, but we don't know which, or even how many people we have in common.

We could just swap lists of say, the SSNs of our patients & find out who we share, except that we don't really trust each other to treat this sensitive data w/the care that it's due, and wow would people freak out and hate us if it got out that we were making free w/their SSNs, etc. etc..  So--please take for granted that sending raw SSNs is neither practical nor desirable.

But here's what we maybe can do.  I grab my commutative-cipher software, generate an encryption key, save it off somewhere safe, and produce a file of encrypted SSNs (each SSN encrypted separately with my key).  My colleague at provider B does likewise.  Then we swap encrypted lists, and each encrypt the other guy's encrypted SSNs with our own keys.  Then we swap the doubly-encrypted lists.  Because the cipher is commutative, encrypting with key A first, and then key B should give the same results as encrypting with key B first and then key A.  Which means that any values that are shared on the two doubly-encrypted lists represent the same SSN, and therefore a shared patient.  So we know exactly who we share, without exposing the SSNs of our entire patient list.

To clarify a little, you need "encryption" that is commutative, deterministic (otherwise the commutative ciphertexts won't necessarily match even if the plaintexts do), and has a private encryption function (otherwise given that it is deterministic and the plaintext space is small, an exhaustive search would be possible). For example, Elgamal is commutative but it is also randomized and public key. Encryption is in quotes because, since you never decrypt, you actually just need a trapdoor function with those properties.

Pohlig-Hellman and SRA are suitable.

As far as implementations go, I do not know of any. However Pohlig-Hellman would be easy to implement with just a number theory library (it is just a single modular exponentiation -- you don't need to decrypt in your application). If you have a DSA library that has a function to generate a public key from a secret key, you can use that as the encryption function.

Similarly, SRA is just RSA with two key pairs. If you could call the key generate function of an RSA implementation is such a way as to get $e,d$ if you supply $p,q$, then that would work.

Both of these ciphers are old and were developed before certain attacks were known. For Pohlig-Hellman, you should work in a multiplicative subgroup and this requires encoding the plaintext. SRA could leak the Jacobi symbol of the plaintext like RSA (I think even if $e$ is not known?).

Finally, the application you are implementing is called "private set intersection." There are lots and lots of papers on how to do it, and potentially some implementations of the whole protocol. There are some issues with the way you are implementing it assuming that one of the parties is malicious.

If both parties are honest (only submit true values) and fair (one party learns the result before the other), it seems ok. But there are all sorts of attacks otherwise that could be resolved by using a private set intersection protocol designed for exactly this purpose.


Why is the core ChaCha primitive not good for use in a CRCF? Why create BLAKE? Why is the core ChaCha primitive not good for use in a collision-resistant compression function (crypto hash)? Why go through the trouble to create BLAKE?

What's wrong with using the core ChaCha primitive unaltered in a Merkle–Damgård like construction to construct a collision-resistant compression function/one-way compression function/Cryptographic hash function.

Is there a practical consideration, or is this just number theoretic?

Edit: The following reduces this question without changing it, and summarizes the answer.

Why is the core ChaCha primitive not good for use in a collision-resistant compression function (crypto hash)?

The chacha paper, linked in Lery's answer below, seems to specifically state that compression functions could, indeed, be built on the chacha core primitive. It's on the second to the last page.

  "[...] Modifying constants first is helpful for compression functions built on the [chacha] core."

At this point, it becomes safe to say the first question reduces to an argument about what the words "built on" and "good for use in" means. It's not productive to argue semantics, so discussing it further is moot.

Thus, the whole question reduces down to "Why go through the trouble to create BLAKE?" Lary's answer explains this best, so it was chosen. But I'd like to distill out some parts.

Why make BLAKE? What's wrong with core chacha + Merkle–Damgård?

Pure Merkle–Damgård has flaws. BLAKE uses the HAIFA construction, which fixes  these flaws by adding a salt and a hash count as extra variables/inputs. What's more important (and quite provocative IMHO) is that HAIFA, in fact, shares the same security requirements and proofs from its core primitive as for Merkle–Damgård.

From the HAIFA paper... (Technical Report  CS-2007-15 - 2007)

  The same arguments that are used to prove that the Merkle–Damgård construction retains the collision resistance of the underlying compression function, can be used to prove that HAIFA does so as well.

TL;DR: HAIFA basically just 1ups Merkle–Damgård. (Though, does so in a very important way!)

So then, in a practical sense, BLAKE (original) actually is or at least contains a collision-resistant compression function "built on" the chacha core primitive, in a Merkle–Damgård like construction.

In other words, my first question is flawed.

BLAKE doesn't change the core function of chacha in a qualitative way at all, rather it changes how and what data is input to it. (See SEJPM's answer for a reasoning as to why.)

The only modification to the function of the core was apparently a mistake. BLAKE creators fat-fingered the rotations. This, as explained, is not strictly a requirement. Pure chacha core would work just as well.

I'm answering the following which was asked in the original question:

Why is stock chacha20 not good as a cryptographic hash? Why create BLAKE?
Why not simply apply the one-way compression function concept on raw chacha20, specifically its quarterround() function, unaltered.

TL;DR: Chacha was meant as a stream cipher, it needs a different kind of security guarantees to become a hash function.
The BLAKE designers tweaked it so that it became one, but they also did more than that. They also had some constraints because of the NIST's SHA3 competitions for which they created BLAKE.
Also, if you ever wondered why BLAKE was using a different direction for its rotation (left shifts instead of right shifts), you might want to read all about it below, because it's amazing!
Why create BLAKE?
If you don't want to buy the book on that topic, written by BLAKE's designers, I'll try to explain some things that might help you understand why we needed BLAKE.
First things first, I'll recall that ChaCha itself is a variant of Salsa20, a stream cipher that was already recognized for its simplicity and high speed.
The fact that it is a stream cipher notably means that when you take a message of size $\ell$, you'll get a ciphertext of size $\ell$ out of it, whereas with a hash function you want a fixed size output.
Now, ChaCha consists of a minimal set of basic operations and repeats the same pattern of addition, rotation, and XOR, called "ARX".
The main reason to choose ChaCha over Salsa20, is that while using the same numbers of operations than Salsa20 to invertible update four 32-bit state words, ChaCha does so in a different order and updates each word twice rather than once, hence giving each input word a chance to affect each output word. And it also has other nice properties about which you can read in the ChaCha paper.
Now, BLAKE designers wanted to compete in the NIST competition for SHA3, so they were notably required to:

produce digests of 224, 256, 384 and 512 bits
support maximum message length of at least $2^{64}-1$ bits
process data in a one-pass streaming mode, reading each message block only once

The BLAKE designers also decided they wanted to have the same interface as SHA2, which implied parsing input byte arrays to 32- or 64-bit words in a big-endian way (unlike MD5 for example).
Now, what part of BLAKE is actually coming from ChaCha?
Well, its core, the "G" function, which consists of 16 operations and is directly inspired from the "quarter-round" function used by ChaCha. But as I said, ChaCha is using 32-bit words!
So, they had to modify it in order to be able to support 64-bit words, they had to if they wanted to be able to match the SHA2 interface so that BLAKE can be a drop-in replacement for SHA2.
You might ask why, and the reason is mostly to allow Blake to take full advantage of the 64 arithmetic that is available on today's CPUs in servers and desktop computers, while still having a 32-bit version with Blake-256 that is more suited for older, or smaller devices.
ChaCha on its side has the goal of being a stream cipher, that is simple, and fast. To do so, and still be compatible with older or smaller devices, having 32-bit words makes sense. Plus, with a stream cipher, you want interoperability between platform without having to choose a specific version depending on your architecture to have better performances, whereas, with a hash function, it is customary to have more choice.
The rest of the design of BLAKE is indeed just a straightforward way to convert ChaCha into a secure hash function, but it still is important to do so while using the right methods, and so you could not "just take ChaCha" to have a hash function, since you still need for example to compress your message into a single fixed-size digest.
Why is stock chacha20 not good as a cryptographic hash?
Well, as mentioned above, ChaCha is a stream cipher, which means that it does not compress a message so that you get a fixed size digest, and it also does not care about the same kind of threats and attacks. (For instance, collision resistance is definitively not something that a stream cipher tries to tackle, but it is crucial to have a secure hash function.)
But as said by SEJPM in his answer, ChaCha is featuring a PRF function at its core, which maps onto the 512-bit space, which is a nice building block for many cryptographic algorithms, from stream cipher to hash function.
So, ChaCha being a stream cipher, it is not fit to be used as a cryptographic hash directly as it stands, but its core ideas were used by BLAKE designers in their compression function with fixed-size output digest. Also, the fact that ChaCha was well understood and studied help the crypto-analysis of BLAKE that ensured it had the right security properties.
Notice also that since you want to hash (almost) arbitrary size input, you need a way to extend the domain of your compression function, and BLAKE is using the HAIFA model to achieve "domain extension" and also its goal of being a secure hash function.
Notice that the later also answers your question about "why there seem to be no Merkle–Damgård like constructions". BLAKE avoids Merkle–Damgård because of its many pitfalls and prefers to use a simplified HAIFA construction instead.
Rough idea of how BLAKE works and its differences with ChaCha
Here I'll try to give you a high-level idea of how BLAKE works, which should also help you spot more differences with how Chacha works.
In order to hash a message $M$ with BLAKE-32 (the closest to Chacha):
The message is first padded so that the length of the padded message is a multiple of 512. But it is always padded with at least 66 bits since it allows for the last 64 bits of the padding to be the binary encoded bit length of the (unpadded) message.
The padded message is then split into 512-bit blocks and iteratively fed to the compression function along with the previous hash value, a 64-bit counter counting the bits already hashed, and an optional 128-bit salt.
Before you ask, the previous hash value for the very first block is an initialization vector (IV) that is defined in the BLAKE specification.
Notice that the compression function has a finalization phase, in which you compute the output hash value using its internal state $v_{0 \leq i \leq 15}$ and the salt $s_{0\leq i\leq 3}$ chosen by the user (0 by default):
$$h'_i \leftarrow h_i \oplus s_{i \bmod 4} \oplus v_i \oplus v_{i+8}$$ for $i = 0,\dots , 7$. The eight $h'_i$ are the output of the compression function. It might be interesting to note that this can be seen as a particular case of a Davies-Meyer-like construction. (See the BLAKE paper for more.)
It is also useful to note that the "core" G function of BLAKE is also differing from Chacha because it feeds 2 input words XORed with constants (that are defined in the specification and that were removed in the design of BLAKE2) into its state at each execution of the G function.
And notice also that the rotation (shifts) used in the G function are right ones, whereas Chacha is using left rotation. (But this is actually not changing much and is only due to a typo in one of the early specifications...!?! ^^ Congrats for making it so far, you deserved to know the truth!)
Finally to have a more visual idea of these latest points, here is the G function of BLAKE:
$$\begin{align}
a &\leftarrow a + b + (m_{\sigma_r(2i)} \oplus c_{\sigma_r(2i+1)})\\
d &\leftarrow (d \oplus a) \ggg 16\\
c &\leftarrow c + d\\
b &\leftarrow (b \oplus c) \ggg 12\\
a &\leftarrow a + b + (m_{\sigma_r(2i+1)} \oplus c_{\sigma_r(2i)}) \\
d &\leftarrow (d \oplus a) \ggg 8 \\
c &\leftarrow c + d \\
b &\leftarrow (b \oplus c) \ggg 7
\end{align}$$
compared to the "quarter-round" function used by ChaCha:
$$\begin{align}
a &\leftarrow a + b \\
d &\leftarrow (d \oplus a) \lll 16\\
c &\leftarrow c + d\\
b &\leftarrow (b \oplus c) \lll 12\\
a &\leftarrow a + b \\
d &\leftarrow (d \oplus a) \lll 8 \\
c &\leftarrow c + d \\
b &\leftarrow (b \oplus c) \lll 7
\end{align}$$
If you really want more details about how BLAKE works, the BLAKE paper is actually not too difficult to read.


Why is C_digest defined in PKCS#11? Digesting doesn't require any key and can be performed on the client side. Why does the PKCS#11 token interface standard have a C_digest method? For example, why should I send my data to a PKCS11 HSM whereas I can do this in my client?

What defining the digest as part of the API does is allow the device to be a completely self-contained cryptographic system. This system can then be tested as a unit -- if you did, say, hashes on the client side, you would have to ensure that the hash implementation was secure for each and every new implementation. By putting everything in one module, you can test and secure that module independently of everything else on the system -- you know your PKCS #11 device has a proper implementation, and don't have to bother re-implementing it yourself. That gives you a lot more flexibility as well, as everything you need is in that device (so you don't have to reimplement digesting every time you have a new system, as it's in the device).

FIPS actually requires a similar thing -- all cryptography has to be within a FIPS-certified device, because that outsources all the needed compliance steps to the FIPS device (you only have to check that device for compliance, and can then use it anywhere without worrying about the cryptographic implementation in the rest of the system).


How to calculate the complexity of a meet-in-the-middle attack in terms of the key size k (Use big-O notation) I dont understand this question at all what is it trying to tell me:

  The meet-in-the-middle attack means that two successive encryptions
  using two different k bit keys do not give the security against a
  brute-force attack that you would expect from a 2k bit key.
  Blockquote

(a)

  Consider the situation when using two successive AES encryptions.
  Calculate the complexity of a meet-in-the-middle attack in terms of
  the key size k (Use big-O notation). Assume that a 2-DES attack
  required you to build tables containing the “middle” values. Making
  simple assumptions, what is the size of these two tables? Show your
  working.
  Blockquote

(b)

  In the meet-in-the-middle attack, if we built the tables
  first and then looked for matches, we would have another high
  complexity problem. For each of the table 1 entries, compare with all
  the table 2 entries; this algorithm has complexity of O(22k). Explain
  how the matching could be done while building the tables, resulting in
  the total complexity remaining at O(2k+1).

The meet-in-the-middle attack means that two successive encryptions using two different k bit keys do not give the security against a brute-force attack that you would expect from a 2k bit key.

Consider the case where you take your plaintext, encrypt it once with a $k$-bit key, and then encrypt it a second time with a second $k$-bit key.

You used a total of $2k$ bits of key; however this can be attacked with less effort than by simply trying all possible combinations of the $2k$ bits of key.

Blocks (a) and (b) try to talk about the complexity of how it is done; however they assume that you know the basic technique.  If you don't, well, that's probably what's confusing you (and block (a) talking about AES at one point and DES at another may well add to the confusion).

The basic attack is fairly simple; go through all possible values of the first $k$-bit key, and generate all possible first stage encryptions; go through all possible values of the second $k$-bit key, and decrypt the known ciphertext with that key, generating what had to be input to the second stage.  For the correct guess, the output of the first encryption had to be the input to the second, and so look for a match.  This is known as the 'meet-in-the-middle' attack; where you attack the cipher from both sides (and meet in the middle).


How do the Serpent S-boxes work? Warning: The link in the answer explain the S-Box well, but there is an error in the pseudocode.
$K_i = K_{i-8} \oplus K_{i-5}  \oplus K_{i-3} \oplus K_{i-1} \oplus  0x9e3779b9 \oplus i$;
Instead, it should be :
$K_i = K_{i-8} \oplus K_{i-5}  \oplus K_{i-3} \oplus K_{i-1} \oplus  0x9e3779b9 \oplus (i-8)$;
The loop start from 8, but in the paper, i is worth 0 as the beginning of the loop.

For DES, you take the 4 inner bits as the column to choose from the S-Box, and the two outer bits to choose the row.
However, for Serpent it doesn't make sense to me as the prekeys that are used to choose the row and columns are 32 bit words, and the 8 S-boxes are one dimensional arrays.
Now the paper tells us that the S-boxes are 4 bit permutations, but what does it mean? Would it mean that the two outer bits are used to choose one of the 8 S-box, and the 4 inner (ignoring thus 2 bits in the process) would be used for the columns? However, the paper directly specifies which S-box to use, like so:
${k_0 , k_1 , k_2 , k_3 } := S_3 (w_0 , w_1 , w_2 , w_3)$
I've searched online, but serpent doesn't seem to be as documented as Rijndael or DES.

Serpent uses 8 different 4-bit S-boxes (i.e. each S-box contains 16 elements) a total of 32 times. There are no "rows" or "columns" as it is a one-dimensional array containing a derangement of 16 elements. For each S-box, a 4-bit integer from 0 to 15 is mapped to another 4-bit integer from 0 to 15. When implementing the S-box as an array, the input is used as the index and the contents of the array are what make up the S-box itself. The output is simply the element at the index given by the input.
The 8 different Serpent S-boxes (ignoring the inverse S-boxes) are described by the following table:
\begin{equation}
\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
\text{Input}&\operatorname{S_0}&\operatorname{S_1}&\operatorname{S_2}&\operatorname{S_3}&\operatorname{S_4}&\operatorname{S_5}&\operatorname{S_6}&\operatorname{S_7}\\
\hline
0&3&15&8&0&1&15&7&1\\
1&8&12&6&15&15&5&2&13\\
2&15&2&7&11&8&2&12&15\\
3&1&7&9&8&3&11&5&0\\
4&10&9&3&12&12&4&8&14\\
5&6&0&12&9&0&10&4&8\\
6&5&5&10&6&11&9&6&2\\
7&11&10&15&3&6&12&11&11\\
8&14&1&13&13&2&0&14&7\\
9&13&11&1&1&5&3&9&4\\
10&4&14&14&2&4&14&1&12\\
11&2&8&4&4&10&8&15&10\\
12&7&6&0&10&9&13&13&9\\
13&0&13&11&7&14&6&3&3\\
14&9&3&5&5&7&7&10&5\\
15&12&4&2&14&13&1&0&6\\
\hline
\end{array}
\end{equation}
This means that the integer $9$ (binary $1001$) fed through the 3rd S-box ($\operatorname{S_2}$) would be the element at index 9, which happens to be the integer $1$ (binary $0001$). In other words, $\operatorname{S}_2[9] = 1$. The S-box that is used in any given round is determined by the round number. Round $r$ uses $\operatorname{S}_{r\bmod 8}$. The Serpent authors decided to use 8 different S-boxes instead of 32 because the security benefit did not appear to be worth the added ROM footprint, and fewer than 8 would be insecure for such a small S-box.
Each of the 4-bit S-boxes operate on 4-bit chunks of input, returning 4-bit chunks of output. Each round's substitution step involves 32 parallel applications of the same S-box. This substitution is done 32 times (one time for each round). This is realized by splitting the 128-bit block into four 32-bit words. The first bit of each word is used as input for the first S-box. The second bit of each word is used as input for the second S-box. This continues 32 times. Since there are always four words, each S-box only takes 4-bit inputs. The following is taken from a blog post on an implementation of Serpent which explains how a 4-bit S-box is capable of operating on four 32-bit words (i.e. the 128-bit round state):

The diagram below shows how the s-boxes are implemented in bitslice mode. The 128 bit input block is divided up into 4 x 32 bit words: |w0|w1|w2|w3|. These are then arranged as shown in the diagram. The substitution is then applied by taking 32 slices of 4 bits each and putting then through 32 copies of the s-box in parallel. Bit 0 is the lsb in the 4 bit value.


How does constant-time comparison work? libsodium has a method for comparing two byte sequences in constant time.

Is the idea here to simply avoid early-out if a difference in the data is detected?

When I first heard of such a thing I imagined an operating-system sleep operation to round-up the runtime of the algorithm to some threshold, but this sounds very inefficient.

A common method for constant-time comparison goes

$r←0$
for each bit/byte/word $x_i$ and $y_i$ to compare

$r←r ∨ (x_i⊕y_i)$   where $∨$ stands for bitwise OR and $⊕$ stands for bitwise XOR

all the $x_i$ match the corresponding $y_i$ if and only if $r$ is now $0$

The point is that the duration is independent of the data compared, thus measuring that duration does not reveal anything about the data.

Other methods are possible, like hashing all the $x_i$, and all the $y_i$ (perhaps with the same random prefix), then comparing the result (preferably, using a similar constant time method). This could be less sensitive to other forms of side-channel attacks.


What is the discrete logarithm assumption and why it is not easy with Shank's baby-step/giant-step When I read about the DLP, it seems that the assumption is that it is not generally possible to solve it in polynomial time. But I also read that there are several algorithms in $\mathcal{O}(\sqrt{n})$, for instance, the Shank's baby-step/giant-step so there must be some misunderstanding by me.

What is the assumption?

If I understand the problem correctly, we are given a group with a modulus and a generator of that group. The problem is:

Given an element $x$ of the group, find the number $a$ so that the generator $g$ will generate $x$ by $$x = g^a \bmod q.$$ And the assumption is that we cannot do it for a random or worst instance of the problem in polynomial time, but I must have misunderstood because I read about deterministic algorithms such as Shank's baby-step/giant-step which solve the problem in $\mathcal{O}(\sqrt{|G|})$ which is quite fast isn't it?

Where is my mistake?

When I read about the DLP, it seems that the assumption is that it is not generally possible to solve it in polynomial time.

Actually, whether or not we assume that it is hard depends on the group; there are certainly groups where it is quite easy (for example, in $\mathbb{Z}_q^*$ where $q-1$ is smooth).

  But I also read that there are several algorithms in O(sqrt(n)) for instance the big-step/baby-step so there must be some misunderstanding by me.

That is what you are misunderstanding; when we say "polynomial time", we mean "polynomial in $\log(n)$"; $\sqrt{n}$ is not polynomial in $\log(n)$ (actually, it is exponential), and so that is not a contradiction.

  The problem is: Given an element $x$ of the group, find the number $a$ so that the generator $g$ will generate $x$ by $x = g^a \bmod q$.

Actually, there are a number of generalizations, and they're all sometimes called DLP:

Perhaps we don't require $g$ to be the generator of the entire group; we still insist that $x$ be a member of the subgroup that $g$ generates (there won't be an $a$ otherwise).  This is actually more common than your meaning; where $g$ might generate a prime-sized subgroup.
Perhaps we don't restrict ourselves to groups of the form $\mathbb{Z}_q^*$, but instead have $g$ and $x$ be members of a different group (for example, an elliptic curve group).  Sometimes this is called the ECDLog problem; sometimes, we aren't as specific.

  I read about deterministic algorithms such as Shank's which solve the problem in O(sqrt(|G|) which is quite fast isn't it?

Not if $|G| > 2^{256}$, it's not (and yes, that's the size of the groups we use in practice)


Convert m-Sequence into a de Bruijn Sequence In his paper Alternating Step Generator Controlled by de Bruijn Sequence, C.G. Günther states on page three that

  a de Bruijn sequence (..) can easily be obtained from an m-sequence (maximal length LFSR sequence)

Unfortunately he gives no method for doing this in the paper, and I have been unable to find such a method in my own research. Can anyone clue me in as to what Mr. Günther had in mind there? Is there an easy circuit for converting an m-sequence into a de Bruijn sequence?

A de Bruijn Sequence, as defined in N.G. de Bruijn's A combinatorial problem, Proc. K. Ned. Akad. Wet., vol. 49, pp 758-764, 1946 (with attribution to Ir. K. Posthumus) is

  an ordered cycle of $2^n$ digits 0 or 1, such that the $2^n$ possible ordered sets of $n$ consecutive digits of that cycle are all different.

The example given for $n=3$ is the sequence 00010111, yielding sets 000, 001, 010, 101, 011, 111, 110, 100.

Given that, a de Bruijn Sequence of length $2^n$ is obtained from any m-sequence of length $2^n-1$ (that is, the cyclic output of a LFSR with a primitive polynomial of degree $n$ starting from a non-zero state) by inserting a single 0 in the single subsequence with $n-1$ consecutive 0.

Update per comment: We can implement a circuit that outputs a de Bruijn Sequence of length $2^n$ using $n$ D-type flip-flops connected as for a maximal-length Fibonnaci LFSR with $n$ stages, by adding an additional XOR term equal to the NOR of the outputs of the $n-1$ flip-flops on the feedback's side. In the following drawing (which outputs the example sequence above), the added gates are NOR1 and XOR2.

Note 0: When the number of stages $n$ gets large, the NOR gate with $n-1$ inputs gets annoying; one can trade this for a $\lceil\log_2(n)\rceil$-bit counter with reset, counting the number of consecutive zeroes in the output, giving a $1$ when reaching $n-1$ consecutive zeroes, and that output the additional XOR term.

Note 1: A de Bruijn generator is used in the paper only for the control generator of the ASG, deciding which of the other two are clocked. It would be questionable to also use a de Bruijn generator for any of the other two generators: notice that if the control generator has $c$ bits, a slave generator $x$ bits, and both are de Bruijn, the overall period of the slave's output is $2^{\max(c,x+1)}$, rather than $2^c\cdot(2^x-1)$ when the slave is a maximal-length LFSR.

Note 2: I do not see why the ASG's security would be weakened if the control generator was a maximal-length LFSR rather than a de Bruijn generator, with both slaves maximal-length LFSRs, provided $\gcd(2^{c-1}-1,2^x-1)$ is small [as well as $\gcd(2^x-1,2^y-1)$], where $c$ (resp. $x$, $y$) are the number of bits of the control generator (resp. the slave generator clocked when the control generator outputs $0$, the other slave generator). The original paper hints at another paper (submitted to IEEE Transactions on Information Theory, but I could not locate it) covering the case of maximal-length LFSR as control generator. It also seems to be the case in this article on the ASG, and some of its references.

Late addition: This is also easy in software. Assume $x^\mathtt n+x^\mathtt k+1$ is a primitive trinomial over $GF(2)$ (suitable constants $\mathtt n$ and $\mathtt k$ can be obtained from Jörg Arndt's Complete list of primitive trinomials over GF(2) up to degree 400). If x is an unsigned integer variable at least $\mathtt n$ bits wide, then the C expression
x = ((((x>>k)^x)&1)<<(n-1))|(x>>1);
readily implements a LFSR with period $2^\mathtt n-1$ (when starting from any positive x less than $2^\mathtt n$). We can change this to
x = ((((x>>k)^x^!(x>>1))&1)<<(n-1))|(x>>1);
which implements a NLFSR with period $2^\mathtt n$ (when starting from any non-negative x less than $2^\mathtt n$).


Using non-standard constants for SHA-256 For SHA-256, FIPS 180-4 states the following on the constants:

  These words represent the first thirty-two bits of the fractional parts of the cube roots of the first sixty-four prime numbers.

If one were to change some small number of those constants, say $n \leq 8$, to suitably "random" values, would this significantly weaken the cryptographic strength of SHA-256? The intent is simply to use a "non-standard" version of SHA-256.

Those are "nothing up my sleeve" numbers, their values aren't central to the security of the algorithm. Nevertheless an intent to arbitrarily choose different and thus incompatible values probably means something else you're doing is a bad idea.


What is the "compression function" in Merkle-Damgård? Is the "compression function" in Merkle-Damgård just a collision-resistant, one-way hash function but one that operates only on fixed size inputs?

If so, is MD just a way to extend it to work on arbitrary length strings?

A compression function takes two fixed size inputs: a chaining value and a message and returns a fixed size value. So it's essentially a hash function with fixed input size.

Merkle-Damgård is a domain extender, which turns that compression function into a hash which supports arbitrarily long messages.

MD uses the output of the compression of one block as the chaining value when hashing the next block. It also describes how to pad the message so it consists of complete blocks.


Why is the public/private key length used in libsodium so much shorter than needed for RSA Reading the libsodium source I see that is uses a key length of 32 bytes (256 bit) for private/public key encryption.

For RSA private/public key encryption a key length of 2048 (or 4095) bit is suggested.
Why is the key length in libsodium so much shorter? Is the used algorithm so much more "efficient"? Or is there something I am missing?

It's not the algorithm that's more "efficient" (that's just a welcome side-effect) but the security level.

Security levels are usually given in bits; to say that a cipher has 80 bits of security means that we assume it takes roughly $2^{80}$ effort to break it, for some definitions of "effort" and "break".

For RSA, the main problem is factoring large numbers. Factoring algorithms are a lot better than brute force - factoring a $n$-bit RSA modulus takes a lot less than $2^n$ operations. Based on the speed of current factoring algorithms, the latest guess (according to ENISA) is that for 80 bit security your $N$ should have around 1024 bits length and for 128-bit security you need a 3072 bit $N$.

For libsodium, the main problem is taking discrete logarithms over a particular elliptic curve group of order $2^{255}-19$. With the best-known algorithms today, taking a discrete log over such a group (where the elements have about 256 bits length) would take around $2^{128}$ operations, hence you get 128 bit security with a lot smaller elements.


Combined scheme security proof Let CS be a combined scheme of $n$ public key subschemes.
CS is composed of two algorithms Setup and KeyGen, that all the subschemes share, plus all the other algorithms of each subscheme.
Suppose that each one of the subschemes is individually secure in the Random Oracle Model (ROM).
I want to prove that CS is secure, with the following definition: CS is secure if all its subschemes are jointly secure, meaning that each subscheme is secure in the presence of the others.
$Proof$. Suppose an adversary A is able to break the security of subscheme $i \in n$ in the presence of the others.
We can construct an adversary B that simulates subscheme $j \neq i \in n$ by programming random oracles, in a game that is indistinguishable from the real experiment.
B will then use the attack of A to break the standalone security of subscheme $i$, which we assumed to be secure. We prove, by contradiction, that CS is secure.
Does this make sense? If not, how can I prove that CS is secure?

No, it's not so simple. In particular, you have to be much more precise about what do you mean by combine.
if you want a good example about how to combine insecure things could become secure you can read :
Let's consider the following one-time-signature scheme $\Sigma_1, \Sigma_2$ both which are equal to
https://eprint.iacr.org/2010/446.pdf . with message space $\{0, 1\}^4$.
Remark that these two schemes are proven secure (the fact they are the same is not relevant in the hypothesis you made).
Now let's consider the Signature scheme $\Sigma_3$ over $\{0, 1\}^8$, which is the concatenation of $\Sigma_1$ and $\Sigma_2$. i.e :
$\Sigma_3.\texttt{KeyGen} = \Sigma_1.\texttt{KeyGen}$, and $\Sigma_3.\texttt{Sign} ( sk, m_1 || m_2) =\Sigma_1.\texttt{Sign} (sk, m_1)||\Sigma_2.\texttt{Sign} (sk, m_2)$. $\Sigma_3.\texttt{Verify} ( vk, \sigma_1 || \sigma_2) =\Sigma_1.\texttt{Verify} (vk, \sigma_1)\wedge\Sigma_2.\texttt{Verify} (vk, \sigma_2)$.
Then, if you obtain the signature of $00001111$, you can sign every message in $\{0, 1\}^8$ which contradicts the one-time-unforgeability.QED
To "combine schemes" people are using universable-composability :
https://en.wikipedia.org/wiki/Universal_composability
What is universal composability guaranteeing, specifically? Where does it apply, and where does it not?
But :
1)It's not enough for your schemes to be secure, they have to be UC-secure.
2)You have to be sure your combination is captured by the formalism of UC.
To conclude, it's a little bit like cooking. It's not because two meals are good separately, that combining both would create a good meal.
About the error in your reasoning " Suppose an adversary A is able to break the security of CS by breaking the security of subscheme", you don't have to suppose how the adversary breaks your scheme, when you are doing a security proof.


Does TLS use RC4-drop[n]? According to many sources, the first few (n) bytes of the RC4 keystream are strongly biased, and therefore should be discarded before using the keystream to encrypt anything; this precaution is commonly called RC4-drop-n.

There are variants of RC4 available in SSH that do exactly that (arcfour128 and arcfour256).

I've not been able to find any hint on whether the SSL/TLS specifications take that into account. The RFC don't include any specification of the RC4 algorithm itself, just a reference to a source that is not available online.

So are they using RC4-drop-n, and if so, what is their value for n?

Well, no, there's no defined TLS ciphersuite that does the RC4 algorithm with a discard of the original stream.

I'm not a designer of TLS, nor am I a member of the IETF working group that controls it; I suspect that they'd prefer for people to transition to ciphersuites that use AES (or some other newer cipher), and so there's little incentive for them to add variant RC4 ciphersuites.

As for the problems that the know biases that the start of the RC4 stream can cause, well, those biases actually come in two flavors:

There are known biases in the keystream bytes themselves; for example, the second byte of the keystream is 0 with probability 1/128 (rather than the expected 1/256).  What this means is if you have a few thousand TLS sessions keyed with RC4, and you know that their plaintexts have the first few bytes in common, you might be able to deduce the values of the second plaintext byte; with more keystreams, you might be able to deduce the values of the first and third plaintext bytes.  Obviously, this is a security failure, and this may be of real concern if (for example) you're sending a password through the TLS session as the very first thing.
There are known correlations between the keystream bytes and the RC4 key itself.  These correlations aren't strong, and so you'd need thousands of keystreams from related keys to get much information about the key.  This is exactly the problem that WEP ran into; however, with TLS, they derive the RC4 key from a real key derivation function; that means that there are no known corrections between the keys from different connections, and so this observation is of no use.

The bottom line: if the first few bytes of the TLS stream are high-value, you probably shouldn't be using an RC4 ciphersuite.


In CBC mode if 2 cipher blocks are same then is CBC still secure? I was going through this question Why is it said that if we have a duplicate ciphertext block it can leak our information? and I was just wondering

if there is a $P_i \oplus P_j= C_{i−1}\oplus C_{j−1}$ relationship, is CBC still secure?
How does this equality lead to information leak?

if there is a $P_i \oplus P_j= C_{i−1}\oplus C_{j−1}$ relationship, is CBC still secure?

As commented by SqueamishOssifrage standard collision of $2^{64}$ blocks for a 128-bit block cipher is not a hard limit. We want a negligible success for the adversaries. With $q$ queries ( encryptions) the advantage of the adversary must be negligible like $2^{-32}$ or $2^{-64}$.

To achieve this we need

$q^2/2^{128} = 1/2^{64}$ that is $q=2^{32}$, or
$q^2/2^{128} = 1/2^{32}$ that is $q=2^{48}$

Therefore you should not encrypt more than $2^{32}$ or $2^{48}$ block depending on the advantage settings of the adversary.

The CBC mode has more problems than this;

The IV must be unpredictable.
The padding oracle attacks on servers.
The BEAST and Lucky13 attacks on TLS only.

And, therefore CBC mode is removed from TLS 1.3. CBC mode is archaic. Today, you should use Authenticated Encryption as AES-GCM or ChaCha20-Poly1305.

  How does this equality lead to information leak?

You have a relation $P_{i}\oplus P_j=C_{i-1}\oplus C_{j-1}$ in which you know
$C_{i-1} \text{ and } C_{j-1}$ then you know the $\oplus$ difference of the two plaintext. In AES, you will have at most 128-bit to apply crib-dragging attack like in OPT. If you know one of the plaintext you know the other.


Elligator-2 against curves over Fq, q mod 4 = 3 It appears that the conditions for applicability of Elligator-2 against many of the SaveCurves curves, where $q \mod 4 = 3$ will inevitably poke a hole in the bit-string set over $(0, 1, .. (q-1)/2)$.

There are two conditions for use of the decoding of a bit string to a point on the curve: $(1 + u \cdot r^2) \neq 0$ and $A^2 \cdot ur^2 \neq B(1 + ur^2)^2$, where $r$ is the numeric equivalent of the bit string, $A,B$ come from curve equation: $y^2 = x^3 + Ax^2 + B \cdot x$, and $u$ is non-square over the field $F_q$.

And when $q \mod 4 = 3$, these conditions will be violated for some valid bit string representation(s) in the set $(0, 1, ... (q-1)/2)$.

Conversely, when $q \mod 4 = 1$, it can be shown that there are no holes in the mapping from bit strings to curve points, and all valid bit strings in the set $(0, 1, ... (q-1)/2)$ map to curve points.

Hence, it becomes clear to me that the intent of Elligator mappings was never to allow arbitrary bit strings to map to curve points, but rather to support a compressed encoding for selected random curve points to bit strings that mimic uniformly random bit strings. The effect is near full coverage of the bit space, but not totally. And it can be shown that Decode(Encode(pt)) = pt. It cannot always hold true for the inverse case: Encode(Decode(bits)) = bits, when $q \mod 4 = 3$, which is the case of many, or most, of the SafeCurves.

The stated purpose of such obfuscation was to avoid censorship from unfriendly authorities who could otherwise spot the use of EC points, even compressed representations of points, during transactions such as ECDH key exchange or ElGamal encryption.

So… the question is:

If the authorities have the wherewithal to spot the use of EC points, or compressed representations of points, then why would one expect that the authorities could not also detect the Elligator obfuscations? They have access to the Elligator equations just as we do. And they could run the decodings for themselves to see if a curve is being referenced.

Most probably, the elligator (hiding in here: Elligator: Elliptic-curve points indistinguishable from uniform random strings – PDF) will jump onto the attackers and bite them, so that they will not risk any further attack.

As an additional security, as described in section 5.1 of the paper, the definition of Elligator 2 is parametrized with a non-square element $u\in \mathbb{F}_q$. So if I understand this correctly, an attacker will not know this parameter $u$ and will thus not be able to decode and encode points of the curve. All the attacker can do is observe a uniformly distributed sequence of bits.


What are preimage resistance and collision resistance, and how can the lack thereof be exploited? What is "preimage resistance", and how can the lack thereof be exploited?
How is this different from collision resistance, and are there any known preimage attacks that would be considered feasible?

Preimage resistance is about the most basic property of a hash function which can be thought. It means:

  For a given $h$ in the output space of the hash function, it is hard to find any message $x$  with $H(x) = h$.

(Note that the it is hard here and in the next definitions is not formally defined, but can be formalized by looking at families of hash functions with a security parameter $n$ (often the hash output size), and saying »hard = there is no polynomial $P$ so this can be done in time $P(n)$ for all functions of the family«. For practical uses, we are often only looking at a single hash function, and are content with »hard = takes more time/costs than any hypothetical attacker can invest«, preferably with some estimation of the work to be done.)

A function with this property is also called one-way function (though this term is also used for non-hash functions with this property, like asymmetric encryption primitives).

A related property is the second preimage resistance:

  For a given message $x_1$ it is hard to find a second message $x_2 \neq x_1$ with $H(x_1) = H(x_2)$.

A function without preimage resistance is usually also not second preimage resistant: Given a message $x_1$, calculate $h := H(x_1)$ and then get a preimage $x_2$ from $h$, then we usually have $x_1 \neq x_2$ and $H(x_1) = H(x_2)$. (The exception to the "usually" would be when the function is (for the space of interesting messages) essentially injective, and the preimage finder would always return the only interesting preimage. Such a function would be second-preimage and collision resistant, but still a quite bad hash function. As normally the space of interesting messages is much larger than the hash space, this doesn't arise in practice.)

Collision resistance is an even harder property, which we still want for most usages of hash functions:

  It is hard to find a pair of messages $x_1 \neq x_2$ with $H(x_1) = H(x_2)$.

Of course, from a (second) preimage attack we also get a collision attack. The other direction doesn't work as easily, though some collision attacks on broken hash functions seem to be extensible to be almost as useful as second preimage attacks (i.e. we find collisions where most parts of the message can be arbitrarily fixed by the attacker).

Also, there is the generic birthday attack on hash functions (which even works for random oracles), which needs $O(\sqrt N)$ tries to have a good probability to hit a duplicate, where $N$ is the size of the output space of the function, where a similar generic brute-force attack on the second-preimage and preimage resistance needs about $O(N)$ queries (which is not feasible for the output sizes of all hash functions used in practice).

I know of no practical preimage attack for the usual hash functions (please add them in other answers, or as comments), while for example for MD5 the collision-resistance is about totally broken, and SHA-1 is starting to show cracks (in 2017, a research team from Google produced two colliding documents).

How can one exploit the lack? This strongly depends  on the use of the hash function in a higher-level protocol (or algorithm build on top of it). In some protocols only the other properties are used directly, but as said, missing preimage  resistance always also leads to missing second-preimage and collision resistance. For example, in signature schemes we usually hash the message first, and a (second) preimage attack allows to create a second message with the same hash as the first one, i.e. where the same signature fits.

An example where the preimage resistance itself is needed is the hashing of a password, or usually a password together with a salt known to the attacker. (Actually here the message space is often small that searching it becomes feasible to brute-force search it with a common fast hash function, which is why one uses slow hash functions for password hashing.)


Combining a block cipher with a (pseudo) OTP One of the drawbacks of OTP is that it can require an inconveniently long key. Besides that, it doesn’t provide data authentication. Therefore, I have been working on an algorithm idea, which I hope to be more powerful and efficient than OTP:

Encrypt plaintext with a block cipher (something with strong avalanche effect and strong pseudo random output.)
Encrypt a random part of the ciphertext with a random pad which has a random length.

I hope my idea to have the following advantages over OTP:

it requires a short key consisting of three parts: one for the block-cipher, one that tells which part of the OTP to use, and the OTP itself. It's extremely small when compared to the key length of an actual OTP, but I think it is worth the burden.
It provides data authentication (due to the usage of a block-cipher).

So, the idea is built on the fact that each and every ciphertext bit is required to decrypt, or even break, a block cipher encryption. With some unknown part locked away with OTP, it will be impossible to obtain each tiny bit of the block-cipher-text, without the key.

Besides that, I think additional security may come from the fact that the part that was encrypted with OTP can not be recognised, because the block cipher output is (better: has to be) pseudo random. Bruteforce seems to be out of reach, as there are more possible chances than OTP (that's because the attacker doesn't know where the OTP was used).

TL;DR

All in all, you could say I have this idea of combining a block cipher with a (pseudo) OTP, trying to gain security and data authentication from that combination. Is there anything that seems obviously wrong with that? Some crucial aspect I may be missing? Are there any specific security issues?

There's quite a few things wrong with this. For starters, a block cipher does not imply authentication. Common block cipher modes such as CTR, CBC, and (god forbid) ECB provide nothing but pure encryption. If you want authentication, look into the GCM block cipher. AES-GCM is possibly the better way to go here.

You state that it is built on the idea that every bit is important when deciphering the data, but this is simply not true. It is difficult (to my knowledge) to have a block cipher rely on every bit of the ciphertext for decryption to be successful. The best thing you can get is having a block cipher rely on every previous bit, meaning you can decrypt the first half of the data just fine while ignoring the second half.

If you have a working OTP, why are you bothering with a block cipher? Just digitally sign it or use a MAC and it will be authenticated. Other than that, an OTP provides perfect secrecy. (Don't be fooled, this is for a perfect OTP, which is virtually impossible to do correctly)

If you are dead set on your OTP & block cipher combo, then I suggest using AES in GCM mode as your block cipher, followed by a newly generated OTP (or a removed section of an existing OTP generated for use in encryption).

However, AES-GCM alone will do what you are looking for without the need of a OTP. And considering how difficult it is to pull off using a real OTP, it's probably more secure just sticking with AES.


Encrypted files in an encrypted partition or folder Recently I started wondering about multiple encryption and found pages upon pages of posts and debates about the security of cascades.

Now, don’t worry – I'm not looking for someone to discuss a homebrew cascade encryption scheme. What I do wonder about is the dangers of multiple layers of encryption.

I keep most of my sensitive files on a LUKS encrypted USB stick – and most of the files are encrypted themselves. There are AES encrypted password wallets, password protected LibreOffice documents (using AES if I have understood the documentation correctly) and lately I have been developing a growing folder of Camellia encrypted files (thanks to a colleague that discovered that GPG now included the cipher).

In short: does storing these encrypted files in an encrypted partition/folder create the same potential weaknesses as cascade encryption? If not, what about encrypting a .tar of encrypted documents?

Pardon my ignorance, and thank you in advance.

In short: does storing these encrypted files in an encrypted partition/folder create the same potential weaknesses as cascade encryption? If not, what of encrypting a .tar of encrypted documents?

An encrypted file inside an encrypted container is a cascade of ciphers, almost by definition.

Is that a problem? Not really. A cascade of ciphers shouldn't be weaker than a single layer of encryption, unless something is wrong – e.g. the keys are not independent.

Concerns about cascades are mostly theoretical – I wouldn't expect the cascade to ever be weaker when you have two different ciphers. There is no easy way to prove that for real world ciphers, however, and there's always the risk of sidechannel attacks and bugs, so it isn't something to recommend as a way to strengthen a system.

In your case it's still the best thing to do, since you don't want all those files to be visible decrypted when the filesystem is mounted.


Encoding Public Keys We would like to encode ECDSA Public Key specifically keys generated using the ed25519 for storage .

What is the best and less error prone method , for now we think about using Hex strings or Base64 are there other encoding schemes that can be used ?

Sure, there are many ways. For instance, if you need to enter key manually, you may even prefer to split text representation into groups of 4 or more characters.

But I'd suggest you choose between SSH2 (RFC 4716) and OpenSSH format. Both use Base64 for key representation. Both have an advantage that they are supported by standard tools like ssh-keygen.

If you have multiple keys and want to more reliably distinguish them, I'd suggest SSH2 (RFC 4716), because it provides slightly better possibilities to comment.


What is the random tape? I am reading the paper "Toward plaintext-aware public-key encryption without random oracles" by Bellare and Palacio. So I can't understand what is the tape and random tape?

Tape is a basic concept from Turing machines.

The random tape is the tape with random bits on it.


Multiple passwords per key with any allowing decryption How to get secret key based on multiple passwords?
e.d we have cipher encrypted by combination of passwords "qwe" and "asd", and our purpose to decode the cipher using any of passwords above separately?

Thanks

You can do this by generating a (random) encryption key for the data and then encrypting that key separately with each of the passwords, using some password-based encryption.

To decrypt the user can use any of the passwords to decrypt the encryption key, then use that to decrypt the actual data. If the password-based encryption used is authenticated encryption, the decrypter can decrypt each of the encrypted keys and use the one where the authentication checks out.


Generating a small EdDSA curve I have an application that would benefit from very small (e.g., 16-20 byte) EdDSA keys and small signatures. It's an application where the goal is more to deter DOS attacks than "hard" security, so having the signature be attackable by someone with a lot of resources is not a huge problem. (Full Ed25519 or similar are used for the real security parts of the system.)
How would one go about generating such a curve? Or is this an extremely nontrivial thing to do? I can find some sample code for general EdDSA but no curves other than 25519 and 448. This makes sense since small curves wouldn't have many use cases, but I have one.
Right now, I have sample code using traditional ECDSA with the Brainpool P-160t curve. It works, but I'm wondering if an Edwards curve would be faster and would offer better security with an even smaller key and signature size.

After more Googling I found a paper called "A note on high-security
general-purpose elliptic curves" which contains some "legacy strength" Edwards curves that might work. Thought I'd self-answer in case anyone else ever needs something like this.


Is it safe to reuse a ECDSA nonce for two signatures if the public keys are different? We denote the s value of an ECDSA signature $(r, s)$ on a message $m$ as:
$s=\frac{H(m)+xr}{k}$

Assume two ECDSA signatures sharing the same nonce $(r, s_1) , (r, s_2)$ on two messages $m_1, m_2$, that verify under two pubkeys $x_1G, x_2G$.

If the two public keys are equal then the secret keys should be equal $x_1 = x_2$ and we can easily recover the $k$ using the standard attack on nonce reuse. Once we know $k$ we can recover the secret key.

$\frac{H(m_1)-H(m_2)}{(s_1 - s_2)} =\frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)+x_1r - x_2r}$

$x_1 = x_2 \rightarrow x_1r - x_2r = 0$

$\frac{H(m_1)-H(m_2)}{(s_1 - s_2)} =\frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)} = k$

My question is can this attack be made to work if the secret keys are not equal i.e. $x_1 \ne x_2$:

$\frac{H(m_1)-H(m_2)}{(s_1 - s_2)} =\frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)+x_1r - x_2r} = \frac{k(H(m_1)-H(m_2))}{H(m_1)-H(m_2)+ (x_1 - x_2)r}$

If you know either $x_1 - x2$ or $\frac{x_1}{x_2}$  you should be able to compute $k$ as long as $s_1 \ne s_2$.

You can calculate $x_1 - x_2 = \frac{H(m_2) - H(m_1)}{r}$ in case where $s_1 - s_2 = 0$. However this case seems to reduce to the hardness of ECDSA since anyone can compute the pubkey for a new message $m_2$ that verifies under first signature $(s, r)$ using public key recovery.

If $s_1 \ne s_2$ you can compute $\frac{x_1 - x_2}{k}$ which allows you to convert $s_1$ into $s_2$ and vice versa.

Suppose you have two message signature pairs and following values are then public i.e. known to you -

The public keys: $Q_1 (= x_1G)$, $Q_2 (= x_2G)$
The messages and their hashes: $m_1$, $m_2$, $H(m_1)$, $H(m_2)$
The signatures: $(r_1, s_1)$, ($r_2, s_2$)

The following are unknown -

The private keys: $x_1$, $x_2$
The nonce: $k$

The following relations are known as well -

$s_1 = k^{-1}(H(m_1) + r_1x_1)$
$s_2 = k^{-1}(H(m_2) + r_2x_2)$

Note that we have two equations in three unknowns. In order to solve these we'll need to eliminate at least one unknown so that we can write one equation in terms of only one unknown and substitute that into the other equation (resulting in an equation with one unknown which can be solved via basic algebra).

The trick employed when $k$ is used with the same $x$ (i.e. $x_1 = x_2$) is that it eliminate two unknowns ($x_1$ and $x_2$) which yields an equation that is easily solved.

So how do we approach this when $x_1 \ne x_2$? The only way I see is to try to divide $s_1$ by $s_2$ to eliminate $k^{-1}$. Eliminating $x_1$ or $x_2$ seems like it would require index calculus, and that would mean solving ECDLP, which would violate the security assumptions ECDSA is predicated on.

So let's see what $\frac{s_1}{s_2}$ yields -

$$\frac{s_1}{s_2} = \frac{k^{-1}(H(m_1) + r_1x_1)}{k^{-1}(H(m_2) + r_2x_2)}$$
$$\frac{s_1}{s_2} = \frac{H(m_1) + r_1x_1}{H(m_2) + r_2x_2}$$
$$\frac{s_1(H(m_2) + r_2x_2)}{s_2} = H(m_1) + r_1x_1$$
$$\frac{s_1(H(m_2) + r_2x_2) - s_2H(m_1)}{s_2}  = r_1x_1$$
$$\frac{s_1(H(m_2) + r_2x_2) - s_2H(m_1)}{r_1s_2} = x_1$$

Note that we can now remove $x_1$ from the equation defining $s_1$ and we are left with a system of two equations in two variables, which can be solved via linear algebra as long as they are not linearly dependent.

(From here on I'll be using $h_n = H(m_n)$ for the sake of brevity)

$$s_1 = k^{-1}(h_1 + r_1\frac{s_1(h_2 + r_2x_2) - s_2h_1}{r_1s_2})$$
$$k = s_1^{-1}(h_1 + \frac{s_1(h_2 + r_2x_2) - s_2h_1}{s_2})$$

Then doing some more substitution -

$$s_2 = k^{-1}(h_2 + r_2x_2)$$
$$k = s_2^{-1}(h_2 + r_2x_2)$$
$$s_1^{-1}(h_1 + \frac{s_1(h_2 + r_2x_2) - s_2h_1}{s_2}) = s_2^{-1}(h_2 + r_2x_2)$$
$$s_2(h_1 + \frac{s_1(h_2 + r_2x_2) - s_2h_1}{s_2}) = s_1(h_2 + r_2x_2)$$
$$s_2(\frac{h_1s_2 + s_1(h_2 + r_2x_2) - s_2h_1}{s_2}) = s_1(h_2 + r_2x_2)$$
$$(h_1s_2 + s_1(h_2 + r_2x_2) - s_2h_1) = s_1(h_2 + r_2x_2)$$
$$s_1(h_2 + r_2x_2) = s_1(h_2 + r_2x_2)$$

So we're left with a tautology... why? Because substituting for $x_1$ into the first equation essentially left us with two instances of the same equation, just with some extra terms and terms on different sides of the equation. This means we can't solve the system. Or more precisely, that the system we have has infinitely many solutions. A simple way to see this is to consider a simpler system -

$$x = 2y$$
$$2x = 4y$$

You could substitute for $x$ in the second equation but it won't do you any good.

In conclusion, it would appear that nonce reuse with different key pairs does not allow recovery of any secret material. While far from a full or rigorous proof the above should convince you that it at least does not fall victim to an attack that uses the same approach as the nonce reused with the same key setting. In any case, if you have the choice I would advise to avoid this scenario, there are plenty of good ways to generate nonces out there. RFC 6979 is a good place to start.


Is it possible to encrypt a message's destination as well as its content? I have imagined a way to break through any kind of censorship but since I don't have enough professional knowledge of cryptography I don't know whether it is feasible or not.

If there is a method that can only enables the recipient to know this message is for him, and when others catch this message they don't even know who will receive that, then no one can block a certain site unless he can decrypt it.

I hope some professionals can respond to this question and tell me if this is possible.

Any peer to peer mesh network would be sufficient.  If peers pass messages on to other peers then no peer can no for certain which peer a message is intended for.  It would be possible to determine (with some degree of confidence) the source of the message.

The real difficulty is handling all the other problems.  How do you deal with malicious nodes, denial of service attacks, and who pays for the network as peers are anonymous.  That is just the tip of the iceberg.

As a real world example the Bitcoin network uses similar system for connecting peers and passing messages.  Transactions are simply messages shared peer to peer in an adhoc fashion (your node tells all your peers who tells all their peers who tells are their peer .... and the recipient is one of them).  Bitcoin solves a lot of those "bad node" problems because the messages (transactions) have a cost in term of fees taken out of the transaction.  They are low but they do prevent things like some attacker just creating a bunch of nodes and telling them to make a trillion messages to cripple the network.


Calculating cycles per byte Cycles per byte seems to be a critical concern in designing and choosing stream ciphers. For example, from Wikipedia, RC4 has 7 cycles/byte on original Pentium chips.

How is this calculated? Do they just time the encryption of multiple megabytes and then divide by the CPU's clock speed? Do they look at the assembly code and lookup cycle per instruction in some table, figuring in pipelining, branch prediction, etc.?

They measure it.

Once upon a time, CPUs were simple enough that you really code compute the amount of time for a stretch of code by looking up the clocks per instruction in the manual, add them all together, and that'd be the total time.

However, CPU manufacturers have added more and more optimizations and parallelism; this makes the CPUs run faster (for example; using memory caches, executing instructions in a pipeline, executing instructions out of order), however it becomes increasingly difficult for someone to look at some code and generate an estimate.

So, instead of trying to deal with the complexity, we just measure it.