Is it possible to unscramble a scrambled ed25519 SSH key? Let's say I generate an ed25519 SSH key with ssh-keygen -t ed25519. Then I take the private key file and randomly scramble the order of base64 encoded characters. Is it practically feasible to recover the original key from this scrambled file?

Is it possible to unscramble a scrambled ed25519 ssh key?

I think you confuse the encryption with the scrambling. Scambling doesn't require a key and it may require a large amount of memory even for the owner to unscramble it if it is a true permutation. Yes, scrambling is a permutation.
Assume that there are $n$ elements that you want to scramble then there are $n!$ permutation if we consider they are all distinct. To store the permutation one needs $n! \times n \times x$ bits where $x$ is the number of bits to represents the elements. For generic cases the repeating is not necessary, so live with this huge number.
We can find the number of base64 characters for $m$ bits with the formula $\lceil(m / 3) \cdot 4 \rceil$. Place the length of the PEM file or just the private key 256 bits that is 32-byte then we have $\lceil 128/3 \rceil = 43$ base64 character for the private key. That will require $43! \times 43 \times 64$ bit to store. This makes approximately $2^{186.7}$ bits, impossible!
This is why we use block ciphers to encrypt and we call a block cipher a family of permutations. Those are expected to select a random permutation from all possible permutations with a key. Even the total number of the permutations of a 128-bit block cipher is tiny compared to all possible permutations $(2^{128})!$. We can see this with the help of Stirling's formula
$$2^{b}! \approx \sqrt{2\pi 2^{b}} \bigl(2^{b}/e\bigr)^{2^{b}}.$$
$$2^{128}! \approx \sqrt{2\pi 2^{128}} \bigl(2^{128}/e\bigr)^{2^{128}} \!=  \sqrt{2\pi 2^{128}} e^{-2^{128}} \bigl(2^{128}\bigr)^{2^{128}} \ggg 2^{128}$$
So, as long as you are not playing a game with a friend ( like CTFs), then secure scrambling has no practicality.

Then i take the private key file and randomly scramble the order of base64 encoded characters. Is it practically feasible to recover the original key from this scrambled file?

The source you linked is using a passphrase for the encryption of the contents of the PEM file - that is not scrambling -. This passphrase is hashed with SHA-1 (old version uses MD5) to derive a key and then the contents of the PEM file is encrypted with AES-128 in CBC mode with this key.
AES-CBC is CPA secure and to break it you need to search $2^{127}$ keys on average.
The common attack is not the key, the user's bad passwords. John the Ripper password cracker and the hashcat are ways to break it. There are currently  613M pwned passwords to easily test! They are already in SHA-1 format as ssh uses SHA-1 to derive the key.
The usual advice to mitigate this is using the diceware based passwords to have passwords with good strength. Or, see XKCD 936.


Is encrypting multiple message with same key and iv secure for this case? AES256, CBC

IV is sha512 of key.

Ek[random padding | message | random padding]

How much information would be leaked from the use of the same IV & key in this way, assuming the adversary has complete access to the system, design, iv, and all information, the AES Object itself, etc etc, except the key?

If the initial "random padding" is (at least) 16 bytes, this is effectively CBC mode with a random IV.

That's because the initial block of the ciphertext is, with your scheme:

$$E_k( \text{IV} \oplus \text{Random Padding} )$$

which is equidistributed among all $2^{128}$ possible values (assuming Random Padding is equidistributed among all $2^{128}$ possible values independent of the IV).

The rest of the ciphertext is effectively the CBC mode encryption of the rest of the plaintext, with the above equidistributed value as the IV


Is this how padding can work? So for block ciphers you need a fixed size block.

If the plaintext length is not a multiple of the block length then you need to pad it.

One way you could do this is that for the last block you just pad the blocks with 0s or some random characters except for the last character of the last block which represents the number of characters padded.

Of course the problem is what happens when the plaintext is a multiple of the block length (i.e. fits exactly). In this case you just add a dummy block of 0s or 1s. Then when you decrypt you know that if you encounter such a dummy block then the previous block has no padding.

You normally want to use a fully invertible padding scheme, i.e. a padding scheme with an associated unpadding scheme such that $unpad(pad(X)) = X$ for every $X$.

Assuming you only append data at the end, and don't do different things depending on the content of the message, this means that you always have to append something, even if the message is already of the right length.

In your scheme, in the case of a message which has already the length of a multiple of the block length, you'll have to append a full block ending with a 16 (assuming a 16-byte block cipher like AES).
Your unpadding function then reads the last byte, and knows it has to strip off 16 bytes.

You shouldn't do any special-casing with a block of a certain structure only in the case of a full block appended.

But note that you should preferably use standardized schemes to help interoperability - for example PKCS#7-padding works just like your scheme, but with a bit different filling of the padded data. (This, just like your scheme, requires that the number of appended bytes is encodable in a byte, i.e. a block size of less than 256 bytes = 2048 bits. I'm not aware of any common block cipher with a larger block size, but you would need a different padding scheme in this case.)


What is the advantage of AEAD ciphers? What is the advantage of AEAD ciphers? Why is the TLS working group pushing for them? I thought modern cipher suites require SHA256 for authentication. What advantage is there to including Poly1305?

Slight additional question: TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 has GCM and SHA256. What is GCM used for, and what is SHA256 used for? It seems all one needs is GCM.

AEAD cipher implementations are generally encrypt-then-authenticate internally (while the CBC ciphers in OpenSSL were not). TLS really was in need to get rid of the authenticate-then-encrypt which required special handling of the CBC code for block ciphers such as AES. The AEAD ciphers - regardless of the internal structure - should be immune to the problems caused by authenticate-then-encrypt.

AEAD algorithms generally come with a security proof. These security proofs are of course dependent on the underlying primitives, but it gives more confidence in the full scheme none-the-less.

These ciphers are often single pass (OCB, not often used), 1.5 pass (GCM, Poly1305) or 2 pass (EAX). That means that they generally have an execution speed advantage over two pass schemes using CBC + (H)MAC. Even a scheme as EAX can have performance advantages if a higher level language (Java, Python etc.) is used to implement TLS. This is because it is easier to create a fully optimized implementation for one algorithm (EAX) than for a combination of two algorithms at protocol level (CBC + HMAC). Internally EAX is simply CTR + CMAC.

Furthermore AEAD schemes generally can be (forced to) adhere to RFC 5116. That means that there is only one interface required for all of the AEAD ciphers with regards to the handling of the IV and plaintext. It is of course possible to let CBC + HMAC adhere to this RFC as well though.

Speed and security is probably the reason for Google to already support ChaCha20 + Poly1305/AES in Chrome. With such a big elephant in the room it is kind of hard to ignore this scheme by Daniel J. Bernstein (et all). It's a 1.5 pass AEAD cipher that uses a fast stream cipher underneath, so it's pretty efficient overall.


Regarding NTRU homomorphic properties NTRU has some homomorphic properties modulo q, supporting both addition and multiplication. Due to its nature, it cannot support many of them. My main focus currently is in the addition, so the question is how many additions could it support to consider the result reliable? I believe that a naive bound would be $q/2$ but is there anything better?

Since you referring to the LWE variant of Stehlé and Steinfeld, I will try to give you an answer to your question in that context. Note that these results are a mere extension of the correctness condition in Lemma 3.7 from the revised version of the paper [SS13]. As I said in the comments, at the end it all depends on the choice of parameters ($n, \alpha, q$, etc), and additionally, on the number of additions you want to support.

In this scheme, ciphertexts are of the form $c = h s + p e + m$, where $h$ is the public key, $s$ and $e$ are sampled from a Gaussian distribution, $p$ is a public parameter, and $m$ is the message. Public keys are of the form $h = p g f^{-1}$, where $f$ is the secret key, and $g$ a random polynomial.

The correctness condition for one ciphertext is $||f \cdot c_i ||_{\infty} \leq q/2$. We want to check the conditions for decrypting correctly a sum of $k$ ciphertexts:

$c_{sum} = \sum\limits^k_{i=1} c_i = \sum\limits^k_{i=1}(h s_i + p e_i + m_i)$

Since $f h = f (p g f^{-1}) = p g$, then $f \cdot c_i = f h s_i + p f e + f M = p g s_i + p f e + f M$

Hence, we want to check whether $||f \cdot c_{sum} ||_{\infty} \leq q/2$, where:

$f \cdot c_{sum} = \sum\limits^k_{i=1}(p g s_i + p f e_i + f m_i) = \sum\limits^k_{i=1}p g s_i + \sum\limits^k_{i=1}p f e_i + \sum\limits^k_{i=1}f m_i$

Lemma 3.7 provides the following bounds:

$||pgs_i||_{\infty}, ||pfe_i||_{\infty} \leq 8 \alpha q n^{0.25} \omega(\log n)||p||^2 \sigma$

$||fM||_{\infty} \leq 4n||p||^2 \sigma$

Therefore, $||f \cdot c_{sum}||_{\infty} \leq 2k\cdot(8 \alpha q n^{0.25} \omega(\log n)||p||^2 \sigma) + 4n||p||^2 \sigma$.

Next, assuming that $n^{0.75} \leq \alpha q$, as in Lemma 3.7, we have that:

$||f \cdot c_{sum}||_{\infty} \leq 16 k \alpha q n^{0.25} \omega(\log n)||p||^2 \sigma + 4n^{0.25}\alpha q||p||^2 \sigma$

After some simplifications, we obtain the following bound:

$||f \cdot c_{sum}||_{\infty} \leq (16 k + 4) n^{0.25}\alpha q\omega(\log n)||p||^2 \sigma$

Note that when $k=1$, it produces precisely the same result than Lemma 3.7. Finally, similarly to Lemma 3.7, we have to initially assume that $ \omega( n^{0.25}\log n)\alpha q k ||p||^2 \sigma < 1$, so the correctness condition for the sum of $k$ ciphertexts holds.

A final note: these results, as the one from Lemma 3.7, are not tight, and depend heavily on the choice of parameters. My guess is that you can sum (much) more than $k$ ciphertexts, and still decrypt correctly.

References

[SS13] Stehlé, D., & Steinfeld, R. (2013). Making NTRUEncrypt and NTRUSign as Secure as Standard Worst-Case Problems over Ideal Lattices. IACR Cryptology ePrint Archive, 2013, 4.


Looking for title of encryption machines book I am looking for a title of book in the field of stream crypography.

I vaguely remember, that I saw this book at online shop (maybe amazon) near 5-10 years ago. This book is devoted to electronic machines cryptography (LFSR). Electronic encryption machine (perhaps, military) and LFSR in a "magnifying glass" (shows that LFSRs are used inside this machine) is drawn on the book cover.

Now I can't find this book on ebay, amazon, springer, etc. Please help to recall this book.

Note that this is not book recommendation request. My question covers an actual problem that I faced, and it has unique correct answer (book title). I think cryptography community is a best place where this question can be asked.

This is the book, I believe.

W Barker: Cryptanalysis of shift register generated stream cipher systems

I have (had? I need to check, maybe gave it away) a copy.


Does the XML signature standard support Ed25519? https://www.w3.org/2008/xmlsec/Drafts/xmldsig-core-20/#sec-ECKeyValue talks about ECDSA but even the explicit curve parameter stuff won't work with Ed25519 as Ed25519 has a completely different equation with different equations for point doubling / addition, etc.

Does the XML signature standard support Ed25519?

As of 2018-03-12, no.

(Whatever is the latest version may change.)

The XML signature standard looks like a committee of bureaucrats got in a room with a 1990s-era textbook on cryptography and invented a way to shoehorn it into XML syntax by stuffing it into a blender with the X.509 standard and a collection of O'Reilly XML books.  This is not a standard for using—this is a fine standard for laying down and avoiding.


How was the 5 digit random number in the VIC cipher generated? Knowing that VIC was a "spy cipher" it is unlikely that the agents used a cryptographic device to genreate the 5 digit number but how did they do it?

In the VIC cipher, that significant five-digit number was created by the user when doing the encryption. It was surely made on the spur of the moment without equipment. As you remarked, these people were spies, and they would not have wanted to get caught with some strange device.
The CIA's online library does not mention the five-digit number as a value that the user had to memorize. The agent already had four mnemonic keys stored in his or her mind:
 1. a date (in Russian this would be day/month/year; six digits)
 2. a snippet of a popular Russian song        (20 characters long)
 3. the user's personal identification number
 4. a Russian word (e.g., the word for "snowfall")

I do not know for sure, but I think it is most likely that agents came up with their own "random" number out of their own heads. One, admittedly thin, piece of evidence might be that the Russians were generating "one-time pads" at that time out of their own heads by pecking at a typewriter--and keys generated in such manner were considered "random" enough to encrypt important traffic.


What makes SHA-256 secure? For example, RSA relies on a mathematically hard problem, factoring, while ECDSA or similar rely on discrete logarithm problem.

What makes SHA-256 and similar hash functions, of the same family, secure against pre-image and collision attacks? What's the math behind it?

It's worth pointing out that in the case of SHA2 and most other hashes the compression function has a block cipher (keyed permutation) as its core.

Basically what you are asking is identical to asking how can block ciphers be resistant to known-plaintext attacks and chosen-plaintext attacks (arguably doesn't apply to SHA2 specifically because an attacker doesn't control that aspect) and even related-key attacks in the case of SHA2 (because it uses a Davies-Meyer construction where the attacker has control over what gets fed into the key schedule).

There is no proof that this methodology is reducible to something that is proven secure. It is believed to be secure due to diffusion and confusion properties which as far as is known allow no efficient backtracking. You can think of it as extreme sensitivity-to-initial-conditions in a discrete non-continuous domain.

Edit: The reason I went to block ciphers is because hash security is provably reducible to the security of the core keyed permutation (or even unkeyed if you look at SHA3) - that's how hashes are designed to begin with. Which I believe is the spirit of your inquiry. But the buck stops there, no security proof for those exists.


Why do Feistel ciphers need round keys? Looking at the design for Feistel ciphers, they use a list of round keys which are generated from the main key using the key schedule of the associated block cipher. Some block ciphers need this as to prevent repetition, but why does a Feistel network need it?

If $F$ is a good PRF, then the output should be indistinguishable from random after the first few rounds. Under the random oracle model, one would expect that $L_0$ is made pseudorandom after the first round, then $R_0$ is made pseudorandom right after that. Continuing this should never return you back to the plaintext in a reasonable amount of time.

So my question is why are round keys used in the Feistel network as opposed to making all the round keys the same? Did I get anything wrong in my reasoning?

Iterated ciphers need variability between rounds to resist so callad Slide attacks. One common way to thwart this attack is with a key schedule generating different round keys for each round.

Slide attacks exploit the repeating rounds of the cipher by finding a collision between one input plaintext and the intermediate value after one round of encryption of some other plaintext. This collision gives a "slid pair" and gives the attacker two known input/output pairs of the round function which in many cases is enough to recover at least parts of the key.

In the question we have a balanced Feistel cipher where every round uses the same round function and key. Due to the birthday paradox we expect to find a slid pair with on the order of $2^{n/4}$ chosen plaintexts or $2^{n/2}$ known plaintexts, breaking the cipher.


Crack linear congruential generator knowing every other word in sequence I need to crack one of the example of linear congruential generator.

I have $X_{n+1} = (a \cdot X_n + b) \bmod m$

and I know every other word in the output sequence:

..., 3158, ..., 1888, ..., 1285, ..., 1744, ..., 253, ..., 722, ...

The question is how to get the generator parameters ($a$, $b$, $m$) ?
I have read Cracking a linear congruential generator
but still don't know how to break it.

Sometimes, rather than do cool math, the easiest approach is brute force!

#include <stdio.h>
#include <assert.h>

int main()
{
    enum { X0 = 3158, X1 = 1888, X2 = 1285, X3 = 1744, X4 = 253, X5 = 722,
           M_START = 3159 };
    for (int m = M_START; m < 10*M_START; ++m) {
        for (int a = 2; a < m; ++a)  {
            int c = X2 - ((X1 * a) % m);
            if (c < 0)
                c += m;
            int my_x2 = (X1 * a + c) % m;
            assert(my_x2 == X2);
            int my_x3 = (X2 * a + c) % m;
            int my_x4 = (X3 * a + c) % m;
            int my_x5 = (X4 * a + c) % m;
            if (my_x3 == X3 && my_x4 == X4 && my_x5 == X5) {
                printf ("m=%d, a=%d, c=%d\n", m, a, c);
            }
        }
    }

    return 0;
}

This code does an exhaustive search.  In less than a second, it spits out:

m=3187, a=2663, c=2627
m=6374, a=2663, c=2627

Now, this is for an LCG that just outputs the values you gave without any gaps.  But we can easily do a little math to work out that if $a^2 \mod m = 2663$, then $a = 1200$, the modular square root of 2663 (in Mathematica, PowerMod[2663, 1/2, 3187]).

Likewise, we can easily find $c$.  Thus, we find $m = 3187, a = 1200, c = 854$.

And thus the actual sequence (with odd-numbered items in bold) is 2679, 3158, 1111, 1888, 497, 1285, 346, 1744, 2982, 253, 1689, 722, 390, 365, 2235, 2587, 1116, 1514, 1064, 2854, …

But maybe you worry that I've used a $\mathrm{O}(n^2)$ algorithm?  What if $m$ were larger?  Well, I was just feeling lazy, that's all.  We can easily drop the complexity to something far less.  It just makes for slightly longer code:

#include <stdio.h>
#include <assert.h>

int modular_inverse(int a, int m)
{
    // Based on code from http://rosettacode.org/wiki/Modular_inverse#C
    int t, nt, r, nr, q, tmp;
    t = 0;  nt = 1;  r = m;  nr = a % m;
    while (nr != 0) {
        q = r/nr;
        tmp = nt;  nt = t - q*nt;  t = tmp;
        tmp = nr;  nr = r - q*nr;  r = tmp;
    }
    if (r > 1) return -1;
    if (t < 0) t += m;
    return t;
}

int main()
{
    enum { X0 = 3158, X1 = 1888, X2 = 1285, X3 = 1744, X4 = 253, X5 = 722,
           M_START = 3159 };

    for (int m = M_START; m < 10*M_START; ++m) {
        int diff0 = (X1 - X0);  if (diff0 < 0) diff0 += m;
        int diff1 = (X2 - X1);  if (diff1 < 0) diff1 += m;
        int diff2 = (X3 - X2);  if (diff2 < 0) diff2 += m;
        int diff3 = (X4 - X3);  if (diff3 < 0) diff3 += m;
        int diff4 = (X5 - X4);  if (diff4 < 0) diff4 += m;

        // diff1 = a * diff0   =>   1/diff0 * diff1 = a
        int inv_diff0 = modular_inverse(diff0, m);
        if (inv_diff0 < 0) continue;
        int a = (diff1 * inv_diff0) % m;

        int my_diff1 = (a * diff0) % m;
        int my_diff2 = (a * diff1) % m;
        int my_diff3 = (a * diff2) % m;
        int my_diff4 = (a * diff3) % m;
        assert(my_diff1 == diff1);

        if (my_diff2 == diff2 && my_diff3 == diff3 && my_diff4 == diff4) {
            printf ("m=%d, a=%d\n", m, a);
        }
    }

    return 0;
}

This version spits out its answer essentially instantly, taking 0.001 seconds to run the program.

m=3187, a=2663

From here, we can then figure out $c$ and then proceed as above.

BTW, if you enjoy more of a challenge, feel free to check out this question I asked a while back.


Is there a practical way to crack an AES encryption password? I heard that the fastest method to crack an AES-128 encryption, or and AES-256 encryption is by brute force, which can take billions of years. But I can't help thinking there's got to be a faster way.
Because the AES encryption scrambles the data contained in a zip file, the password could be found by unscrambling that data correctly. Say if a portion of the data in the file is known, for example a string at the end of a file, or a header containing an expected sequence of bytes in a known file type.
 Then by comparing the scrambled bytes with the 'expected' unscrambled bytes, the password can easily be determined by computing an algorithm that converts those bytes because both the scrambled bytes and the unscrambled bytes are known. Only the formula is unknown.
However, the condition for this type of cracking is that the zip file contains known file types which have a determined data format and places certain data in certain locations in the file. For instance, a 3ds file always starts with a header containing the bytes "4D4D".
Hence a list of possible passwords to rearrange the sequence begin to be narrowed down as the cracking progresses.
So is this method plausible? or is there something wrong with it,  like maybe the actual address of the bytes in the zip is different from the address in the unzipped file.

Yes, in the question's situation, a password-recovery attacks is entirely reasonable.

The question considers a (partially) known plaintext attack, where e.g. some header of the encrypted file(s) is known, for a file encrypted with AES, where the key has been determined from a user-supplied password. In this scenario, it is not important to consider the expected number of AES operations for brute-force search of the AES key ($2^{127}$ for AES-128, $2^{255}$ for AES-256) because that's not the best (nor a credible) attack strategy.

The reasonable attack strategy is password cracking: try passwords, approximately from most to least likely to have been chosen, and for each attempt decryption up to the point where known plaintext is reached, and move on to the next password if this test fail. Attack cost will depend on:

How the password was chosen. Users vary widely on that, and 123456 will be easier to find than MdSm2aZ!t&5u*Z5. That varies widely with the context, and motivation of users. See the obligatory XKCD.
How the password is transformed into an AES key. A password-based key derivation function should be used here, parametrized so that it adds a sizable cost.

The cost for an attack grows roughly as $2^E$ times the cost of the PBKDF (assuming that dominates the cost of testing a password), where $E$ is the password entropy in bits. For example, if the password is 6 random decimal digits ($E=\log_2(10^6)\approx19.9\,\text{bit}$), and the PBKDF + plaintext testing uses 0.1 second of CPU time (300000 CPU cycles @3GHz), a competent attacker will use an average of $10^6\times10^{-1}/2=50000\,\text{s}<14\,\text{h}$ of CPU time to find a password, that is less than 2 hours of wall clock time with a single 8-core PC, minutes for a powerful adversary.


TLS1.2 AES 128 CBC Encrypted Data size is not a multiple of block size I know that TLS ciphers such as TLS_RSA_WITH_AES_128_CBC_SHA transmit data as shown https://tools.ietf.org/html/rfc5246#section-6.2.3.2. From my understanding the ciphertext MUST be a multiple of the block size, which in this case is 16 bytes. However when I look at the below output from wireshark, I'm confused. After subtracting the 16 bytes corresponding to the IV from the beginning of the Encrypted Application Data, that leaves 100 bytes of ciphertext which is obviously not a multiple of 16. What am I not understanding?

EDIT: I've included information about the ciphersuite

The default mode of TLS use MAC-then-Encrypt, it compute the tag, append it to the message, and then padd it to have a length multiple of the block size (16 in our case).
However, you can change the default mode to use Encrypt-then-MAC (which eliminates risks of padding attacks over AES-CBC). In this case, the message is padded and encrypted, and only then you compute the tag and add it at the end.

In your case,  TLS_RSA_WITH_AES_128_CBC_SHA use SHA1, which produce a 20 bytes long tag :
$$116-20=96=16\times 6$$

That's the only way I have to explain it, but both the server and the client have to implement the option Encrypt-then-MAC.


Using cryptographic hash to match AES key size I am making a tool for myself where I intend to store cipher text. I wish to use AES together with arbitrary sized keys to create these cipher text strings. The idea is to use a cryptographic hash like SHA256 to compensate for the key length issue.

Is this a sound way of doing things?

Also, since the output domain of SHA256 is much larger than any key a "normal" person can remember, does this add security if an attacker gets hold of the password digest from for example a computer?

Is this a sound way of doing things?

Depends. Where do the keys come from? If they come from a user's memory (e.g., a password) then no. The reason for this is that a simple hash if fairly fast to compute. Typically we recommend people use something like PBKDF2 or scrypt as they run through thousands of iterations. The effect of this is that computing this function once is still fairly fast and user won't notice the delay. Trying to brute force it, however, involves computing the function many, many times. This slows down a brute force attacker significantly. Also, scrypt in particular was designed to be slow on hardware. That means attackers can't throw a GPU or other hardware device at the problem to speed it up.

  Also since the output domain of sha256 is much larger than any key a "normal" person can remember, does this add security if an attacker gets hold of the password digest from for example a computer?

No. We often measure security in bits. In particular, bits of entropy. A deterministic function (like sha256) cannot create entropy.


How to make this cipher strong? Suppose I have an arbitrary 256 bit number $m$ another secret number $k$ of the same bit length, and then I multiply them both modulo a 256 bit prime number $p$ to get $c$ as follows:
$$
c = (m\cdot k) \mod p
$$
Is there any way to get $m$ back without knowing $k$?

Can anyone please clarify a bit more on that, and also please explain to me why my example can be broken by an attacker?

The cryptosystem enciphers plaintext $m$ as ciphertext $c \gets (m\cdot k) \bmod p$ where $k$ is the secret key, and $p$ is a prime. It is (silently) assumed $0<m<p$ and $k\bmod p\ne 0$; otherwise decryption by $m \gets (c\cdot k^{-1}) \bmod p$ is not possible. Not told, and of paramount importance: is $k$ used just once, or reused?

Once: the system is information-theoretically secure, which is the best it can get, but is not a cipher per both the academic and practical definitions of that. It's like a One Time Pad, as inconvenient from the standpoint of transmitting the key, and much less convenient to use afterwards.
Reused: The system is a cipher, but it is trivial to find (a working equivalent $\hat k$ of) $k$ from a single known pair $(m,c)$, per $\hat k \gets (c\cdot m^{-1}) \bmod p$; then decipher the rest. This is below what the expectation for good crypto has been since at least Kerckhoffs.

There's no bad crypto that can't be improved: if we use OAEP padding like in RSA to turn the message into $m$, and undo that on decryption, I believe the combination becomes a provably secure IND-CPA (perhaps IND-CCA2) symmetric cipher. But we have simpler and more efficient ones.


Side-Channel attack on RSA decryption using comparison result with p,q? I was pointed to whether we could learn the secret key of RSA by repeatedly using following side channel:

We assume that there exists a side channel in RSA decryption using CRT that, if the most-significant bits of the input x (down to about half the size of x) are zero, reveals if:

$$x \bmod p > x \bmod q$$

Can we learn the secret key through that side channel?

Some hints:

You know $p\,q$.
First assume $q<p$ and find $q$ by dichotomic search.
Move to the slightly more difficult case $p<q$.

In dichotomic search, it is given an integer interval $\big[a,b\big]$ and a Boolean function $F$ defined on that interval such that $F(a)\ne F(b)$. Dichotomic search always find $c$ in $\big[a,b\big)$ with $F(c)=F(a)$ and $F(c+1)=F(b)$, using $\approx\log_2(b-a)$ evaluations of $F$. It proceeds by repeatedly computing $c=\lfloor(a+b)/2\rfloor$, stopping when $c=a$, otherwise replacing $a$ or $b$ by $c$ according to if $F(c)=F(a)$ holds or not.

Define $F(x)$ to be the result obtained by submitting $x$ to the side channel. That is $F(x)=\text{true}\iff(x\bmod p)>(x\bmod q)$.

By definition of the $\bmod$ operator in $x\bmod m$ (recognizable by neither having an opening parenthesis immediately on the left of $\bmod$, nor appearing on the right side of an expression with a matching $\equiv$ sign), for all $x$ and all $m>0$ it holds that $0\le(x\bmod m)<m$ and $m$ divides $x-(x\bmod m)$. It follows the properties
$$\begin{align}
x=(x\bmod m)&\iff 0\le x<m&&\text{and}\\
x>(x\bmod m)&\iff x\ge m
\end{align}$$

For the second bullet: When $0\le x<p$ and thanks to the above properties, $F(x)$ reduces to $x>(x\bmod q)$, then to $x\ge q$. Set $a=1$ and $b=\lfloor\sqrt{p\,q}\rfloor$, which we can compute. From the hypothesis $q<p$, we get $q\le b<p$. Therefore when $x\in\big[a,b\big]$ the function $F(x)$ tells whether $x\ge q$. It holds that $F(a)=\text{false}$ and $F(b)=\text{true}$. Thus dichotomic search yields $c$ in interval $\big[1,\lfloor\sqrt{p\,q}\rfloor\big)$ with $F(c)=\text{false}$ and $F(c+1)=\text{true}$, that is $c<q$ and $c+1\ge q$. That reveals $q=c+1$.


With AES-GCM, may I use multiple tags per key? In my implementation of AES-GCM, the key might change only once per minute.  However, I wish to calculate a new tag every 6us, to reduce latency (since you have to buffer up a GCM "packet" before checking the tag and releasing it).

May I keep the same key and generate millions of tags using the same key, as long as the GCM counter increments for every 128-bit block?
Do I need to restart the tag computation process (i.e., clear accumulators) for each tag?
Or, must I change the key once a tag is computed and transmitted?
In a related question, can I use an IV of fewer than 96 bits?

Normally there is an IV of 96 bits and a 32-bit counter, but at my data rates (400Gbps) I'll burn through the 32-bit counter in less than 1.5 sec, and I don't want to have to update the key every second.

Could I use, say, an 84-bit IV with a 44-bit counter?

I thought I'd update this with what I learned designing my ASIC.  I found the literature and terminology very ambiguous, even McGrew & Viega's paper on GCM.  Thanks to Poncho and others for their answers.  Here are some notes from my code:

************************* Nonce Format *****************************

|<--            Counter Block (CB) (128 bits)                   -->|
|<--            Nonce (96 bits)                   -->|
                                  |<-  Invoc Cntr  ->|
                      Salt[56:63] |<-->|
+-----------------+---------------+------------------+-------------+
|   salt[0:31]    |  salt[32:55]  |       SEQ        |   Blk Ctr   |
+-----------------+---------------+------------------+-------------+
|<--    32      -><--    24     -><-      40       -><-   32     ->|

Salt:  64-bit value used to form the nonce.  This is unique to each
       key.  It should be true-random but need not be secret.
       RFC-4106 recommends that only salt[0:31] be used and that
       salt[32:63] be left at 32'b0.  salt[56:63] will be XORed
       with the leftmost 8 bits of SEQ.
SEQ:   Extended sequence number, aka invocation counter.  This is
       called the IV (Initial Vector) in RFC-4106.  This normally
       starts at 0 with a new key and increments every frm.
Blk Ctr:  This starts at 32'd2 on every frame and increments for
       every 128-bit block of cryptext.
-------------------------------------------------------------------

In my case, I start with a key/salt pair, which should be updated every 8 hours. (I generate a new tag every ~6$\mu$s, and the NIST recommends not using more than $2^{32}$ tags per key.)

Much of the terminology (e.g., "IV") is ambiguous.  The terms I use are not completely standardized.  There is a unique "nonce" for each "frame", where each frame has a tag.  The nonce format is shown above.  The "salt" is normally 32 bits but can be up to 64 bits.  It changes when the key does.

When the key/salt changes, the 40-bit sequence counter SEQ is reset to 0.  SEQ increments for every "frame", each of which is terminated with a tag.  In my case, "frames" have about 20e3 128-bit AES blocks.  SEQ should not exceed $2^{32}$ to prevent tag forging.

The 32-bit block counter starts at 2 at the beginning of each "frame".  It increments for each 128-bit block up to about 20e3 and then resets for the next frame (after a tag is generated).

I don't have to worry about collisions because only one chip is encrypting with a given key, so there will be no nonce reuse.


Montgomery Exponentiation - selecting input value R for a given BigInteger I have Montgomery exponentiation working, but it's working quite slow. I suspect there are two reasons for this - I implemented it bit size instead of word size (I didn't realize at the time that software implementation should use word size).

The second is how I select R. Given a modulus N with bit length n, I'm calculating R by raising 2 to the power of the bit length of N, n. i.e. This is way all the examples I've seen use, but they all use small numbers. Every number I'm dealing with here has at least 1024 bits.

BigInteger R = new BigInteger("2").pow(n.bitLength());

I suspect this might be why my Montgomery is running slower than my Right-To-Left binary implementation - can anyone give me a more efficient way of selecting r? (In as simple English as possible please!)

Edit - the full code is at - https://codereview.stackexchange.com/questions/18199/optimization-of-exponentiation if anyone want to have a look at it.

Montgomery multiplication makes sense only with word sizes. If your word size is $w$ (e.g. $w = 32$ if you have 32-bit words), then $R = 2^{kw}$ for some integer $k$; you choose $k$ as small as possible, given that you must have $R \geq N$.

In plain words, if your modulus $N$ has size $n$ bits, then you look for the next multiple of $w$. For a 1024-bit modulus, which is already a multiple of 32, you use $R = 2^{1024}$. For a 1025-bit modulus, you would use $R = 2^{1056}$.

You really want to read chapter 14 of the Handbook of Applied Cryptography.


Complexity of arithmetic in a finite field? I am wondering what the complexities are of adding/subtracting and muliplying/dividing numbers in a finite field $\mathbb{F}_q$. I need it to understand an article I am reading.

Let $n = \lceil \log q \rceil$ (with "$\log$" being the base-2 logarithm, so $n$ is the size, in bits, of $q$).

If $q$ is a prime integer (i.e. $\mathbb{F}_q$ is the field of integers modulo $q$), then classical implementations will have cost $O(n)$ for addition and subtraction, $O(n^2)$ for multiplications and divisions. The cost of multiplications can be asymptotically lowered by using Toom-Cook multiplication or Fast Fourier Transform (with fast algorithms for the final modular reduction, whose name currently evades me), down to about $O(n(\log n)^2)$. However, for numbers of the size used in cryptography (say, 2048-bit integers), these methods tend not to be worth the effort, and plain Montgomery multiplication is faster. At least so goes the usual wisdom; each new hardware architecture may challenge such results. For modular divisions, the fastest algorithm is the extended binary GCD algorithm, which is quadratic.

One must note that even if Montgomery's multiplication and extended binary GCD are both in cost $O(n^2)$, the former tends to be, in practice, several dozen times faster than the latter, for numbers of the same size, because Montgomery's multiplication can rely on the hardware native multiplication opcode and process bits by chunks of 32 or 64, while binary GCD is a bit-by-bit algorithm.

If $q$ is a power of 2 ($q = 2^n$), then field $\mathbb{F}_q$ is the quotient field obtained by taking polynomials in $\mathbb{F}_2[X]$ modulo a given irreducible polynomial $P$. Since all finite fields of same cardinal are isomorphic, one can choose the polynomial $P$ to be almost empty, i.e. a trinomial ($P = 1 + X^a + X^n$) or a pentanomial ($P = 1 + X^a + X^b + X^c + X^n$). This allows for a linear reduction modulo $P$. In practice, multiplication will be done with Karatsuba's algorithm with complexity about $O(n^{1.585})$.

Also, in a binary field, squaring (and extracting a square root) can be done very efficiently, with $O(n)$ complexity. This is the Frobenius endomorphism, and is used to speed up computations on a special kind of elliptic curves called Koblitz curves. Squarings and square roots can be even further optimized to become "free" using normal bases, but this makes multiplication widely less efficient, so this is not considered to be a net gain in the general case.

Besides the Handbook of Applied Cryptography (especially chapters 2 and 14), a good reference is chapter 2 of the Guide to Elliptic Curve Cryptography, which covers finite field arithmetics -- and, lo! chapter 2 of that book is the "free sample" chapter that can be downloaded as a PDF from the Web site.


Why does a one-time-pad key have to be at least as long as a message? I am studying one time pad and find it hard to understand. What happens if the key is one bit or 100 bits shorter than the message?

If you using in one time pad key shorter then message, it means that some part of text will be encrypted with same part of key, two or more time.
In this case, XORing two part encrypted with same key, adversary can receive few information about plaintext. If key significantly shorter then plaintext, adversary can apply frequency analysis to discover whole message, or part of it.


Is flipping the bit belonging to encryption? Just a simple question about encryption.

If we have an image, we transform into a bits and we get 1001001...
Then, I flip the bits into 0110110... manually.

Can I said that I have done an image encryption?

Thanks.

The book "Cryptography Engineering - Design Principles and Practical Applications" was recommended to me on this very site.

From the book:

  Bob needs two things to decrypt the ciphertext. He must know the decryption algorithm D, and the key Ke. An important rule is Kerckhoffs' principle: the security of the encryption scheme must depend only on the security of the key, and not on the security of the algorithm.

While I've only just started reading it myself the mention of Kerckhoffs' Principle (see
Why should I make my cipher public?) is most relevant to your question.

The method you present uses an algorithm but has no key. So anyone who learns how you are flipping bits could restore your original image.

Let's just call your method "image obfuscation".


What is the "successive-configuration relation"? This term is used in the book Foundations of Cryptography on pg 20 with regard to defining deterministic oracles, but is not previously defined and I can't seem to find a definition online easily.

OK, let's first observe the usage of the word in-context:

  Definition 1.3.8 (Oracle Machines): A (deterministic/probabilistic)
  oracle machine is a (deterministic/probabilistic) Turing machine with
  an additional tape, called the oracle tape, and two special states,
  called oracle invocation and oracle appeared. The computation of the
  deterministic oracle machine $M$ on input $x$ and with access to the
  oracle $f:\{0,1\}^*\to\{0,1\}^*$ is defined by the
  successive-configuration relation. For configurations with states
  different from oracle invocation, the next configuration is defined as
  usual. Let $\gamma$ be a configuration in which the state is oracle
  invocation and the content of the oracle tape is $q$. Then the
  configuration following $\gamma$ is identical to $\gamma$ , except that the state is
  oracle appeared, and the content of the oracle tape is $f(q)$. The
  string $q$ is called $M$’s query, and $f(q)$ is called the oracle reply.
  The computation of a probabilistic oracle machine is defined
  analogously. The output distribution of the oracle machine $M$, on input
  $x$ and with access to the oracle $f$ , is denoted $M^f(x)$.

So the context we have is: Turing Machines!

Now if we look at the formal definition of a turing machine, we will spot a relation $\delta:(Q\setminus F)\times\Gamma\to Q\times \Gamma\times\{L,R\}$. Note how a function is actually just a relation.

This above function defines, when in a given state and looking at a given cell content, which cell content shall be written, where state shall be entered and which direction the head shall be moved. Thus, this relation defines the successive configuration for every configuration. However I'd guess that the relation used for the turing machine in question is a little bit more complicated than the one of the "basic" turing macine (also accounting for the special states and the extra tape).


Is splitting AES ecrypted data safe? Say I have a key, an iv and an AES/GCM/NoPadding encoded string and I want to split this information between three people such that only jointly can they reveal the secret.

Is it safe to just split all this data to three equal chunks and provide to each party in a format "1/3 of key-1/3 of pass-1/3 of iv"? Under "safe" I mean, is it possible to come up with some kind of efficient attack while having 1/3 (or 2/3) of all the data?

Just use Shamir's Secret sharing: wiki link

It's designed by Adi Shamir, who is the "S" in RSA. It's fairly simple to use and there are no known weaknesses in it. While it doesn't split the data, splitting the key may work just as well (unless you absolutely must split the data.)


Why does SRP-6a use k = H(N, g) instead of the k = 3 in SRP-6? I've been reading up on the Secure Remote Pasword protocol (SRP). There are a couple different versions of the protocol (the original published version being designated SRP-3, with two subsequent enhancements 6 and 6a).

There was a very limited attack on version 3, where the attacker could submit two password guesses per falsified attempt against the server instead of just one. This was because in step 2 where the client submits ($g^x + g^b$) to the server, they could in fact set $b$ to be a second password guess, and since the server doesn't have the password, it can't tell that $b$ isn't randomly chosen (like it's supposed to be). The attack and remedy are detailed in the paper for SRP-6.

The remedy described in SRP-6 is that the client send $k·g^x + g^b$ instead, where $k = 3$. However, there is also a version SRP-6a (which is the version detailed on the page above), which sets $k = H(N, g)$. Since both $N$ and $g$ are publicly known values ($N$ is a large safe prime, and $g$ is it's generator), and the $(g,N)$ group is used for all transactions in a given SRP system (independent of password, user or session), $k$ is still a constant value.

So the question is, what's the justification/benefit of picking this alternate value $H(N,g)$ for $k$? This value of $k$ is used in the TLS/SRP implementation, but I haven't found any explanation for why.

If k is a constant, such as 3, it becomes possible to select a pair (N,g) such that the discrete log of k to the base g is known, which would enable the two-for-one guessing attack again.


Can you help me understand indistinguishably as described in the CPA security definition? When I read the definition of the CPA indistinguishably encryption scheme, I see that the adversary can use an oracle as many times (to get as many encryptions of any messages it choose). An the end of the experiment, it has to distinguish between two messages $m_0$ and $m_1$ while it gets $c_b$ (from some challenger), which may be one of $m_0$ and $m_1$ encryptions.

But what if the adversary uses the oracle to get the encryptions (of $m_0$ and $m_1$)? Does that mean the encryption algorithm uses some probabilistic way and generates an exponential ciphertext space for every key, which does not give the adversary a polynomial advantage?

Yes, your intuition is completely right (assuming a polynomial-time adversary and a super-polynomial message space, which is the usual setting). If the scheme were deterministic, then the adversary could simply use the oracle to distinguish which message was encrypted. Therefore, no deterministic encryption can be CPA-secure. This is a well-known implication of the definition of CPA-security.


Why is keysize almost always expressed in bits? I've never actually seen a time when somebody has expressed RSA keysize in bytes, and I haven't seen keysize expressed in bytes in other encryption algorithms either (can't be certain that that's always the case). Is there a reason why keysize is almost always expressed in bits instead of bytes (in encryption algorithms in general, not just RSA)?
P.S. if possible possible, please link any documentation to support your answer.

It’s traditional.

(Don’t underestimate the power of Tradition. The main reason we use bits is that this is how things have been done for a lot of time. If only to avoid confusion, it is a reasonable idea to stick to traditions. You don’t need a compelling reason to do things in the usual way, but you’d need one to do things differently.)

Also, bytes have not always been octets. The PDP-11 used 9-bit bytes. Even the C standard defines bytes to have at least eight bits, but possibly more.


What is the effect of the different AES key lengths? How does a changing key length affects the ciphertext, not only in case of AES, but in general? I know that the key spaces become much larger and the number of rounds in case of AES changes, but is security really that much enhanced that if I choose 256 bits as key length it is sort of unbreakable?

Something else what I'm thinking about currently, any idea if it is possible to get any details about key length or algorithm of an observed ciphertext? For example when measuring the entropy (or anything else) is there any difference e.g. between AES and DES?

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

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

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

There are a few gotchas:

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


What type of cipher or encryption method is this called? Let's say I have a key value of 5.

The message I want to encrypt is "AAAA"

A = 1,
B = 2,
C = 3,
and so on...

the final message is "FLRX"

Each letter will be the value of itself + the value of the previous + the key

1. A = A + previous + key = 1 + 0 + 5 = 6
*6 corresponds to the letter F
2. A = A + previous + key = 1 + 6 + 5 = 12
*12 corresponds to L
3. A = 1 + 12 + 5 = 18
*18 corresponds to R
4. A = 1 + 18 + 5 = 24
*24 corresponds to X

What is this method called? I've been looking at most known ciphers and it doesn't seem to match any. The reason it caught my attention is because the same letter doesn't correspond to the same output much like the majority of the well known ciphers. It is based on the previous letter assignment.

Adding the previous block to the plaintext before encryption is what the CBC mode of operation does. So you're essentially treating the Caesar cipher as a block-cipher and using it in CBC mode.

This adds no security relative to a plain Caesar cipher, since the attacker can simply undo the addition before proceeding to break Caesar as usual.

  the majority of the well known ciphers

That property is shared by substitution ciphers, but not by Vigenere. Modern ciphers don't have any such obvious weaknesses either if you use them correctly.


Why does Merkle's Puzzle requires Eve quadratic complexity of effort to break the system? The way Applied cryptography 2ED explains the puzzle is as follows (I paraphrase it):

Bob generates 2^20 messages of the form x,y where x is a puzzle number and y is the secret key. Both x and y are different for each of the one million message. Encrypt each message using symmetric cipher with a different 20-bit key. Send all messages to Alice.
Alice picks one at random and brute force it. She should be able to recover x and y.
Alice encrypts her message to Bob by using y she just recovered (using symmetric cipher). Her message will contain x, the puzzle number.
Bob looks up the secret key for puzzle x and decrypts the message.

According to the book and many Internet sources, Eve would have to do theta(n^2) work to brute force the communication.

The book doesn't seem to say much about how x is included in Alice's response to Bob. It must be not be encrypted right? Because Bob has to do a O(1) look up. That is, Alice would have to send x+E(private message, y) to Bob.

Then why can't Eve just wait for Alice's response to Bob and compute that puzzle?

This is the brute force algorithm I think would satisfy 2^n if x is encrypted in Alice's response as well.

for y in 2^20:
   for x in 2^20:
       c = symmetric_enc(y, x)
       if c == c_from_alice:
           return yes, c, x, y
return no, none, none, none

But if x is encrypted in Alice response, then Bob have to brute force like Eve too, no?

$x$ is not encrypted in Alice’s response. The point is that, even though Eve knows the puzzle number $x$, she has no way to tell which of the puzzles Bob sent is the one with this number, unless she solves all of them (or at any rate half of them, on average).


Collision attacks on digital signatures After reading this document about MD5 collision attacks, I still don't understand how collisions can make digital signatures insecure. In the paper, the researchers created two files with the same hash, one innocent and one malicious. The malicious party first sends the good file, gets it signed, and then copies the signature to the bad file to be used against the victim. My question is this: since it is impossible to create a collision without a giant jumbled mess somewhere in the file (though not necessarily immediately visible to the user, for example if preceded and followed by """ in a Python file), why can't users simply ensure that files don't contain blocks of seemingly random bytes if they're digitally signed? For example, why can't SSL certificates hash with MD5 and then use client-side code to verify they don't have any weird strings in them?

Manual detection of such blobs of random bytes is rather easy to circumvent, as soon as the file is either too long or non-human-readable. So for something like this to work, you would need to automate the process.

The problem is, that it's really hard to find a valid ruleset on what is a blob of random bytes and what is valid data.

An automatic detection algorithm would have to understand all file formats that should be checked. So lets say, that program could detect a Python triple-quoted comment. Now you let it check a Java file. Java does not do triple-quoted comments, but instead uses /* do denote multiline comments. So your checker does not understand that. Or you could let it check a JPEG-file, which just looks like random bytes, if your checker does not understand JPEG.

Also, triple-quoted strings with random bytes often serve a real purpose, e.g. if you have a look at get-pip.py, it has a blob of Base64-encoded binary at the end, which contains a full installation of pip. Or any RSA-keys, they also look like random bytes and it would be really easy to put something into these fields, that causes an MD5 collision.


Encryption algorithm which produces comparable results for substrings I am wondering is there any encryption algorithm available which produces comparable string.

I am expecting the output as shown below.

Data        |       output
---------------------------------------------
testData    |  uTrildHcKpM
testData_1  |  uTrildHcKpMiopu

Please let me know if you happen to know such algorithms.

It is somewhat unclear what you mean by comparable strings. But from the example you give, one might construe that you want the same substrings in different plaintext messages to be encrypted in the same way. This property is obviously very bad for an encryption scheme (given a number of plaintext/ciphertext pairs it would be easy to derive a lot of information about the encryption scheme).

There are however early instances of encryption with such a bad property like the monoalphabetic substitutions (Caesar's cipher for example).


Split 32-bit LFSR into two 16-bit LFSR which xor to same sequence Today I was thinking about exactly this.

Is it possible, for a 32-bit LFSR e.g.

x^32 + x^30 + x^28 + x^26 + x^22 + x^21 + x^20 + x^16 + x^14 + x^12 + x^10 + x^8 + x^7 + x^6 + x^2 + x^1 + 1

to generate two 16-bit LFSR which xor to each other generate the 32-bit sequence?

edit:
my wording wasn't exactly

there is a LFSR sequence with a known plaintext of 64 bit e.g.

1010111000000011
1111001010111001
0001010011010111
1001001111101101

it is known that this LFSR is built upon two 16bit LFSR which xor together give the same sequence as the LFSR above.

is it possible to generate the two unknown 16bit LFSR?

technically you have many lineary connections,

for example you know either the first bit in the first LFSR or the first bit in the second LFSR is 1

If a given 64-bit sequence is known to be the bit-by-bit XOR sum of
the outputs of two 16-bit LFSRs, then the degree-32 LFSR feedback polynomial
found by the Berlekamp-Massey algorithm is indeed the product of the
(16-bit) feedback polynomials of the two 16-bit LFSRs, and as @poncho said,
you need to factor the degree-32 polynomial into two 16-degree polynomials.
But, be aware that while this is guaranteed to work when the two 16-degree
polynomials are irreducible, there can be issues if the two 16-degree
polynomials are not irreducible or are not relatively prime. For example,
it might be that the Berlekamp-Massey algorithm (which finds the shortest
LFSR that will generate a given sequence) might give you an LFSR of length
less than 32 when the algorithm is applied to the 64-bit sequence.


Bijective function with unknown reciprocal function I have a use case where I need to build a unique identifier for my users with the email address and the "family member number". However, the two personal informations used to build the identifier must be hidden. I thought using a hash function for that but there is a risk of collision (the identifier is not guaranteed to be unique).
Should I still use a hashing function for that, or should I use some kind of bijective function with unknown reciprocal, if such kind of function exists?

First of all, there is no problem with using SHA256 or SHAKE128/256[1] those would have had $2^{128}$ collision resistance with a 50% probability by the birthday attack. If you really fear that switch to 512-bit versions. Take SHA512 or Shake256/512 both have $2^{256}$ collision resistance with a 50% probability by the birthday attack. Even if you ever hash $2^{80}$ uniform random 256-bit strings then the probability of the collision is $(2^{80})^2/2^{256}/2 = 2^{160 - 256-1} = 1/2^{97}$ and this is not going to happen, and the less the data you have, the more little probability you will get.
If you ever find a collision tell the world that you will be famous. Actually, I would go for the tiny, tiny chance to find a collision in SHA256 or SHAKE128. A simple query for checking the existence of the identifier would find out the collision. There is always such checking already since you might add the same user again.
For direct hashing with SHA-256, you do not need to worry about the collisions, you need to worry about the possible leak of information, and that totally depends on how the data are transmitted and/or stored.
It is possible to use a keyed hashes if you have some HSM to protect the key. The HMAC-X is proven to be PRF if the underlying hash function is PRF. The X stands for a hash function as HMAC-SHA256.
All of the above would solve your problem without any fear.
In short: A good cryptographing hashing is enough if there is no leakage problem. Even a collision resistance is not required at all. It may suffice to use a 128-bit PRF, if the secret key is safe to be used in your application.


Large primes p and q for RSA I am writing a high-school paper on textbook RSA (the mathematical aspect only). Many definitions of the RSA method start off with saying that one should:

Generate two large random (and distinct) primes p and q, each roughly the same size
(http://cacr.uwaterloo.ca/hac/about/chap8.pdf, page 286)

My question is: what does 'large' imply? How many digits - is there a 'limit' to the amount of digits for an suitable prime? In some books they talk about 'bits' and 'strings': I still do not understand what they mean. Please clarify.
Another question: What does distinct mean? What does it imply.
Thank you in advance

My question is: what does 'large' imply? How many digits - is there a
  'limit' to the amount of digits for an suitable prime?

A prime $p$ is called large in this case if factoring the multiplication $pq$ with a similar-sized prime $q$ prime is considered infeasible.  Usual sizes of the primes include $2^{1024}$ up until $2^{2048}$. For the recommended size of the modulus (which is roughly twice as long as the primes) refer to keylength.com.
There's no hard limit to the size of the RSA-primes, as there are infinitely many primes and any two will do.
The soft limit is the amount of computation you want to invest to use these parameters. The larger your primes, the longer you'll take to encrypt, decrypt, verify and sign data which is undesirable in many cases. Usually this makes people chose the lowest reasonably secure size (e.g. 1024-2048 bit primes).

  In some books they talk about 'bits' and 'strings': I still do not
  understand what they mean.

Computers represent numbers as a sequence of bits ($0$ or $1$). The bitlength of a number is said to be the amount of bits ($0$s and $1$s) required to represent said number or equivalently: The bitlength of $n$ is $\lfloor \log_2(n)\rfloor +1$.
A string is generally said to be an arbitrary sequence of bits without any interpretation of its contents (f.ex. as number).

  What does distinct mean?

It means what it says: Two primes $p,q$ are said to be distinct if and only if $p\neq q$. The reason for this requirement in RSA is obviously that $n=p^2$ is easy to factor.


Differences between ECIES and DHIES I'm studying the Integrated Encryption Scheme and I did't understand which are the main differences between ECIES and DHIES. Can someone help me ?

Thank you in advance.

ECIES is DHIES restricted to an Elliptic Curve group, when DHIES is defined for any cyclic group, including but not limited to $\Bbb Z_p^*$.

Mihir Bellare writes on his web page on DHIES: An encryption scheme based on the Diffie-Hellman Problem that it

  describes a Diffie-Hellman based encryption scheme, DHIES, (formerly named DHES and DHAES)..
  The SEC1: Elliptic Curve Cryptography, v1.0 standard by SECG includes DHIES

and SEC 1: Elliptic Curve Cryptography Ver. 1.0 (dated September 20, 2000) mentions ECIES stating that "It was proposed" in that article, referenced under the old name DHAES. SEC 1 Ver. 2.0 references that article under the new name DHIES. Both versions of SEC1 are elliptic about the origin of the name ECIES.

Update: I read in Victor Shoup's A Proposal for an ISO Standard for Public Key Encryption (version 2.1 dated December 20, 2001) that there was ECIES as proposed in P1363a (as drafted July 21, 2001), and ECIES-KEM, with only the later secure against adaptive chosen ciphertext attack (thru some compatible restriction).

The P1363a rationale (as drafted July 16, 2003 shortly before adoption) clarifies:

  C.3.5 For the DL and EC families, why was the DL/ECIES encryption scheme selected?
  Several proposals on DL and EC encryption schemes were presented to the P1363 working group during the development of IEEE Std 1363-2000. None of the proposals was considered mature enough to include in IEEE Std 1363-2000 and it was expected that a suitable encryption scheme would be established during the P1363a effort. The DL/ECIES scheme has emerged as a common reference in several other standards efforts, including ANSI X9.63 [B12] and SEC-1 [SEC-1], with accompanying security analysis, and is thus considered appropriate for the amendment. DL/ECIES has two modes: non-DHAES mode, which is compatible with ANSI X9.63 and SEC-1 but does not have the full set of security properties of the DHAES scheme on which it is based (see Abdalla, Bellare, and Rogaway [ABR98]); and DHAES mode, which has the full set. (..)

In the end my reading is that draft DH(A)ES is history, DHIES never had issues, and ECIES is its restriction to an Elliptic Curve group.


pairing parameters in PBC library I would like to know what are the pairing parameters of PBC library and what are they used for? Here an example where they are used.

I noticed that we can give any file in the param subdirectory. Is there any difference or change if we use one file unstead of another?

the parameters define which curve is used, which has consequences on security and efficiency.

To decide which curve type you need, go to section 8 of the PBC manual and read the paper "pairings for cryptographers"

then PBC provides functions to create your curve (i.e. param files):
https://crypto.stanford.edu/pbc/manual/ch05s01.html

But you can skip this step by directly using one of the curves already provided in the param directory.


Will SHA1 or Other Hash Functions Ever Contain Quotes I feel foolish asking this, but will the hash generated by SHA-1 or other encryption methods ever have the possibility of containing a quote? Or any other characters that may be escaped such as ", ', and \

I am attempting to make a non-MySQL database to hold values such as hashes (and yes, I am aware that it is not the most secure option for holding things such as passwords; this is just a private endevour for fun). I was planning to store the tables and data in JSON files, so that is why I need to know if I will need to escape some characters before storing the data.

SHA-1 (and, in general, any modern cryptographical method) will generate an arbitrary bitstring.  The bit string 0x22 (the ASCII code for double quote) is as probable as any other bitstring.

You could attempt to detect (and escape) such byte values; another possibility is convert the bitstring into hex or base-64; those have a deterministic size, and may be a bit easier to place into the database.


Attack XOR encryption of binary data compressed by zlib with known key length (very short key) I am trying to break a packet format. The packet format simply packs several files into one big file. The file contents are plain. But the index data which contain offsets, file sizes and filenames are encrypted. The index data are about 1 KB and compressed by zlib (the DEFLATE algorithm with no zlib or gzip wrapper), and then XOR encrypted. In other words, the key is concatenated with itself many times to get a keystream of equal length as the zlib-compressed data, and then the zlib-compressed data is XORed with this keystream (like a Vigenère cipher).
I know the key length is 8 bytes. Is it possible to decrypt the data?

If you have known plaintext, namely one input file that is known in its entirety, this is trivial to break.  So I'll explore methods that might lead to a break, if you don't know what's in the input file that was compressed.

I suggest that you start by analyzing the DEFLATE stream format carefully (see also these handy notes).  This will probably help you derive some consistent relationships that the first handful of bits of the DEFLATE stream must satisfy.

On first glance, it looks to me like the beginning of the DEFLATE stream has the following structure:

As Stephen Tousot explains, in normal operation the first 3 bits of the DEFLATE stream are likely to be 110.  (You may want to double-check this with the compression program you are using.)
The next three fields are HLIT (5 bits), HDIST (5 bits), and HCLEN (4 bits).  I suggest that you take a bunch of sample inputs that would be typical for your application, compress them with the compression implementation you're using, and look at the typical range of values for HLIT, HDIST, and HCLEN in the resulting DEFLATE stream.  I suspect you may find that not all values are equally likely.
After the aforementioned 17 bits is a chunk of 3*(HCLEN+4) bits, which is interpreted as a sequence of 3-bit values.  If I understand the DEFLATE algorithm correctly (and I might not), if you permute these appropriately using a fixed permutation found in the DEFLATE specification and ignore all 000-values, then the remaining 3-bit values should be in sorted order.  This provides an additional constraint on possible values for those bits.
Then there's some more stuff that I'm ignoring right now.

For example, if HCLEN=15, then the first three items above account for the first 74 bits of the DEFLATE stream.  And, if I understand correctly, above structure imposes some consistency relationships on the bits: not all possible 74-bit sequences are possible (and not all possible ones are equally likely).

Now, I think you could use the following procedure to try to recover the key $K$.

For each candidate value of the 64-bit key $K$, xor it against the first 64 bits of ciphertext to obtain $Y = C\oplus K$, a guess at the 64 bits of the DEFLATE stream.  Check to see if $Y$ is consistent with the above-mentioned constraints.  If it is not consistent, continue on to the next candidate for $K$.
If it is consistent, then do a trial decryption of the entire ciphertext using $K$ (i.e., xor a repeated version of $K$ against the ciphertext, then decompress).  See if the resulting plaintext looks like a plausible input.  If yes, you may have found the key $K$.  If not, continue on to the next candidate.

As described, this method would take $2^{64}$ iterations of the loop.  However, I suspect you might be able to speed it up if you are a bit clever about how you check keys $K$.  Rather than iterating over all possible 64-bit values one-by-one, I think you can use a tree-like iterative-deepening method.  The idea is, roughly, if you reject a (say) 17-bit prefix of $K$ as impossible, then there is no need to try any of the keys that start with that prefix.  So, an optimized algorithm might first check all candidate values for the first 17 bits of $K$ (say) to see which ones look consistent, then for each 17-bit prefix that survives, you look to find all plausible ways to extend it by 3 bits, and so on, repeating at each step.

I don't know what the running time of this more sophisticated algorithm will be, but if you study the DEFLATE format carefully and are able to identify enough consistency checks on the first 64 bits of the DEFLATE stream, you might be able to make this attack run efficiently enough to be practical.

I realize I haven't worked out all the details for you -- I've left something for you to do on your own.  But hopefully this gets you started and gives you some ideas for a direction that might lead to a practical attack.


How is a Yubikey static password derived from the AES key? When I configure a Yubikey slot as static, it's not documented or obvious how the static password yielded by a press relates to the AES key I set.  For example:

me@mine:~$ ykpersonalize -1 -ostatic-ticket -ofixed=cccccccccccc -a00000000000000000000000000000000
Firmware version 2.3.3 Touch level 1795 Program sequence 9

Configuration data to be written to key configuration 1:

fixed: m:cccccccccccc
uid: 000000000000
key: h:00000000000000000000000000000000
acc_code: h:000000000000
ticket_flags: APPEND_CR
config_flags: STATIC_TICKET
extended_flags:

Commit? (y/n) [n]: y

me@mine:~$ cat >/dev/null  # and do a short press...
ccccccccccccncejelrjvjvvciclerknrlihnteljrcb

Where does the key-based part (ncejelrjvjvvciclerknrlihnteljrcb) come from?

The password is the result of encrypting the fields used for OTP, but with fixed values:

me@mine:~$ ykparse 00000000000000000000000000000000 ncejelrjvjvvciclerknrlihnteljrcb
Input:
  token: ncejelrjvjvvciclerknrlihnteljrcb
          b0 38 3a c8 f8 ff 07 0a 3c 9b ca 76 bd 3a 8c 01
  aeskey: 00000000000000000000000000000000
          00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Output:
          00 00 00 00 00 00 ff ff ff ff ff ff ff ff 0f 2e

Struct:
  uid: 00 00 00 00 00 00
  counter: 65535 (0xffff)
  timestamp (low): 65535 (0xffff)
  timestamp (high): 255 (0xff)
  session use: 255 (0xff)
  random: 65535 (0xffff)
  crc: 11791 (0x2e0f)

Derived:
  cleaned counter: 32767 (0x7fff)
  modhex uid: cccccccccccc
  triggered by caps lock: yes
  crc: F0B8
  crc check: ok

This can be reproduced with OpenSSL:

me@mine:~$ key=00000000000000000000000000000000
me@mine:~$ fixed='\x00\x00\x00\x00\x00\x00\xff\xff\xff\xff\xff\xff\xff\xff\x0f\x2e'
me@mine:~$ modhex -h $(echo -ne "$fixed" | openssl enc -aes128 -nopad -K $key -iv "" \
                       | hexdump -v -e '/1 "%02x"')
ncejelrjvjvvciclerknrlihnteljrcb

You can't quite reproduce it with ykgenerate because that tool always includes a genuinely unpredictable random: field.


Multidimensional meet-in-the-middle attack on AES Is an MD-MITM attack possible for AES? As I know, we can break 2 rounds of AES. So we could apply the MD-MITM attack 5 times. This should significantly reduce the security of AES.
What stops us from these kinds of attacks? Why GOST was broken with such method and AES not?

Why GOST was broken with such method and AES not?

MD-MITM attacks have been published e.g. against KATAN and GOST in https://eprint.iacr.org/2011/619. The authors stated that their attack is "suitable for lightweight ciphers with simple key schedules and block sizes smaller than key lengths". Another reason and the answer for this question is, that the attacked ciphers in that paper had a block lengths up to 64 bit, while AES has a block length of 128 bit and the space–time tradeoff would require too much space.


What communications security protocols exist that aren't based on PKC? Lets say that you have two devices that need to communicate in a secure manner. These devices can share secrets before communication takes place (This sharing of secrets occurs over another secure channel). Furthermore,
these devices can not use public key cryptography.

Assuming that underlying cryptographic primitives are soundly implemented, what communications security protocols exist that can secure such communications at both the message level (authentication, encryption, and integrity) and the protocol level (guard against replay attacks and so on)?

The answer is to your problem is called Transport Layer Security with Pre-Shared Keys (TLS-PSK) and is widely available in implementations.

TLS-PSK offers PKC aided and non-aided key-exchanges, with the former being recognizable by the DHE, ECDHE, RSA parts in their names. This means you want to look for the TLS_PSK_WITH_* cipher suites.

In particular I'd recommend you using TLS_PSK_WITH_AES_128_GCM_SHA256 (or the 256/384 version thereof). If your platform doesn't offer SHA-2 and / or AES-GCM your best choice would be TLS_PSK_WITH_AES_128_CBC_SHA.

Note that TLS-PSK will take care of all the security issues, with the protocol (TLS v1.0, v1.1, v1.2, v1.3, newer versions are preferrable, v1.3: draft version 10 linked) taking care of the protocol level issues using the cipher suites for the message layer issues.


Mathematical calculation to determine probability of observing the character space used for a set of string inputs I am designing some methodology to determine the composition of wireless router security passphrases in terms of the character space used to generate them.

The problem I am having is I am unsure what formula or technique I can use to calculate the number of strings I would need to observe in order to determine the full character set which was used to generate these passphrases.

I was thinking along the lines of the birthday paradox but I am not sure if this is applicable for my problem.

The algorithm to deduce the string composition is simple: the passphrase strings will be read and every character will be processed. If the character hasn't been seen before, it will be added to a temporary array and if the character has been seen before, it won't be added. Thus, at the end the array will store all the unique seen characters from the processed strings (the passphrases in question).

Let's say the character space that the router manufacturer used to generate these passphrases was 62 different characters in size. For example:

abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789

(a-z lowercase, A-Z uppercase and 0-9)

These generated passphrases are just strings like these for example:

2UAYnCtL
YR3kLX49
MJLDJIgt
xouq9KOV

Considering that each passphrase is 8 characters in length and that these passphrases are randomly generated by picking characters at random from that example character space mentioned above, how many strings will my algorithm need to see before it can build a complete representation of the above mentioned character space ?

Or in other words how can I determine the minimum number of strings which need to be observed in order to have a high probability (or close to 1 probability) of my algorithm being able to recreate that character space mentioned above ?

Please let me know if anything is unclear. Thanks for your input !

Well, assuming that the router selects each character of the password in a uniformly and independently distributed fashion, then the probability of an individual character not being a specific character $c$ is:

$$1 - 1/62$$

(where the alphabet size is 62).

Hence, if we generate $n$ characters, the probability $c$ never occurs is:

$$(1 - 1/62)^n$$

Now, we have 62 possible values of $c$, and we want the probability that all of them occur somewhere to be high (say, $>0.99$), and so we have:

$$62 (1 - 1/62)^n < 1 - 0.99$$

Evaluating this, we get $n > 537$, or 67 8-character passwords.

The exact value you obtain will depend on the size of the alphabet (which you might not know precisely when you start), and the desired failure probability.  In addition, this is pessimistic in the sense that if you see every alphabetic character other than n, it's plausible that n can occur (and you just didn't happen to see it).  On the other hand, the router may be programmed to avoid the 1, I, l characters (because they may be easily confused in some fonts), and so that might not be quite so dreadfully pessimistic.

Pedants will note that this analysis isn't precisely correct (as the probabilities aren't independent; each character of the password is some $c$, and so multiplying the nonoccurance probability of each individual character by the number of characters isn't actually justified), however I believe that it's close.


How can I handle the situation if key size is less than 64 bits in DES? If the data is not a multiple of 64 bits, then I can use padding. I know that it is not secure. But if the key is less than or more than 64 bits, should I ask the user to enter the key again, or should I pad / truncate it?

A DES key is, by definition, a (pseudo)randomly chosen sequence of 8 × 7 = 56 key bits, plus 8 parity bits,* for a total of 64 bits.  If what you have isn't 64 bits long (with the appropriate parity bits), then it's not a DES key, but something else (e.g. a passphrase).

To turn that "something else" into a DES key, you need a key derivation function (KDF).  There are several standard and commonly used ones, most of them based on cryptographic hash functions.

If the "something else" you have might contain less than 56 bits of entropy (which is likely, if it's e.g. a user-chosen password), then you will most likely want a key stretching KDF such as PBKDF2.  Such KDFs are deliberately slow (and their slowness is adjustable) to make brute force guessing attacks harder.

Also, please note that the 56-bit key size of plain DES is itself too short to resist brute force attacks using modern hardware, making DES insecure.  If you can't use a more modern cipher like AES, you should at least use Triple DES, which doubles the effective key size of DES to 112 bits (at the cost of also tripling the work needed for encryption).

(Ps. Of course, the "something else" could also be a corrupted DES key.  In that case, you should just reject it, and report the error to the user who supplied the key.)

*) The standard way of storing a DES key is as a sequence of eight bytes, each consisting of 7 key bits and one redundant parity bit.  Thus, the standard form of the key has 64 bits, even though only 56 of them are actually used for cryptographic purposes.  This is a peculiarity of DES, not shared by most later block ciphers.


ElGamal Signature Scheme: Recovering the key when reusing randomness Show how if Alice uses the same value of $k$ to sign two different messages $m_1$ and $m_2$, using the ElGamal signature scheme, Eve can recover the value of $a$ from the corresponding signatures $(m_1, r_1, s_1)$ and $(m_2, r_2, s_2)$. (Note: you are allowed to assume that if $\gcd(a, n) = d$ then there are $d$ solutions to the congruence $ax \equiv b \pmod n$.)

  ElGamal Signature Scheme:

  Key Gen:

  Compute $y = g^x \;\bmod p$.

  The public key is $(p, g, y)$. The secret key is $(p, g, x)$

  Signature Gen:

  Choose a random $k$ such that $0 < k < p − 1$ and $\gcd(k, p − 1) = 1$

  Compute $r = g^k \;\bmod p$ and $s = k^{-1}(m – xr) \;\bmod{p-1}$

Thoughts: So far, I can tell that $r_1$ and $r_2$ are equal and $s_1$ and $s_2$ are closely related since the only variation is $m$.

We can relate the two equations for $s$, by solving them for $-xr$:

$$s_1k - m_1 \equiv s_2k - m_2 \pmod p$$

$$(s_1 - s_2)k \equiv m_1 - m_2 \pmod p$$

Let $a = s_1 - s_2$, then we know from the question that for $\gcd(a, n) = d$ there are $d$ solutions for $k$.

Now the forger can compute $g^k$ for each solution to k, until $r$ is found.

Then compute $xr \equiv m_1 - ks_1 \pmod{p-1}$

There are $d' = \gcd(r, p-1)$ solutions for $x$.

The forger can compute $g^x$ for all the $x$s found until she finds $y$.

Once she has $y$ she knows the proper $x$ which can be used to find $m_1$ and $m_2$.

How does this look?

That looks about right.  Assume we have two messages $m_1$ and $m_2$ and the corresponding signatures $(r,s_1)$ and $(r,s_2)$ generated using the same $k$ (where $r=g^k$ is thus the same for both signatures).

If we could assume that $s_1 - s_2$ and $r$ were invertible modulo $p-1$, we could simply compute

$$ k \equiv (m_1 - m_2)(s_1 - s_2)^{-1} \mod p-1 $$

and then

$$ x \equiv (m_1 - ks_1)r^{-1} \mod p-1. $$

Of course, that's not necessarily the case, but we can still first solve the congruence

$$ k(s_1 - s_2) \equiv (m_1 - m_2) \mod p-1 $$

for $k$, check which of the $\gcd(s_1-s_2,p-1)$ solutions yields the correct $r = g^k$, and then solve

$$ xr \equiv (m_1 - ks_1) \mod p-1 $$

for $x$ and check which of the $\gcd(r,p-1)$ solutions gives the correct $y = g^x$.

Note that, in the ElGamal signature scheme, the only operations done modulo $p$ are the exponentiations (and the final multiplication $y^r \cdot r^s$ in the verification step); everything else is done modulo $p-1$.

This makes sense when you realize that we're really working in two distinct $(p-1)$-element algebraic structures: the ring of integers modulo $p-1$ and the multiplicative group of integers modulo $p$.

We may usefully view the latter of these as a module over the former, with exponentiation as the "scalar multiplication".  Also, since the two structures have the same number of elements, we can identify the canonical (i.e. least non-negative) representations of their elements simply by identifying 0 with $p-1$; this is what we do implicitly during signature generation, when we first calculate $r = g^k \pmod p$ and then use it to calculate $s$ modulo $p-1$.

(Actually, the case $r = p-1$ is impossible anyway, since it would imply that $r^2 \equiv 1 \pmod p$, and thus that $2k \equiv 0\pmod{p-1}$, and so $\gcd(k,p-1) \ne 1$.  The case $r=1$ can be similarly ruled out, so we always have $1 < r < p-1$.)


The difference between being not strongly collision resistant, and not weakly collision resistant? So I understand the two concepts:

(Strong) collision resistance: it is infeasible to find a pair $x \neq x'$ such that $h(x) = h(x')$
Weak collision resistance / 2nd-preimage resistance: for all $x \in D$ it is infeasible to find $x' \neq x$ such that $h(x)=h(x')$

But I'm confused as to how to negate the two. This is what I end up with:

h is not (strongly) collision resistant if: it is feasible to find a pair $x \neq x'$ such that $h(x)=h(x')$
h is not weakly collision resistant (not 2nd-preimage resistant) if: there exists $x \in D$ such that it is feasible to find $x' \neq x$ such that $h(x)=h(x')$

These two negations seem the same. Suppose I show h is not (strongly) collision resistant, because of $x \neq x'$ where $h(x)=h(x')$. Surely this then shows h is not weakly collision resistant when the $x \in D$ is $x$ or $x'$? (sorry for the different uses of $x$ there!) A similar argument would say that any $h$ that is not weakly collision resistant is strongly collision resistant. But it's absurd that the negations of the two concepts are the same! Where have I gone wrong?

I prefer using definitions that explicitly specify who does what.

Weak collision resistance: After Bob creates some message x1, it is "computationally infeasible" for an attacker Mallory to compute some other message x2 such that h(x1) == h(x2).

Strong collision resistance: It is "computationally infeasible" for an attacker Mallory to find any two messages x1 and x2 such that h(x1) == h(x2).

The negations would be:

Weak collision vulnerability: After Bob creates some message x1, it is "computationally feasible" for an attacker Mallory find a bound collision -- to compute some other message x2 such that h(x1) == h(x2).

Strong collision vulnerability: It is "computationally feasible" for an attacker Mallory to find a free collision -- to find any two messages x1 and x2 such that h(x1) == h(x2).

Specific examples:

The "XOR checksum" (and each non-cryptographic hashe in general) is weak collision vulnerable -- and therefore is strong collision vulnerable.
The MD5 hash is now known to be strong collision vulnerable, but (as far as we know) it still has weak collision resistance.
The SHA3 hash (as far as we know) has strong collision resistance -- and therefore also has weak collision resistance.

Strong collision resistance implies weak collision resistance, in the random oracle model,
as Vijay Ganesh points out in
"Cryptographic Hash Functions".
(Vijay apparently thinks the term "infeasible" is useful in this context).

Klaus Schmeh apparently made up the "bound collision" and "free collision" terminology for the book "Cryptography and Public Key Infrastructure on the Internet".

Therefore,
weak collision vulnerability implies strong collision vulnerability, in the same model.

One might argue that strong collision vulnerability implies weak collision vulnerability:
After Mallory creates two messages x1 and x2 that collide,
it is theoretically possible that Bob might create a message exactly the same as x1, and then Mallory could easily remember the x2 message that Mallory generated earlier.
In practice, any protocol where Mallory influences Bob into using a message generated by Mallory (a chosen-plaintext attack) is already considered broken in other ways.
In practice, we assume that, without such influence, the probability that Bob coincidentally picks such a message generated by Mallory is negligible.

I suspect otus is alluding to the fact that people who work with keyed hash functions have their own definitions for these terms that are incompatible with the definitions used by people who work with unkeyed hash functions.
Shoichi HIROSE mentions this conflicting terminology in the introduction of his 2005 paper "Weak Security Notions of Cryptographic Unkeyed Hash Functions and their Amplifiability".


For perfect secrecy, does the keyspace need to be uniform? The definition of perfect security is just that:
$Pr(M =m | C=c) = Pr(M=m)$. We can prove that one time pad is perfectly secure for any distribution on a message space $M$, and it happens to be that the keyspace $K$ has a uniform distribution. Does that have to be true?

For example, let's say $M= \{0 \}$, $K=\{ 0,1 \}$ where $0$ is chosen with probability $p$ and $1$ chosen with probability $1-p$. Then we could have $c = m \oplus  k$, and $c=0$ with probability $p$ and $c=1$ with probability $1-p$. Is this perfectly secure if $p \neq \frac12$?

The answer to your question in the title is No.
For example, let's modify a little the one-bit OTP considered in your question description (with a one-bit message space $M=\{0,1\}$). Instead of using a one-bit key $K=\{0,1\}$, we can use a two-bit key $K=\{00,01,10,11\}$ and discard its last bit when doing the xor. It's easy to see that perfect secrecy holds as long as the first bit satisfies uniform distribution, while the 2-bit key distribution is rather arbitrary.
Therefore, for perfect secrecy, the key distribution does not have to be uniform. Actually, this statement should be true for any kind of security. Security-wise, what really matters is the key entropy rather than the exact key distribution. We see uniform key distribution assumed almost everywhere because it is convenient to use (a weird key distribution could cause problems, e.g., for usability) and it gives us maximum key entropy.
Note that though seemingly contradictory, kelalaka's answer is also true; but it considers only the classical use of OTP where the keyspace matches the message space. In this case, the key distribution has to be uniform because a non-uniform key distribution xoring the message distribution will not generate a ciphertext distribution that has the same distribution as the messages.


Securely send public key from client to server in RSA? I have a client and a server communicating with messages encrypted using RSA.

Initially, the client knows server's public key, but the server does not know the client's public key. Is it possible to securely receive the client's public key over a network (i.e. without a man in the middle intercepting and changing the public key the client is trying to send with their own).

I was thinking that the client can generate a random secret and then send it to the server using the server's public key for encryption. Then the server can decrypt the secret, use it as a key for AES, and echo it back (this time encrypted with AES). The client then verifies that the decrypted secret is the same as the one it sent.

I'm scratching my head trying to figure out if this is secure, and how I should incorporate hashing to verify the integrity of the data.. Would this even work?

In this protocol:

client draws a random AES key $K_\text{SES}$ (I'll make it 128-bit);
client enciphers $K_\text{SES}$ using the server's RSA publickey $K_\text{PUB}$, and sends the result $\text{RSAES}_{K_\text{PUB}}(K_\text{SES})$ (note: RSAES designates RSA encryption with some unspecified padding e.g. per one of the two fine encryption schemes defined in PKCS#1);
server receives the alleged $\text{RSAES}_{K_\text{PUB}}(K_\text{SES})$ and deciphers it into the alleged $K_\text{SES}$, using the server's RSA private key $K_\text{PRI}$; servers stops if that fail;
server enciphers $K_\text{SES}$ using AES key $K_\text{SES}$, and sends the result $\text{AESENC}_{K_\text{SES}}(K_\text{SES})$;
client receives the alleged $X=\text{AESENC}_{K_\text{SES}}(K_\text{SES})$, deciphers it using the original AES key $K_\text{SES}$, and aborts if $\text{AESDEC}_{K_\text{SES}}(X)\ne K_\text{SES}$;
presumably, $K_\text{SES}$ is then used as a session key; I'll assume as key to some unspecified mode of AES for confidentiality, and perhaps something (not even suggested) for authentication; at least the client's public key is sent using that encrypted channel.

A 5-minute non-exhaustive analysis reveals various serious issues, limitations, and risks with this protocol:

there is no explicit protection against replay of a session to the server; in many circumstances this is a gapping hole!! (clarification: replay to the server is simply sending the messages sent by a genuine client and recorded in an earlier session, including any IV, and would work in the absence of some challenge-response from the server, which is currently not described);
it was imprecisely specified (it still is, in particular regarding error handling and time-outs), making a detailed analysis impossible;
it is not peer-reviewed, thus must be presumed unsafe;
as any protocol starting without secret credentials on the client side, it can not authenticate the client;
as any known non-quantum protocol, it can not prevent Eve-in-the-middle from intercepting or/and relaying the messages, but that is not by itself a security issue;
there is no protection against denial of service of the server by multiple connections, replayed or not;
there are Bleichenbacher padding oracle attacks on some bad implementations of step 3. on the server side (typically when using RSAES-PKCS1-V1_5), that in the worst case could leak $K_\text{SES}$, and then the sky is the limit;
if somewhat Eve-in-the-middle manage to abuse the implementation of step 6. on either the client or server side as a decryption oracle, then the possibility exists that she can obtain the decryption of $X=\text{AESENC}_{K_\text{SES}}(K_\text{SES})$ using the active key $K_\text{SES}$, giving her $K_\text{SES}$, with similarly devastating effect (clarification: if the encryption uses CBC, the attack could consist is replacing one genuine ciphertext block with with $X$ obtained from step 4. and somehow obtain the corresponding plaintext block, that would yield $K_\text{SES}$ after an exclusive-or with the previous ciphertext block ; that should not be possible in an authenticated link, but not enough details about that are given);
if $K_\text{PRI}$ ever leaks, the protocol is entirely insecure after the leak with no stated provision to recover from that;
if $K_\text{PRI}$ ever leaks, the confidentiality of past recorded communications is compromised; contrast that with protocols offering forward secrecy;
update: there is no stated safeguard to reduce the risks resulting from a poorly seeded or otherwise bad RNG being used at step 1., which times and times has occurred on the field;
update: at step 6. the client's public key is sent enciphered, when we really need authentication, not really described.


Perfect Secrecy and Message distribution I have been trying to come up with a proof of the following statement,
Suppose a cryptosystem achieves perfect secrecy for a particular plaintext probability
distribution then Prove that perfect secrecy is maintained for "any" plaintext probability distribution.
Well I know that the perfect secrecy scheme is independent of plaintext distribution, but how to prove the above statement? Any help would be appreciated.

I don't think the statement is true, and I will come to a counterexample later.
Formalization
One possible formalization of the statement could look like this:
Let $\mathcal{M}$ be the message space, and $\mathcal{C}$ the ciphertext space.
We define two arbitrary distributions over $\mathcal{M}$: $M_a$ and $M_b$,
where $\Pr_{m \in \mathcal{M}}[M_a = m] = p^\mathcal{M}_a(m)$ and $\Pr_{m \in \mathcal{M}}[M_b = m] = p^\mathcal{M}_b(m)$.
Additionally we need distributions over $\mathcal{C}$: $C_a$ and $C_b$ defined analogously.
An encryption scheme $\Pi = (\mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec})$ is perfectly secret with respect to the distribution defined by $M_a$ if:
$\forall m\in\mathcal{M}, c\in\mathcal{C}. \Pr[M_a=m] = \Pr[M_a = m\ |\ C_a = c]$ and $\Pr[C_a = c] > 0$, to avoid conditioning on an event with zero probability.
We want to show that given $\Pi$ fulfills the above definition, then it also fulfills the same definition with $M_a$ replaced by $M_b$.
Attempt to Prove
I first attempted (but did not succeed) at proving the statement.
My attempt looks like this:
First show that it suffices to show that the ciphertext distributions are equal
(i.e. that $\Pr[C_a = c] = \Pr[C_b = c]$ holds).
Then show that the ciphertext distributions are equal.
However, I was not able to prove these statements.
Refutation
I believe I have found a counterexample.
Lets first look at the definition of perfect secrecy:

There are two things I would like to point out:

the definition requires independence of the message from the ciphertext for any plaintext distribution, so your statement deviates from this requirement.
the equation only needs to hold for $\Pr[C = c] > 0$

Counterexample
Let $\mathcal{M} = \mathcal{C} = \{0,1,2,3\}$.
Further, let our key-space be $\mathcal{K} = \{0,1\}$.
We define an encryption scheme that is perfectly secret for the messages $0$ and $1$, but not for $2$ and $3$:
\begin{equation*}
\mathrm{Enc}_k(m) =
\begin{cases}
k \oplus m & \text{if $m \in \{0,1\}$}\\
m & \text{if $m \in \{2,3\}$}\\
\end{cases}
\end{equation*}
Additionally, we define a message distribution as follows:
\begin{equation*}
\Pr[\mathcal{M} = m] =
\begin{cases}
\frac{1}{2} & \text{for $m \in\{0,1\}$}\\
0 & \text{for $m \in\{2,3\}$}\\
\end{cases}
\end{equation*}
We now show, that (1) $\Pi$ is perfectly secret with respect to our message distribution.
Then (2) we show that it is not perfectly secret for all message distributions.
1.
We need to show that
$\Pr[M = m] = \Pr[M = m\ |\ C = c]$.
We don't need to show this for $c \in \{2,3\}$ since for our message distribution, $\Pr[C = 2] = \Pr[C = 3] = 0$.
For $c \in \{0, 1\}: \Pr[M = m\ |\ C = c] = \frac{1}{2} = \Pr[M = m]$.
Therefore, the encryption scheme is perfectly secret for the given message distribution.
2.
However, given a message distribution that assigns $2$ or $3$ a non-zero probability, the scheme is trivially not perfectly secret:
$\Pr[M = 2] \neq 0 = \Pr[M = 2\ |\ C = 3]$
Therefore the scheme is not perfectly secret for all message distributions, and thus the statement does not hold in general.
Appendix
For completeness here is the decryption algorithm:
\begin{equation*}
\mathrm{Dec}_k(c) =
\begin{cases}
c \oplus k & \text{if $c \in \{0,1\}$}\\
c & \text{if $c \in \{2,3\}$}
\end{cases}
\end{equation*}
and the key generation:
\begin{equation*}
\mathrm{Gen}() = k \stackrel{sample}{\leftarrow}\{0,1\}
\end{equation*}