Why does a padding block exist for ECB and CBC modes? In ECB and CBC mode, the size of cipher text is more than the plain-text size by one padding block.

From what I read, ECB does a simple encryption to each 64 bit block of a Plain text, and produces an equivalent 64 bit cipher text block. Then how does an extra padding block exists?

In ECB and CBC mode, the size of cipher text is more than the plain-text size by one padding block.

Block ciphers can only permute plaintext blocks and produce the permuted output ciphertext blocks. As such, modes of operation are responsible to make sure that the messages in the target messages space can be encrypted and decrypted given this restriction.

Now for a generic cipher you would expect to be able to encrypt / decrypt any message or any size. ECB and CBC mode do not provide this functionality by themselves. They need to be paired with a deterministic padding mode such as PKCS#7 compatible padding to operate on messages of any size.

Such deterministic modes must at least add a single bit of padding as otherwise the padding cannot be distinguished from the last bit of the message. Therefore such deterministic padding modes add one bit to N bits of padding, where N is the block size.

For these deterministic modes a full "padding" block is added if the message is already a multiple of the block size. Otherwise the last block contains a mixture of the plaintext message and padding.

If a fully generic cipher is not required you can use many different methods:

just requiring that the message size is a multiple of the block size (the key size of symmetric keys is often a multiple of the block size, so this often works for key wrapping);
nondeterministic padding methods such as zero padding (where the message should commonly not end with zero bits, or contain the message size internally);
ciphertext stealing, which poses constraints on the minimum message size / IV.

Notes:

many implementations are lazy and allocate a buffer size of the message size + 1 block for the ciphertext, this is however a waste of space.
AES-192 keys are not a multiple of the block size, which makes key wrapping more awkward.
deterministic modes require at least one padding bit, but usually implementations only handle bytes, so the padding would consist of 1..N/8 bytes.
Most other modes (CTR, GCM, OFB, CFB) are streaming modes and do not require padding to be able to encrypt messages of any size.


Does the elliptic curve (EC) cryptosystem outperform RSA and DL cryptosystems? Throughout the literature, it is stated that EC cryptosystems outperform RSA and Discrete logarithm cryptosystems, but I cannot understand how ECC would be more efficient than RSA and DL in terms of computation and storage.

Is there any pragmatic performance analysis comparing these cryptosystems so that I can understand?

Simply put, elliptic curves allow you to use smaller fields.

Consider Diffie-Hellman: given $p$, $g$ and $x$, you compute $g^x \mod p$. To ensure security, you must use values of $x$ and $p$ which are large enough to defeat known attacks. In practice, $x$ will need to be at least 160-bit long, while $p$ will be a 1024-bit prime.

Now, the elliptic curve variant: you have a curve $E$ where point coordinates are elements of a field of cardinal $q$, and you compute $xG$ for an integer $x$ and a conventional point $G$. To achieve security, you need $x$ to be a 160-bit long integer, as with the plain DH case; however, it suffices that $q$ is also a 160-bit integer (e.g. a 160-bit prime). Computing $xG$ will require roughly ten times as many field operations than computing $g^x$, but these operations will be performed in a much smaller field, more than 6 times smaller. Since the elementary cost of a field operation is, in practice, quadratic in the field size, you infer that field operations modulo $q$ will be about 40 times faster than field operations modulo $p$. Even if you do ten times as many, you are still 4 times faster with the curve than with plain DH.

The performance ratio increases with higher security levels (e.g. a 224-bit curve will give you roughly the same security than a 2048-bit plain DH key, leading to a factor of more than 8 in favour of the curve).

For storage, elliptic curves are also better: a 224-bit curve point can be represented over 225 bits (and you can often lower that to 224, at least for Diffie-Hellman), whereas a 2048-bit integer uses, well, 2048 bits.

The RSA public operation (raising to the power $e$ modulo $n$, where $e$ is the public exponent) is still a tad faster than public key operations with ECC-powered algorithms, but for private key operations, curves win hands down (if properly implemented, of course).


How important is the size of the public key (for a given security level)? I've read about different signature schemes which for the same bits of security differ largely in the size of the public key: The ones proven in the standard oracle model perform worse than the ones proven in the random oracle model. I understand that a difference in the size of a signature is important in case the signature is sent along the data which was signed.

However, what are the negative effects of a large public key? What comes to my mind is that this could be an issue in embedded hardware which is limited in storing capacity. Might this be an issue in other scenarios as well? E.g. are there protocols in which public keys are included in packets and thus take up important space?

Larger public keys (in the same scheme) lead to

larger signatures
larger certificates
slower signature computation
much slower key generation

All of these might be a problem, especially for embedded devices, as you already mentioned.
As for your last question: Yes, there are a lot of protocols which transfer a public key, usually in the form of a (X.509) certificate. A TLS handshake is just the most prominent example.


Public key encryption and big files with NaCL I am trying to encrypt big files using NaCL (actually PyNaCL) - see http://nacl.cr.yp.to/box.html

After reading some docs, I came up with this prototype :

Bob wants to send a big file to Sarah. They both have a public/private key pair.

set "position" to 0
for each 256ko file chunk

generate a random nonce
append to the chunk 10 bytes containing position zfilled with zeroes
encrypt the chunk using crypto_box (using Bob private key and Sarah public key)
increment position

When Sarah gets the encrypted chunks:

set "position" to 0
for each encrypted chunk

decrypt the chunk using crypto_box (using Bob pub key and Sarah priv key)
extract the position and assert it's equal to "position"
increment position

prototype code here : https://github.com/tarekziade/fxakeys/blob/master/fxakeys/crypto.py#L119

What do you think ?

You're vulnerable to a chunk-level replay attack, where Mallory (the man-in-the-middle) can mix and match chunks from different files, to produce a file that appears to be from Bob but which Bob never wrote.

Bob sends two messages to Sarah. Let's say the first message comes in chunks A1 and A2, and the second message comes in chunks B1 and B2.
Mallory intercepts both messages. She then constructs the new message A1+B2.
Mallory sends the forged message to Sarah. The boxes open with Bob's key, and the sequence numbers look good.

Since Mallory can forge a message, this scheme fails to provide authenticity.

You could fix this problem in a couple ways. One way would be to put another token inside each chunk, next to the position bytes, that's shared by all the chunks and unique for each message. Then in addition to verifying the position, the receiver would have to check that this identifier matched the previous chunks.

Another approach would be to use NaCl's nonce to do this for you. (Since after all, a "unique token for each message" is sort of what a nonce is.) If you use 16 random bytes (shared by all the chunks) plus an 8-byte counter as your nonce, you can avoid nonce reuse and also prevent the chunk-swapping replay attack. This saves you some space because you only have to transmit the 16 random bytes once, and it's also safer: a forged plaintext will never be decrypted at all, so it's impossible for an implementation to somehow forget to check the tokens. This sort of use case is why NaCl was designed with a large nonce.

Edit: Adam Langley has a post on this: https://www.imperialviolet.org/2015/05/16/aeads.html


What are methods of hash classification by finding patterns? I have a long set of hashes (long hashes, long set) generated with the same algorithm. And for each hash I know that it belongs to one of two groups.

Are there any methods of hash analysis, that allow to determine with some probability which group (any) given hash belongs to?

update:

A simple example: I have a long set of 64 bit numbers. Some of them are less than 2^40. And these belong to group A. All the rest belong to group B.
I calculate SHA of each. Then I analyse all SHAs with a magic algorithm trying to find a rule determining the group from given SHA with maximum possible accuracy. From other point of view a magic algorithm measures hash efficiency in some way. I do not know how to start with such task, and whether there are any known algorithms performing similar tasks.

For your example, sure there is:

Precalculate the SHA hash of every number less than $2^{40}$.  Store those hashes in a database.
To check if a hash belong to a number less than $2^{40}$, look it up in the database.  If you find it, the answer is yes, otherwise no.

Sure, that'll take a bunch of precalculation and a rather large database, but it's quite possible to do with modern hardware.

You could optimize the database size a little, e.g. down to 80 bits per entry by only storing the first 40 bits of the hash and the 40-bit number that produced it, letting you verify the match by hashing the number.  Or you could even store just, say, the first 32 bits of each hash and a list of the all the (256 or so) numbers that produced it, getting down to only slightly over 40 bits per entry at the cost of 256 hash computations per lookup on average.  If you don't mind some occasional false positives, even more impressive space savings are possible e.g. using a Bloom filter.

In the general case, though, assuming that:

the groups you wish to distinguish are large enough that precalculating the hashes of all (or even most) elements of either of them is not practical, and
the definitions of the groups don't have anything to do with the hash function used (i.e. you may not choose "strings whose hash begins with a zero" as one of the groups),

then it is generally not feasible to determine which group a string belongs to just from its hash.

Note that resistance to this kind of "generalized preimage attack" does not follow from the standard preimage and collision resistance properties that a secure cryptographic hash is expected to satisfy.  Still, if anyone were to find an efficient distinguisher like that for a widely used hash, that would certainly be considered by most cryptographers a notable attack on the hash function.


Why is padded RSA not CCA-secure? Why is the padded RSA construction given in the picture not CCA secure？

The (CCA-related) problem of this padding scheme is that it lacks a failure condition, i.e. a ciphertext which a decryption oracle will refuse to decrypt.

Now first for the chosen ciphertext attack which exploits RSA's homomorphic property. Assume you want to decrypt a ciphertext $c$ that is the encryption of $m$ which is encrypted properly according to the above procedure. Assume further you have a decryption oracle which won't decrypt $c$ itself.

First you chose a random integer $1<k<N$ yourself. Next you compute $c'=k^e\cdot c \bmod N$. You send $c'$ (which clearly isn't $c$) to the decryption oracle and get $m'$ in return. You compute $(r||m)=m'\cdot k^{-1} \bmod N$ and unpad the result as in the original decryption procedure.

As was noted by poncho in the comments of this answer, my above attack assumes, that the decryption oracle will give you the full message back and not just the lower $l(n)$ bits.

To fix this we'll apply an attack I like to call "hard-core predicate attack". It bases on the fact (as can be found in Katz' and Lindell's Introduction to modern Cryptography) that the least significant bit of a RSA encrypted message is a hard-core predicate. In the book the authors outline an attack to recover a full RSA message, given only an oracle that tells them whether the message corresponding to the queried ciphertext is even. Using this method we can recover the full blinded message $m'$ using polynomially many decryption queries and afterwards proceed with the above attack. For simplicity of the description I'll assume the decryption oracle only yields the least significant bit.

First, we determine whether the current least significant bit of $m$ is $0$.
If yes, then we know the least significant bit and multiply the ciphertext with $2^{-e}\bmod N$ (which shifts the message to the right by one bit) and continue from the start.
If no, then we know the least significant bit and multiply the ciphertext with $2^{-e}\bmod N$, the second least significant bit is then the negated XOR of the least significant bit of the new ciphertext and the second least significant bit of the modulus.


Forging RSA1024 signature with e=3 where hash is right justified I am trying to understand (in the frame of exponent 3) how to calculate a "forgery" in the case where the desired result is:

xxxxxxxxxxx[...]xxxxxxxxxxxxxxxxxxxxHHHHHHHHHHH[...]HHHHHHHH

where HH = a 160 bit hash which are the least significant bytes, and xx are the remaining (1024-160) bits where I could put "garbage".

From: Is this Bleichenbacher '06 style signature forgery possible? (Or more like, why isn't it?)

I understand that the hash must either have lsbit = 1 or the there must be multiples of 0 bits in 3's to assure a cube root is theoretically possible.

(I do not have "reputation" so I cannot comment in that thread)

That is trivial as I can simply re-request the challenge and test its hash to see if the value has those characteristics.

A traditional Bleichenbacher with the hash farther toward the msbit end with garbage space available to the less significant end is trivial.

Effectively trying to find x where: $$x^3\pmod{2^{128}} = h$$

Thoughts?

When $\gcd(e, \phi(n)) = 1$, integers modulo $n$ coprime to $n$ have a unique $e$th root modulo $n$.  This is the basis of RSA.  Unlike for an unfactored RSA modulus, $\phi(2^{160})$ is easy to compute: it's $2^{159}$.

You can calculate this cube root the same way that you do RSA, essentially.  Treat $2^{160}$ as if it were an RSA modulus, with $e = 3$.  Calculate $d = e^{-1} \pmod {2^{159}}$, which is the value:

$d = 243583606221817153033947472119380503275988757163$.

Now, for numbers $h$ coprime to $2^{160}$--that is, odd numbers--you can calculate the cube root as:

$x \equiv \sqrt[3]h \equiv h^d \pmod {2^{160}}$.

Because $x < 2^{160}$, $x^3$ cannot exceed $2^{480}$, so it will not wrap modulo a 1024-bit RSA modulus $n$.  $x^3 \mod n$ as calculated by a signature verifier would retain the property that $x^3 \equiv h \pmod {2^{160}}$, and your forgery is complete.

Assuming that your hash's low bit is $1$, anyway.


ChaCha20 core vs ideal unkeyed PRP I know that the ChaCha20 core (without the initial constant) is not an ideal PRP and must not be used as such.  I also know that $\text{ChaChaCore}(0) = 0$.  Are there any other differences?

It would be extremily surprising if the ChaCha core was a permutation (as the last P in PRP), although we have no proof it is not (if it was a permutation, it would at least be one we do not known how to invert, see this question).

A better approximation is that the ChaCha core behaves as a Pseudo-Random Function with the additional property $\text{ChaChaCore}(0)=0$. When we use as part of the input a constant secret key, the ChaCha core becomes a plausible Pseudo Random Function family.

The ChaCha core has less remarkable externally visible properties than the Salsa20 core has. $\text{ChaChaCore}(0)=0$ is a simple one. There are however others, including keeping some symmetries in the input into the output; and other properties that a true PRF would not have.

In particular: by definition, $\text{ChaChaCore}(x)=P(x)\boxplus x$ where $\boxplus$ is 512-bit addition with carry removed between 32-bit chunks, and $P$ is some public permutation (with $P(0)=0$) that can be trivially inverted. It follows that knowledge of $\text{ChaChaCore}(x)\boxminus x$ is enough to find $x$, by computing $P^{-1}(\text{ChaChaCore}(x)\boxminus x)$, where $\boxminus$ is to $\boxplus$ what subtraction is to addition.


Strictly, is length(key) >= length(message) wrong for one time pads? It's a common adage that for a perfectly secret one time pad, length(key) >= length(message) must hold.  But that's wrong isn't it?  At least very sloppy maths. Isn't the strict mathematical requirement that:-

entropy(key) >= entropy(message)?

An example.  Consider a OTP used for a message in the English language.  From various studies we guesstimate that the information entropy rate of English is ~1.6 bits/character.  Lets not quibble about the exact value as anything <8 will suffice for this example. Now take a standard OTP key of random 0-255 value bytes.  That's an entropy of 8 bits/byte.  Therefore for long English OTP messages, the key can be one 1/5 of the message length and still guarantee perfect secrecy. Essentially the message could be compressed five fold and then XORed with the much shorter binary key.

And the equation is reversible.  If you encrypt binary data (say reasonably in-compressible compiled code) with a basic English alphabet, you'd need five times the length of key material compared to the message.

Clearly as the message alphabet increases, then the mathematical requirement tends towards the original adage.  But isn't my general case more accurate?

Am I wrong/confused/hungry?

Your confusion stems from a misinterpretation of a formal statement about the limitations of perfect secrecy. Let us first recall the definition

Perfect Secrecy.
An encryption scheme $(\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})$ with message space $\mathcal{M}$ is perfectly secret if for every probability distribution over $\mathcal{M}$, every message $m \in \mathcal{M}$, and every ciphertext $c \in \mathcal{C}$ for which $\Pr[C = c] > 0$:
$$Pr[M = m | C = c] = Pr[M = m].$$

Note that there is no mention of bits or bitstrings here and "length of the message" is not really well defined for a general message space.
The statement that is often informally paraphrased as

  The key must be at least as long as the message.

therefore doesn't really make any sense here. This is where you seem to be confused. The formal statement that can be proven about perfectly secret encryption schemes is the following:

Limitation of Perfect Secrecy.
If $(\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})$ is a perfectly secret encryption scheme with message space $\mathcal{M}$ and key space $\mathcal{K}$, then $|\mathcal{K}| \ge |\mathcal{M}|$.

Note that this is only a statement about the size of the key space! It makes no mention of any length.
Now, the most well known perfectly secret encryption scheme is the one-time pad, which is most commonly defined over bitstrings¹ with a message space $\mathcal{M}=\{0,1\}^n$ for some message length $n$ as well as a keyspace $\mathcal{M}=\{0,1\}^\ell$ for some key length $\ell$. In this specific case case $|\mathcal{K}| \ge |\mathcal{M}|$ indeed implies that $\ell \ge n$.

In your specific case however you used a different message space, in particular you defined $\mathcal{M}$ to be the set of "messages in the English language" which is something we would need to define more formally. We can define this for example as "any concatenation of words in the English language with total length at most $\ell$ characters".

In this case, clearly $|\mathcal{M}| < 2^{8\ell}$ and therefore obviously you do not need $|\mathcal{K}|\geq 2^{8\ell}$ but the definition never claimed otherwise. What you are defining here is simply not the one-time-pad, but a different encryption scheme with a different message space. And the same condition on the key space still holds. It is just that this does not necessarily correspond to an immediate lower bound on the length of the keys when encoded as bitstrings.

¹Technically the one-time pad can be defined over strings over any finite alphabet $\Sigma$ as long as we can define an order over $\Sigma$.


Lattice based attack on RSA Let $n=pq$ be the RSA module and at least one of $p,q$ is a weak prime.It is proved that  the number of such $1024$bit $n$ is at least $2^{759}$. With lattices we can factor these $n$ in a second (I implemented it). Are you know the methods that  are more powerful than this method?

This is not quite an answer, because what I'll discuss is only about as powerful as the attack in the question, which refers to section 3 onwards in: Abderrahmane Nitaj and Tajjeeddine Rachidi, Factoring RSA moduli with weak prime factors (preliminary 2015-05 eprint).

The method I'll discuss is acknowledged in section 2.3 of the above article. It was exposed in the seminal: Don Coppersmith, Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known, in proceedings of Eurocrypt 1996; and in section 11 of his Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities in Journal or Cryptology, 1997 (paywalled; or try blind Googling).

The idea is to consider RSA moduli $N=pq$, with $N$ of $n$ bits, $p$ and $q$ prime, perhaps $q<p<2q$; and within that consider the moduli with a "weak prime factor" $p$ having the top $n/4$ bits matching some known arbitrary value (that also works with the low bits). Using a lattice attack (that is, based on the Lenstra-Lenstra-Lovász lattice basis reduction algorithm), $N$ is factored in polynomial time, and efficiently so for common RSA key sizes.

A preliminary version of Nitaj and Rachidi article stated (page 9 below table 2) that for  $N=pq\in[2^{1024},2^{1026}]$, the $\ge2^{759}$ moduli that their new method can factor

  is much larger than the number of RSA moduli with a weak Coppersmith
  prime factor in the same interval, which is actually $N^{0.25}\approx2^{256}$.

Fact is, the authors had grossly miscounted; their exponent $256$ in this quote is too small by a factor of nearly $3$. We get $>768$ is we assume all integers are prime (which in the circumstance is a fine approximation); or $>751$ if we consider that among 513-bit integers, one in about $2^{8.5}$ is prime. So the new method is at best claimed to improve Coppersmith's by a mere $8$ bits. Further, the set of weak Coppersmith prime factors can be trivially extended by a factor of $2^k$ by varying the low $k$ bits of the known arbitrary value.

As noted by poncho, neither method is likely to succeed for randomly seeded $p$ and $q$, for there are $>2^{1008}$ RSA moduli in the interval considered, and odds that a weak one is selected by chance are entirely negligible (in the order of $2^{-248}$).

What's notable with Nitaj and Rachidi's method is that it extends Coppersmith's attack to a more flexible set (not a much wider set) of RSA moduli; and has found applications in factoring more moduli actually deployed (that have been poorly generated) than in:  Daniel J. Bernstein, Yun-An Chang, Chen-Mou Cheng, Li-Ping Chou, Nadia Heninger, Tanja Lange: Factoring RSA keys from certified smart cards:
Coppersmith in the wild aka smartfacts, initially in proceedings of Asiacrypt 2013.

Update: the issue pointed above was promptly corrected in a revised version: Abderrahmane Nitaj and Tajjeeddine Rachidi, Factoring RSA moduli with weak prime factors (2015-12-31).


Research Guidance on Elliptic Curve Cryptography I am a freshman who want to research elliptic curve cryptography.
There are a few questions I have:
Firstly, I am not sure about how I should narrow down the topic. Where should I focus on? Can I examine a specific application of elliptic curve cryptography? Or should I basically compare Elliptic Curve Cryptography and RSA algorithms.
Secondly, which prerequisite knowledge do I need? Also, do you suggest any foundational books on the topic?
Thank you

Firstly, I am not sure about how I should narrow down the topic.

It is better to ask your advisor to help you for selecting a good research topic.

Secondly, which prerequisite knowledge do I need? Also, do you suggest any foundational books on the topic?

A roadmap for learning Elliptic Curve Cryptography:

Beginner: you can learn the basic of ECC by reading Chapter 9 of Understanding Cryptography book and/or some good online tutorials and/or by ECC workshop schools.
Intermediate: for a better understanding, you can read these three books: Elliptic Curves: Number Theory and Cryptography, Guide to elliptic curve cryptography and Handbook of elliptic and hyperelliptic curve cryptography.
Advanced: for a deep dive into the mathematics of elliptic curves, you can read Joseph H. Silverman's books.
Implementation: Implementing Curve25519/X25519: A Tutorial on Elliptic Curve Cryptography by Martin Kleppmann.
Research: for selecting a research topic, you can read last research papers of the Workshops on Elliptic Curve Cryptography.


Secure degree reduction for Shamir's secret sharing I understand the basic Shamir Secret Sharing protocol, and when two shares are multiplied, the degree of the polynomial increases. I've seen in a number of papers a reference to a degree reduction protocol that can be performed to securely reduce the degree back to the original $t$. Yet I cannot find this construction anywhere. Could someone explain to me how the degree reduction is done and/or point me to a paper which describes the details?

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

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

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

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

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

They each share these using new polynomials

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

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

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

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


What is tiger192,4 in PHP? PHP supports hashing of the following Tiger algorithms:

tiger128,3
tiger160,3
tiger192,3
tiger128,4
tiger160,4
tiger192,4

Wikipedia's entry on Tiger says there's Tiger and Tiger2 and provides samples of Tiger and Tiger2 with 192-bit hashes of "The quick brown fox jumps over the lazy dog". So I tried to get PHP to tell me what the hashes of tiger192,3 and tiger192,4 are and...

The output of tiger192,3 matches what Wikipedia says the output is for Tiger(1). But tiger192,4's output does not match the output for Tiger2.

Tiger2's output is as follows:

976abff8062a2e9dcea3a1ace966ed9c19cb85558b4976d8

tiger192,4's output is as follows:

c1f3a704e9f6267e9f75fa47191f83c354100a04c4f1dc6f

tiger192,3 and Tiger's output is as follows:

6d12a41e72e644f017b6f0e2f7b44c6285f06dd5d2c5b075

So what is tiger192,4?

A quick look into the PHP code showed that PHP only understands the Tiger hash (the first one with incorrect bit padding).

It also showed that their implementation of Tiger may contain "additional passes", where each pass consists of 8 rounds (only called for values higher than 3). The value of passes is displayed behind the hash function:

#define compress(passes) \
    save_abc \
    pass(a,b,c,5) \
    key_schedule \
    pass(c,a,b,7) \
    key_schedule \
    pass(b,c,a,9) \
    for(pass_no=0; pass_no<passes; pass_no++) { \ <- additional rounds start here
        key_schedule \
        pass(a,b,c,9) \
        tmpa=a; a=c; c=b; b=tmpa; \
    } \
    feedforward

There seems to be no documentation other than this. Don't use cryptographic primitives that lack any description.

I've generated the same C1... hash by adding the 8 additional rounds in a Java application (and then deleted said Java implementation).


Should I PGP encrypt using a publickey intended only for Certify? I'm working with a publickey that does not include EncryptStorage or EncryptCommunication flags (see RFC4880 for flag reference).

My question is, is it safe/appropriate to encrypt using this key?

$ curl https://members.exacttarget.com/Content/Subscribers/SubsLists/publickey.txt > salesforce_publickey.txt
$ pgpdump salesforce_publickey.txt | grep Flag
 # Notice: The encrypt message and encrypt storage flags are not set

GPG has no problem encrypting with this key, I'm forced to use PGPy a pure-python implementation that is apparently more circumspect and fails to encrypt using the root and any subkeys:

import pgpy
publickey = pgpy.PGPKey.from_blob(bytearray(open('salesforce_publickey.txt').read(), 'utf-8'))[0]

publickey.encrypt('secret message', user=publickey.userids[0].email)
>>> PGPError: Key 64C4D5362A88CF19 does not have the required usage flag EncryptStorage, EncryptCommunications

since the root is only able to Certify and no flags are set on the subkeys AFAICT.

The full pgpdump output is as follows:

$ pgpdump salesforce_publickey.txt
Old: Public Key Packet(tag 6)(418 bytes)
    Ver 4 - new
    Public key creation time - Tue Jul 22 08:08:31 MST 2003
    Pub alg - DSA Digital Signature Algorithm(pub 17)
    DSA p(1024 bits) - ...
    DSA q(160 bits) - ...
    DSA g(1022 bits) - ...
    DSA y(1023 bits) - ...
Old: User ID Packet(tag 13)(54 bytes)
    User ID - ExactTarget, LLC. (We mail it.) <info@exacttarget.com>
Old: Signature Packet(tag 2)(91 bytes)
    Ver 4 - new
    Sig type - Positive certification of a User ID and Public Key packet(0x13).
    Pub alg - DSA Digital Signature Algorithm(pub 17)
    Hash alg - SHA1(hash 2)
    Hashed Sub: signature creation time(sub 2)(4 bytes)
        Time - Tue Jul 22 08:08:31 MST 2003
    Hashed Sub: preferred symmetric algorithms(sub 11)(5 bytes)
        Sym alg - AES with 256-bit key(sym 9)
        Sym alg - AES with 192-bit key(sym 8)
        Sym alg - AES with 128-bit key(sym 7)
        Sym alg - CAST5(sym 3)
        Sym alg - Triple-DES(sym 2)
    Hashed Sub: preferred hash algorithms(sub 21)(2 bytes)
        Hash alg - SHA1(hash 2)
        Hash alg - RIPEMD160(hash 3)
    Hashed Sub: preferred compression algorithms(sub 22)(2 bytes)
        Comp alg - ZLIB <RFC1950>(comp 2)
        Comp alg - ZIP <RFC1951>(comp 1)
    Hashed Sub: features(sub 30)(1 bytes)
        Flag - Modification detection (packets 18 and 19)
    Hashed Sub: key server preferences(sub 23)(1 bytes)
        Flag - No-modify
    Sub: issuer key ID(sub 16)(8 bytes)
        Key ID - 0x64C4D5362A88CF19
    Hash left 2 bytes - c6 d4
    DSA r(159 bits) - ...
    DSA s(159 bits) - ...
        -> hash(DSA q bits)
Old: Public Subkey Packet(tag 14)(525 bytes)
    Ver 4 - new
    Public key creation time - Tue Jul 22 08:08:42 MST 2003
    Pub alg - ElGamal Encrypt-Only(pub 16)
    ElGamal p(2048 bits) - ...
    ElGamal g(3 bits) - ...
    ElGamal y(2047 bits) - ...
Old: Signature Packet(tag 2)(70 bytes)
    Ver 4 - new
    Sig type - Subkey Binding Signature(0x18).
    Pub alg - DSA Digital Signature Algorithm(pub 17)
    Hash alg - SHA1(hash 2)
    Hashed Sub: signature creation time(sub 2)(4 bytes)
        Time - Tue Jul 22 08:08:42 MST 2003
    Sub: issuer key ID(sub 16)(8 bytes)
        Key ID - 0x64C4D5362A88CF19
    Hash left 2 bytes - e4 a9
    DSA r(157 bits) - ...
    DSA s(159 bits) - ...
        -> hash(DSA q bits)

Encrypting with a DSA key—as the master key is—doesn't make sense.  It appears that someone neglected to put the encryption usage flags on the Elgamal encryption subkey, which would be the obvious one to use.


Using an MD5 hash as a password Suppose Alice is using a password prompt that only accepts up to 32 characters for any particular password.

Memorization of long strings of random characters is not one of Alice's strengths, so she opts instead for a memorable passphrase consisting of a permutation of 7 of the 2000 most common English words. Unfortunately this passphrase exceeds the maximum password length allowed by the prompt (i.e. the passphrase is easily longer than 32 characters).

This is a common problem faced by the average user, who often is required to enter passwords to sites or server with maximum password length limits. What I wonder is whether this solution is relatively secure:

Alice hashes her passphrase: passphrase --> MD5(passphrase) --> new_passhash

MD5 digests have a length of 128 bits or 32 hexadecimal digits.

Alice takes new_passhash, which has a length of 32 characters, and uses it as her new password.

On the surface, it appears as if her password is in fact strengthened. Assuming an attacker is performing a brute-force attack:

Permutations for passphrase = 2000^7    (set of 2000 words, 7 choices)
Permutations for MD5 string = 16^32     (set of 16 alphanum characters, 32 choosen)

(2000^7) is strictly less than (16^32)

However, if the attacker does know that the passphrase is hashed using MD5, would the fact that MD5 is susceptible to collision attacks render the new_passhash less secure than the original passphrase?

Password strength is typically measured in bits of entropy, or in layman's terms, the amount of "true randomness" in the system. This is measured by the process of how the password is generated rather than by the number of bits in the output. It's a simple extension of Kerckhoffs' principle: assume your attacker knows your process, and the only information unknown to him/her is the secret key.

You are correct that the number of permutations of the passphrase is $2000^7$. This is about equal to $2^{77}$, so a password generated with this approach has about 77 bits of entropy, which is a very good password strength. However, passing the output through a digest function like MD5 doesn't actually increase the number of possible permutations. MD5 has $2^{128}$ possible outputs, but we're only actually using $2^{77}$ of them. Put another way, assuming an attacker knows our process, they don't have to guess all possible MD5 outputs; they only have to try ones that correspond to a hash of 7 of the 2,000 most common English words. And that's comparatively much easier to do.

In practice, however, 77 bits of entropy is still quite good for a password. MD5 doesn't add any strength in and of itself but it doesn't necessarily remove any either. As an "encoding" (assuming you're using a 32-character hex representation) to stuff seven random words into a field restricted to 32 characters (and frequently to only alphanumeric values), it appears to me to be practical.

One slight improvement would be to use Base32 encoding for the binary MD5 output instead of hexadecimal. This would reduce the length of the output to 26 characters (by allowing for uppercase letters as well) and could allow you to use this scheme for password fields limited to fewer than 32 characters.

Edit: Others have expressed concerns about weaknesses in MD5. While I also share a general distaste for MD5, I believe this use is perfectly acceptable. It is not being used for its preimage resistance here, because the attacker has no need to determine the original seven words that were used; having the hash itself is good enough. Given that both the chosen words and the MD5 hash itself are considered secret, I don't believe there is cause for concern.


Truth table for the Boolean function $f(x,y) = x \oplus xy$ - Conflict with answer computed by sagemath By hand, I computed $f(x,y) = x \oplus xy = (0, 0, 1, 0)$ since, in ascending (lexicographical) order,
$f(0,0) = 0 \\ f(0,1) = 0 \\f(1,0) = 1 \\ f(1,1) =  0$
However, using the following code on sagemath
R.<x,y> = BooleanPolynomialRing(2)
B = BooleanFunction( x+x*y)
B.truth_table(format='int')

The answer is (0, 1, 0, 0). I tried with other Boolean functions of two variables and I'm getting different answers from what I calculate by hand. Another example is $f(x,y) = x$. By hand, the answer is $f = (0,0,1,1)$ but using sage, it is $(0, 1, 0, 1)$.
Is it that the order in which the bits are calculated is incorrect?
A few details for context
I'm specifically interested in the convention regarding Boolean functions. For example, there are tasks that ask to find the ANF of a boolean function given in the $f = (b_1,b_2, \ldots , b_n)$ where $b_i$ is either $0$ or $1$. In the textbooks I have checked, it is often assumed that these values are in ascending order.
In this answer, for instance, the truth table was calculated in ascending order

The truth table
\begin{array}{|c|c|c|} \hline
x & y & xy & x \oplus xy \\ \hline
1 & 1 & 1 &  0 \\ \hline
1 & 0 & 0 &  1 \\ \hline
0 & 1 & 0 &  0 \\ \hline
0 & 0 & 0 &  0 \\ \hline
\end{array}
and you can use Boolean formulas
f = propcalc.formula("x ^x&y")
f.truthtable()

outputs
x      y      value
False  False  False
False  True   False
True   False  True
True   True   False


What is the difference between a hash function and a pseudorandom function? Read the title. I've seen in RFCs that some MAC functions are called "pseudorandom functions". What are those? How are they different than hash functions? Why can't a hash function be used instead?

A hash function is a stateless "primitive" function: given an input of X, it always produces the same output Y, where Y is a fixed length.  A cryptographically secure hash function has some additional requirements: given output Y = hash(X), it is hard to deduce input X; given output Y = hash(X1), it is hard to find output Y = hash(X2); and that it is hard to find hash(X1) = hash(X2).

Common random number generators that are used for statistical simulations are designed to produce a statistically even distribution of bits, and a hash function may be fine for this purpose.  But a statistics simulator doesn't need have the same security needs as a CSPRNG, as it isn't being used to generate cryptographic keys used to protect secrets.  A cryptographically secure pseudorandom number generator (CSPRNG) needs to output bits that are unrelated to each other, so that given output bits 0-n, plus knowledge of all internal state used to produce those output bits, it is hard to determine bit n+1.

To achieve this level of unpredictability, a CSPRNG needs a source of unpredictability, called "entropy".  Entropy is surprisingly difficult to come by inside a computer; as a computer is deterministic, it generally doesn't have an internal source of randomness.  Sources of entropy are often based on unpredictable external analog data (thermal noise on a Zener diode, radioactive decay, nanosecond timing of human inputs, etc.)  But the number of bits available are limited by the time required to collect them, so there is often not a large enough "quantity" of entropy to directly output the bits of entropy to all the clients who need random numbers.

To meet the higher demand of a modern computer system that needs lots of random numbers, the small quantity of entropy available is frequently expanded using a "cryptographic sponge" function.  This is a complex algorithm built of primitive functions that are used to collect the available entropy (called "harvesting"), gather the bits in a pool, and they then "stretch" the few bits in the pool into a larger quantity of relatively unpredictable bits.  A hash function is at the core of many of the sponge functions and can be used to expand a relatively small number of bits into a larger number of unpredictable bits, but the sponge needs extra logic in order to manage the incoming bits, to produce the queue of output bits, and to refresh itself.


Block Cipher Without Key Schedule? I'm designing a cryptography assignment for a college security course, and one of the problems is to perform a simple meet-in-the-middle attack on a 2-round, 2-key cipher.

Since we want this to be a reasonable attack for students to mount on their own laptops or school computers, the cipher needs to be very fast to compute. However, all of the ciphers I've looked at so far require significant key expansion via a key schedule, and since each encryption/decryption performed is with a different key, this expansion must be performed for every encryption/decryption operation, which we're finding in practice has a big performance penalty.

What I'm wondering is: are there any block ciphers that don't use key expansion?

These don't have to be secure by any stretch of the imagination: just secure enough that it's easier for students to do the assignment directly than break the block cipher via some other means.

You might consider using TEA or its successor, XTEA.  Here's the complete C source code for XTEA, taken from the Wikipedia article:

#include <stdint.h>

/* take 64 bits of data in v[0] and v[1] and 128 bits of key[0] - key[3] */

void encipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], sum=0, delta=0x9E3779B9;
    for (i=0; i < num_rounds; i++) {
        v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
        sum += delta;
        v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
    }
    v[0]=v0; v[1]=v1;
}

void decipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], delta=0x9E3779B9, sum=delta*num_rounds;
    for (i=0; i < num_rounds; i++) {
        v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
        sum -= delta;
        v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
    }
    v[0]=v0; v[1]=v1;
}

This code is simple enough that your students should be able to easily integrate it into their programs, and even modify it if necessary.  You might even want to consider reusing it for other exercises, too.  Notably, it also involves no special pre-processing of the key — the "key schedule", such as it is, is very simple and done directly within the encryption loop.

One feature of (X)TEA that (while generally a good thing) may not be ideal for your purposes is that it has a 128-bit keyspace, which is too large for a practical brute force search.  For your exercise, you could artificially restrict the keyspace to just, say, 32 bits by setting the remaining 96 bits of the key to some fixed value.  Then compositing two such encryptions with different keys should give you a 64-bit keyspace, which is still rather large to just exhaustively search by brute force, whereas the meet-in-the-middle attack needs only up to 233 operations, which should be easily doable.

By the way, the general property you're asking for is called key agility.  You may find other suitable ciphers by Googling for "key-agile cipher".


One-round feistel network (DES) attack I can't find out how to break 1 round of feistel network (obtaining the key).

I understand why this equation takes place:

$R_1 \oplus L_0 = f(R_0, k_1)$

EDIT: The function f looks like this:

But how can i find the key ($k_1$) from it?

I saw it's possible in a few references:

http://www.cs.technion.ac.il/~cs236506/04/slides/crypto-slides-05-bc-tutor.4x2.pdf
http://people.scs.carleton.ca/~maheshwa/courses/4109/Seminar11/atttack%20on%20DES.pdf
https://www.icg.isy.liu.se/courses/tsit03/forelasningar/cryptolecture04.pdf
KPA on Feistel cipher?

Thanks!

Since

$$X' = F(X, k) = P(S(E(X) \oplus k ))$$

the value of key $K$ is an element of the set

$$ \{V \oplus E(R_0): V \in S^{-1}(P^{-1}(Z)) \}$$

where

$$Z = R_1 \oplus L_0$$

and

$$
S^{-1}(P^{-1}(Z))
$$
is the set of possible inverse images of the parallel map of the Sboxes $S$ which is not one to one.

Total number of possible keys is $2^{16}$ because Sboxes are not bijective, there are $4$ possible inputs leading to same output.


How can the 'randomness' of a finite sample of binary keys from a finite key space be estimated? Given a set of bit sequences generated by an extractor, what would be a valid setting for estimating the
randomness of these generated keys and what resolutions can be drawn for
that extractor in general? The extractor will only generate bit sequences of fixed length such as 20 bits. Thus, all possible outcomes span only a finite key space.
Randomness
Though we would like to take the generated sequences as input to a cryptographic protocol (which has strong security properties even in the case of low-entropy input)
our requirements for 'randomness' are somewhat less strict than in any well-defined notion of randomness since these typically focus on properties of infinite sequences.
We are rather focusing on local randomness, i.e. the properties expressed by finite subsequences of random sequences of infinite length, and we would be even comfortable with results characterizing the peculiarities/bias/inter-bit-dependencies
our extractor exhibits.
Currently, we approach this problem from two angles:

Empirical: We apply statistical tests on the set of generated sequences such as comparing the number of birthday collisions in the set of sequences with the estimated number of collisions for a typical sub sample of same size. We should point out here that we are aware of suites as dieharder, but don't think they are applicable here as we are only interested in the case of finite sequences.
Conceptual: We focus on corner-cases such as the case where our extractor produces the sequence consisting exclusively of ones and reason about the likelihood of this event.

Please Note: We are aware of suites such as dieharder. We also know about different other tests but consider them not applicable here as they do not focus specifically on sets of fixed-length sequences!
Though we think there is no other straight-forward way of solving this question, we would be grateful for any further insights or advices. Meaningful tests would also be much appreciated.
Update: While we know that concatenation of these bit sequences should be possible given they are random, we inherently lack enough data to do so - we depend on specific sensor data for our extractor to work and this is not easy to obtain in large amounts. We might be able to extract only about 1GB. Therefore, we are trying to bypass this lack of data by focusing more on the specific characteristic of our problem.
Also, the term key is probably not applicable here and should be taken as password instead as we do not ever use it to encrypt plain text. This might enable us to use it even if there are some known slight weaknesses in the extractor.

There are a few things to notice here:

any tested sequence is finite by definition, we cannot run tests on infinite sequences;
the size of the output is interesting, but if it is sufficiently random then the concatenation of the 20 bit sequences should also be random;
we cannot say for certain that a sequence is truly random, as many algorithms can generate output that seems random, but isn't - like a part of Pi from a particular offset;
peculiarities/bias/inter-bit-dependencies are not acceptable for key generation.

Great, that out of the way, let's advance to the answers:

the die-harder tests and any other tests seem fine for your particular problem;
the fact that you generate 20 bits at a time is not a particular issue, as long as it is random;
you should understand the properties of the random number generator and test to see if it is supposed to be random given those properties - basically you cannot and should not test for randomness without description of the RNG itself;
if you are afraid that your results are biased then you should at least whiten the generated stream and / or use it as input to a Deterministic Random Bit Generator (DRBG or CSPRNG).

As for (4), it seems you already assume that your protocol takes care of possible bias ( although you also talk about using the randomness as key data). In that case I would try and prove that the bias does not pose a problem. Furthermore, I'd make sure that then RNG cannot be used for other parts of the application that do require a cryptographically secure random number generator.

Finally, note that die-harder and similar suites work best on (very) large data sets. A few GB is kind of the minimum. I hope your generator is fast enough for that.

Caveat: I'm not a super-expert on this area and cannot answer about local properties your stream exhibits. I do think that the idea that the generic test suites won't pick up on this is flawed though. I'm pretty sure that suites like die harder will pick them up - but I'm not sure about the clarity of the returned results.


Number of combinations required to brute force I am trying to encrypt a password in a program. Here is the process:

Let us assume that I have a string $p$ ($n$ characters long) which contains the password. Now the program reverse the string and stores it in string $r$. After that it takes each character of $p$ and $r$ applies the XOR operator and stores it in string $e$.

Next time the user want to access the file he/she will be asked to enter the password. The entered password will go through the process explained above and will be compared to string $e$. If both are not equal access will be denied.

I want to know the number of combinations of it will take a computer to brute force the password ("just to show if the encryption is mathematically effective or not, during the presentation"). Thanks

You're actually describing a use case for cryptographic hash function (not encryption). A cryptographic hash is a one-way-function that is collision-resistant. Meaning that it is hard to guess a pre-image (input to the function) that will generate a given result (called a hash).
Cryptanalysis of schemes like this assume that there is some structure or predictable property of the plaintext, such as letter frequency or word choice.
Let's assume that all of your users pick 4 words as their password (xkcd pass). And they choose it out of reasonable words in /usr/share/dict (about 50k words).
This is a strong password selection method, so if this scheme doesn't hold up under this plaintext pattern, it is most likely breakable under other password schemes.
Iterate through each word in the file, reverse it, and XOR it with the start of the password. We then take the result and do a look up in the sorted dictionary file (sorted during pre-computation). If this is a match, we've discovered two of the words and can recurse on the inner portion of the hash to find the last two words. This attack method assumes that all of the words are the same length, but I believe it can be easily adapted for various word lengths.
This attack will only take $\Omega(n*logn)$ steps of precomutation (for sorting the words file). And then $2*n*logn$ time for 100% guaranteed reversal of each hash. For a cryptographic hash (or one-way-function), you want a hash scheme to be secure in an exponential ratio to the number of bits, such as $\Omega(2^n)$, so this scheme is insecure.


Cipher Text generated is different if nonce is greater than 12 bytes I wrote a library which uses AES-GCM-128 to perform encrypt and decrypt operations. This library uses EVP functions that provide a high level interface to OpenSSL cryptographic functions.
To verify my library implementation is correct or not, I did the below test.
I took already known nonce, key, aad, plain text which I feed into my library and got a cipher text.
Now I feed the same into an online website which gave me a different output.
The cipher text generated by the website is 56d86b2c9932554f473950900f40250f and the cipher text generated by my local implementation is 6ceedef0a0f24a0fcb8f8730288f757d
The interesting thing is that if the IV is of 12 bytes, then I get the same cipher text from online website as well as my implementation. However, if I change the IV to 16 bytes, then I get different cipher text from online website as well as implementation.
I know that Using the IV longer than 96 bits causes an additional GHASH call to convert into 96 bits.
Also, the tag generated by my local implementation is always different from the one generated online even though nonce, key, aad, plain text remains same.
Can some one please help me in understanding this behavior?

Forget the other websites for comparison, you can fall into traps of inconsistent codes. Either use the OpenSSL as a comparison or better use the NIST test vectors;
GCM Test Vectors (SP 800-38D)


Decomposing a vector of random bits into constituent XORed vectores Suppose I have N potential predefined, publicly known (pseudo?) random bit vectors:

sequence 1: 1001000101010111001...
sequence 2: 0100101011101010100...
...
sequence n: 0101101010111010001...

Suppose you randomly choose a few (call it m) sequences and XOR them bitwise into a final vector. If one wanted to find out which vectors made up the final vector, the only solution that comes to my mind is to enumerate the n-choose-m combinations and start ruling out sets of m.

Is there a way to be smarter about this?  Is there a way to start ruling out individual vectors instead of just the combinations of m?

Also, does the practice of XORing many pseudorandom vectors have a name?

If solutions of more or fewer than $m$ vectors are also admissible, this is easy: XOR of $n$-bit strings can be rephrased as addition in the vector space $(\mathbb Z/2\mathbb Z)^n$. You are looking for a solution to the linear equation
$$ a_1v_1+\dots+a_mv_m=y $$
where $v_1,\dots,v_m\in (\mathbb Z/2\mathbb Z)^n$ are all the public bit vectors, $y\in(\mathbb Z/2\mathbb Z)^n$ is the sum of a subset,
and the coefficients $a_1,\dots, a_m$ must be $0$ or $1$, that is, in $\mathbb Z/2\mathbb Z$.

As over any field, Gaussian elimination can be used to find a solution to such a system.

Here's an example: Suppose given the $4$-bit vectors $1111$, $0100$, $0101$, $0011$ and the result $1110$ of XORing some of them. We write those vectors into the columns of a matrix and perform the elimination (which becomes quite simple in this case as there is only one non-zero field element):
$$
\left(\begin{array}{cccc|c}
  1&0&0&0&1\\
  1&1&1&0&1\\
  1&0&0&1&1\\
  1&0&1&1&0
\end{array}\right)
\leadsto
\left(\begin{array}{cccc|c}
  1&0&0&0&1\\
  0&1&1&0&0\\
  0&0&0&1&0\\
  0&0&1&1&1
\end{array}\right)
\leadsto
\left(\begin{array}{cccc|c}
  1&0&0&0&1\\
  0&1&1&0&0\\
  0&0&1&1&1\\
  0&0&0&1&0
\end{array}\right)
\leadsto
\left(\begin{array}{cccc|c}
  1&0&0&0&1\\
  0&1&1&0&0\\
  0&0&1&0&1\\
  0&0&0&1&0
\end{array}\right)
\leadsto
\left(\begin{array}{cccc|c}
  1&0&0&0&1\\
  0&1&0&0&1\\
  0&0&1&0&1\\
  0&0&0&1&0
\end{array}\right)
$$
The steps performed are:

Add (that is, XOR) the first row to all other rows.
Swap the third and fourth row to obtain a one on the diagonal.
Add the fourth to the third row.
Add the third to the second row.

Now we can read off the result in the rightmost column: The target vector is the XOR of the first three input vectors, that is, $1111\oplus0100\oplus0101$.


bcrypt - collision-resistance against chosen salt and work factor? Would it be difficult to find (cost, salt, input, password0, password1) such that

bcrypt(cost, salt, password0, input) = bcrypt(workfactor, salt, password1, input)

and

password0 != password1

where cost is not too small?

(If no, then the combination of bcrypt with PAKE described in this answer would be insecure.)

The answer to the original question would have been: Yes, it would be impossibly difficult to exhibit workfactor, salt, password0, password1 such that bcrypt(workfactor, salt, password0) = bcrypt(workfactor, salt, password1); but even if that was feasible, it would not matter much, because in normal use at least one of the password is unknown to an adversary matter only in certain protocols where it could allow ruling out two passwords in one try.

As to the question as now worded: No, it would not be too difficult to exhibit workfactor, salt, password0, password1, input such that bcrypt(workfactor, salt, password0, input) = bcrypt(workfactor, salt, password1, input); but that's only because input is left malleable, rather than set to "OrpheanBeholderScryDoubt"! In any reasonable use of bcrypt, input is built as three distinct 64-bit constants (or at least values not malleable to the degree in the question).

The original reference on bcrypt gives it as:

bcrypt(cost, salt, pwd)
    state := EksBlowshSetup(cost, salt, key)
    ctext := "OrpheanBeholderScryDoubt"
    repeat (64)
        ctext := EncryptECB (state, ctext)
    return Concatenate(cost, salt, ctext)

with text around suggesting that the pwd input maps to key (how exactly is unspecified), and that the 24-characters "OrpheanBeholderScryDoubt" maps to three 64-bit blocks constituting ctext. Predictably, implementations have varied on the mapping from pwd to key, including in ways introducing a serious weakness. Perhaps the initial value of ctext has varied also. Further, how Concatenate formats the output has varied (including in an effort to encode the variations used in the rest).

If Blowfish is a good cipher, 64 iterations of Blowfish is also a good cipher (better by some metrics, maybe slightly worse by the cycle structure), and thus for any three distinct constant 64-bit plaintexts, the ciphertexts per that Blowfish64 should be three values indistinguishable from random, except for being distinct. By design of Blowfish and bcrypt, finding a collision with random salt and key should be expected to require over $2^{96}$ evaluations of EksBlowshSetup, thus $2^{97+\mathtt{cost}}$ ExpandKey operations, which is beyond feasible.

But for whatever reason, bcrypt's wikipedia entry as I read it now states that bcrypt computes a hash from a given input as follows:

bcrypt(cost, salt, key, input)
    state := EksBlowfishSetup(cost, salt, key)
    ctext := input
    repeat (64)
        ctext := EncryptECB(state, ctext) //encrypt using standard Blowfish in ECB mode
    return Concatenate(cost, salt, ctext)

Notice the fourth parameter input and the uncertainty on if the password is fed to key (the original intend) or input. In the following I assume this 4-arguments definition, with password in the question mapped to key.

The crux is that the current statement of the question (not the originally intended and likely usual blowfish setup) leaves the choice of input, including as a 64-bit value repeated three times, which makes collision search feasible:

set cost to the lowest possible value;
set salt to some short admissible constant;
for j from $0$ to $2^{20}-1$, compute and store state[j] := EksBlowfishSetup(cost, salt, key) where key corresponds to a password obtained as j translated to an acceptable password as 5 hexadecimal digits and an appropriate suffix; that will require a reasonable 4GiB of RAM, and bearable CPU time.
repeat for i increasing, starting from $0$:

for j from 0 to $2^{20}-1$:

set ctext to i converted to a 64-bit bitstring;
repeat 64 times:

set ctext := EncryptECB(state[j], ctext); the encryption is over a single block;

if that ctext was previously obtained for the same i and earlier j, then derive password0 from that earlier j, derive password1 from the current j, and set input as the 192-bit bitstring formed by three times i converted to a 64-bit bitstring; we have found a collision!
else, remember ctext and the corresponding j in some easily searched table (which will require only a small fraction of the RAM used previously);

having had no luck with this i, empty the table, proceed to next i.

For each i tested, we are looking for collision among $2^{20}$ random-like 64-bit values, and that has odds about $2^{20+20-1-64}=2^{-25}$. Thus we are expected to succeed after about $2^{25}$ loops on i, that is $2^{45}$ loops on i and j, that is $2^{51}$ encryptions, which is considerable but feasible. Twice more memory makes a machine nearly twice as efficient, and to some degree it is possible to substitute hard disk or SSD for the part of the RAM used to store state[j], with some minor complications. Also, this can be distributed trivially, each machine using as much memory as it has available.

Update: I have checked two implementations of bcrypt.

jBCrypt is per the original bcrypt definition, but has two issues: because it is written in Java (which is not fully compiled at least in the most common practice, and lacks built-in idioms for unsigned 8-bit variables), speed is likely significantly worst than something native, which in the particular context means proportionally less secure; also, in that version at least, cost of 31 is accepted but degenerates to less security than the minimum cost of 4, because 1<<31 is negative in Java. Oh wait, I'm not the first to step on that, here's a corrected version.

In PHP, the accepted practice is delegating bcrypt password hashing to a native implementation of crypt (see this Bcrypt.php or that highly-praised answer), which is a sound way to solve the speed issue. I was told crypt goes to crypt.c then crypt_blowfish.c. I now have located "OrpheanBeholderScryDoubt", and the code referencing it is per the original bcrypt definition. Speed is likely quite decent. I like the idea of checking the code at runtime with a quick Known Answer Test, which also stands a good chance of overwriting sensitive values; and some modest but likely useful attempts to reduce other sources of leakage.


Signal Protocol: What extra features does double ratchet algorithm add to Diffie-Hellman ratchet? I have been reading the documentation of Signal protocol and could not find out why they came up with double ratchet instead of using Diffie-Hellman ratchet which was available at first place in OTR?

There can be many messages exchanged within the same DH ratchet round. Without the symmetric-key ratchet, all messages encrypted based on the same comprised DH key can be revealed. However, since the symmetric-key ratchet computes a new message key to send or receive each message and deletes old keys (including previous DH results, root keys, chain keys, symmetric message keys, etc.) after each encryption or decryption, the adversary cannot retrieve old message keys to decrypt previous messages if it knows only the current key materials within a DH ratchet round.


Attacks on LCG with "self-XOR" output function? Consider an ordinary LCG modulo $2^n$ with an internal state of $n$ bits and an output of $n/2$ bits, with the twist that instead of simply truncating the state to produce an output, we take the upper and lower $n/2$ bits of the state and XOR them together.

$$X_{i + 1} = A X_i + C \bmod{2^n}$$
$$Y_i = (X_i / 2^{n/2}) \oplus (X_i \bmod 2^{n/2})$$

Has this kind of pseudorandom number generator been analyzed in a paper somewhere? What are the core ideas to attacking it when $n$ is large (e.g. 64 or 128 bits or larger)? I am particularly interested in an output prediction or state recovery break, but a distinguisher is nice to have too. We may assume both LCG parameters (multiplier and increment) are known and odd.

It seems that the usual methods (e.g. lattice) fail to apply in this case due to the added state-dependent, nonlinear operation.

I made an attempt at approaching this as follows:

We're trying to recover the initial state $X_0$. We may collect a number of outputs $\{ Y_i \}$ and take a guess at the LSB of $X_0$. This immediately fixes the LSB of all other $X_i$ since $X_{i + 1} \equiv X_i + 1 \pmod{2}$, and thus fixes the LSB of the upper half of all $X_i$ by definition of the output function.

Some arithmetic shows that for all $i \geq 0$ we have

$$X_i \equiv A^i X_0 + C \sum_{k = 0}^{i - 1} A^k \equiv A^i X_0 + C_i \pmod{2^n}$$

We can now ignore every bit beyond the LSB of the upper half (T-function property) and focus on the first $n/2 + 1$ bits. If we find that there does not exist an assignment of the remaining $n/2 - 1$ bits of $X_0$ such that, for all $Y_i$ collected,
$$\mathrm{MSB}[\left ( A^i X_0 + C_i \right ) \bmod{2^{n/2 + 1}}] = \mathrm{LSB} \left [ Y_i \right ] \oplus \left ( \left ( X_0 + i \right ) \bmod{2} \right ) \tag{1}$$
then we have certainly guessed incorrectly. There's probably a better way to do this but we could just check satisfiability twice, once using our guess and once with the alternative guess, adding more $Y_i$ until either system becomes unsatisfiable, and thus recover two bits of $X_0$. Rinse and repeat on the next least significant bit until all bits of $X_0$ are recovered, in principle.

Checking for satisfiability exhaustively takes $O(2^{n/2})$ time, so if we need $m$ outputs at most recovering the state through this method in the most naive way takes time
$$O((n/2) \cdot 2^{n/2} \cdot m)$$
which is much faster than brute-forcing the internal state (assuming $m$ is reasonable; I have no proof of this but I suspect that $m$ is proportional to or at least polynomial in $n$). It should be (barely) viable for $n = 64$, whereas the $n = 128$ case remains hopelessly out of reach.

Using an SMT solver as part of the algorithm (I tried Z3 and boolector) doesn't really give any speedups and is in fact slower than an exhaustive search. This makes sense intuitively because the multiplication by the different $A^i$ is highly nonlinear over bitvectors so the solver just gets bogged down expanding and processing an ever-growing, exponential number of clauses.

Can we do better? What are some ideas that could be applied here?

To answer my own question, after some research and experimentation I came up with a fast algorithm to break such constructions (in fact the approach below works even if the increment $C$ is unknown).

As a preprocessing step, find a set of $m$ small weights $\lvert w_i \rvert < W$ such that

$$\sum_{i = 1}^{m} w_i A^i \equiv 0 \pmod{2^{n/2 + k}} \tag{1}$$
where $k$ is some small integer defined later. Such a set of weights can be found rather efficiently (and in polynomial time in general) through lattice basis reduction, e.g. running LLL on the following lattice basis:
$$
\begin{bmatrix}
K A & K A^2 & \dots & K A^m & K \cdot 2^{n/2 + k} \\
1 & 0 & \dots & 0 & 0 \\
0 & 1 & \dots & 0 & 0 \\
\vdots & \vdots & \ddots & \vdots & 0 \\
0 & 0 & \dots & 1 & 0
\end{bmatrix}
$$
for sufficiently large $K$, as shown by Lagarias and Odlyzko. In practice we expect such weights to exist when
$$m \log_2(W) \approx n/2 + k$$

Guess the lower $k$ bits of $X_0$, and use the LCG property to derive the lower $k$ bits of all $X_i$.

Use the $Y_i$ to obtain the lower $k$ bits of the upper half of all $X_i$. Denote $X^*_i$ as $X_i$ masked to only include those guessed upper bits, that is, $X^*_i = 2^{n/2} \times \mathrm{guess}$.

If we do some basic algebra we can notice that the congruence below follows from (1)

$$
\sum_{i = 1}^{m} w_i \left [ X_{i + 1} - X_i \right ] \equiv 0 \pmod{2^{n/2 + k}} \tag{2}
$$

Since the $w_i$ are bounded by $W$ and we know the most significant bits of the variables involved, we can approximate this sum using our $X^*_i$. In fact we can evaluate it to within $\pm 2 m W \cdot 2^{n/2}$. Compute:

$$
Z = \sum_{i = 1}^{m} w_i \left [ X^*_{i + 1} - X^*_i \right ] \bmod{2^{n/2 + k}}
$$
and let $\Delta$ be the difference between $Z$ and either 0 or $2^{n/2 + k}$, whichever is closest to $Z$.

If $\Delta \geq 2mW \cdot 2^{n/2}$, our guess to the lower bits of $X_0$ is certainly incorrect. Otherwise, it is correct with probability $1 - 2mW \cdot 2^{-k}$ (this makes some assumptions about the distribution of the $Y_i$, but works in practice).

Try all $2^k$ guesses against different windows of outputs $Y_i$ (adjusting accordingly, note that the relation (1) still holds even if you shift all exponents by a fixed constant) until all but one fail to pass the test in step 6. The final candidate guess will be the lower bits of $X_0$.

Repeat all steps, guessing successively higher bits of $X_0$ until the entire internal state is recovered.

This turns out to be very fast as $k$ can be set to be not too much larger than $\log_2{mW}$, for the probability of a false positive in step 6 to be sufficiently small, e.g. 0.5; if $k$ is too small then we extract no information.
Given the above, we should try to force $W$ to be as small as possible in step 1 to minimize the number of bits $k$ to guess, so that, for example, $W \approx 2$, $m \approx n/2 + k$ so $k \approx \log_2(n)$ showing that this attack should scale very well with $n$.
I've implemented this and it works well and successfully recovers the internal state as expected for $n = 128$.
Also it's possible to extend this to unknown increment $C$, the only thing that changes is we need to guess the lower bits of $C$ at the same time as the lower bits of $X_0$ to be able to perform step 2, and everything else stays the same; we recover $C$ and $X_0$ simultaneously through the same process.

References
This approach was adapted from techniques described in "Lattice Reduction: a Toolbox for the Cryptanalyst". This paper contains even more sophisticated techniques for attacking similar kinds of problems and is fairly readable.


What is the possibility of collision of trailing 160 bits of Keccak_256, for any two differing public-keys as pre-images? Earlier today I was answering a question on the ethereum SE site that analyzed the potential for more than one private key on curve secp256k1 (which maps to a distinct public key) to control the same ethereum address which are derived by hashing the public-key with Keccak256 as a byte array, and whether the rightmost 160-bits of the two resulting distinct hash digest could collide and thus two different private keys control the same address.

In other words, what would be the possibility that any two Keccak-derived  hash digests had the same right-most 160 trailing bits (small-endian side)?

And secondly, does that possibility change (and to what degree) if both pre-images can only be valid secp256k1 public-keys of which there are roughly ${2^{256}}$ of them or more precisely n as per this curve's parameters, where n is equal to 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141.

Again, ethereum addresses are simply the last 40-hex characters of a 64-hex (256 bit) Keccak Hash of the secp256k1 public-key derived from the users private key (assumed to be less than n).

If the digest space is $2^{256}$, and there exist even 2 digests that share the same trailing 160-bits, what are the chances that the pre-images to those 2 digests are valid 512-bit public-keys? And moreover, that those private-keys were actually derived by a private key known to the user (and not just a random 512-bit string that was brute-forced).

Given the multiple layers of conditions (compared being able to try any arbitrary pre-image regardless of length etc..), I was thinking that it could be possible (by chance perhaps) that no two private keys will derive the same ethereum address, even if there exists more than one Keccak256 hash-digest that partially collides in terms of the last 160 bits.

Although if there is a non-negligible amount of such 160-trailing-bit collisions, perhaps the chances actually exist for one ethereum address to be controlled by two different public keys? (even if not feasible to find them).

Note: My estimate/guess is that one would have to brute-force search at least $2^{160}$ valid private keys on the elliptic curve, including steps to derive the public key and resulting Keccak256 hash digest, to try to find even one such partial collision of the last 160-bits.

Can such a scenario even be computed or is there no way to know?

There are about $2^{256}$ distinct inputs, secp256k1 private keys, and about $2^{160}$ distinct outputs, Ethereum addresses.

By the pigeonhole principle, there is at least one address which is shared by many private keys.  In principle, there could be $2^{160} - 1$ addresses each with exactly one private key, and another address with $2^{256} - (2^{160} - 1)$ different private keys.  But that is essentially guaranteed not to be the case in practice.

The map from secp256k1 private keys to Ethereum addresses can reasonably be modeled as a uniform random function.  In this model, the expected number of secp256k1 private keys shared by a single hash is about $2^{96} = 2^{256}\!/2^{160}$.

What can you do with this apparently staggering number of colliding private keys?

Suppose the world has generated $n$ private keys and published their addresses.  The probability that there is a pair of private keys $k \ne k'$ sharing a common address $H(k) = H(k')$ is about $n^2\!/2^{160}$ by the birthday paradox[1].

If the world has generated a trillion keys, or about $2^{40}$, this probability is below $1/2^{80}$.  In other words, you are essentially guaranteed it hasn't happened.
Suppose you want to find some pair of private keys $k \ne k'$ sharing a common address $H(k) = H(k')$.  The cheapest known method is the van Oorschot–Wiener parallel collision search machine[2], whose expected cost is $\sqrt{2^{160}} = 2^{80}$; of course, if parallelized $p$ ways, it runs in time $2^{80}\!/p$.

This cost is spent by the Bitcoin network in about a day.  But what would you do with this pair of keys?  You could give one of the keys to someone and do something nefarious with the other key, but…if you can already choose someone's key, it's hard to imagine what nefarious things you could do with a colliding key that you couldn't already do with the original in the first place.
Suppose you have a specific address $h = H(k)$ for a key $k$ that you don't know, and you want to find a key $k'$ that matches $h$.  You are essentially guaranteed that $k' \ne k$, but that doesn't matter—$k$ can spend the money of $k'$ and vice versa.  Perhaps you actually have $t$ different addresses, $h_1 = H(k_1)$, $h_2 = H(k_2)$, …, $h_t = H(k_t)$, and you will be happy if you find one matching $k'_i$.  The cheapest known method is an adaptation of Oechslin's rainbow tables[3] to a $p$-way parallel machine[4], which costs $2^{160}\!/t$ as long as $t < p^2$, and runs in time $2^{160}\!/pt$.

Even if you had a quadrillion target keys (about $2^{50}$), which you don't, and you had a $2^{100}$-way parallel computer, which you don't, it would still cost $2^{110}$ to power that computer to find the first matching private key, which you won't.

P.S.  Public keys may be encoded with 512 bits but there are only about $2^{256}$ of them—specifically, there are exactly as many distinct public keys as there are distinct private keys.


Tweakable encryption algorithms vs Key wrapping I have read many articles about Key wrapping and tweakable cipher modes.
However, I don't understand the main difference between them?
What you recommend for Key storage and Key Archive.

Key wrapping and tweakable encryption are actually quite different topics.
Key wrapping is more commonly related to keys forage and key archive.

Key wrapping

This is fancy terminology for encryption key with another key.
In key wrapping you have a master key that is used to protect one or more keys. It is generally impossible for (computationally constrained adversary) to decrypt wrapped key with no access to appropriate decryption key.

There are key wrapping mechanisms used with asymmetric cryptography, i.e. encryption and decryption with different key (such as RSA-OAEP), and symmetric cryptography, such as AES-KW. Many key wrapping algorithms provide some level of integrity/authenticity protection in addition to encryption.

For purposes of key storage and key archive, key wrapping is very often used.

Key derivation

(As introduction towards tweakable encryption). Key derivation is kind of counterpart of key wrapping. The master key is not used to protect wrapped key, but instead a key derivation algorithm is used to produce other keys from master key. The algorithm may, for instance, generate the keys based on purpose (as identified by "Label") and possibly, other fields related to context. Key derivation can be useful when many keys are needed, but it is not desirable to store all the keys, but only store the master key. (Thus, for key storage, this algorithm is not ideal.)

Tweakable encryption

In some fields, most notably Full Disk Encryption, it is would be desirable to use very large number of cryptographic keys, for instance, to use different cryptographic key per each sector. Conceptually, this is very close to using key derivation to derive per sector keys. Unlike key wrapping, in tweakable encryption the per sector keys are not (usually) stored anywhere.

The tweakable encryption algorithms have been usually implemented with optimization goal that it is very lightweight to change one parameter (tweak).
For purpose of key storage and key archive, in many cases, current tweakable encryption algorithms are of little use. Tweakable encryption (for instance XTS-AES), is mainly intended to protect (lower value) bulk data, in situations where data size extension to allow for integrity/authenticity checking is not an option.


Diffie-Hellman Key Exchange with Authentication: Man-in-the-Middle query I have been reading up on MiTM attacks, and the prevention of them using public key certificates. Recently I learnt about Diffie-Hellman Key Exchange with Authentication, and how it uses signed parameters for preventing MiTM.

I'm not fully clear on the process used with the protocol (as listed in RFC5246, appendix-F.1.1.3) with respect to authentication. I understand how Diffie-Hellman is vulnerable to such attacks when used without it, but how exactly does it prevent these attacks?

I understand that the messages are signed, so the attacker Mallory can't modify messages between Alice and Bob. Why is Mallory not able to forward say, Bob's certificate through to Alice, including any of Bob's signed parameters, and eventually intercept the negotiated session key through relaying all messages between the two parties?

Is it simply because Alice and Bob both generate their own secret keys, which means the session key isn't recoverable? (Mallory is more like an eavesdropper/Eve in this scenario?)
Additionally, does this mean if Mallory were able to recover the private key somehow, that he/she could compute 2 separate key exchanges and modify traffic as before with no authentication?

Lastly, say Mallory manages to compromise the private key and can intercept and modify traffic. Without changing the certificate/key, is there any other way to authenticate Bob in this scenario, or is this impossible?

Firstly, PKI makes use of a private key and a public key. The private key is known only to the user, while the public key is communicated securely via the use of certificates. To provide authentication and non-repudiation, users may sign a message with their private keys and obtain a digital signature. Any other users can verify that the signed signature is authentic by "decrypting" it with the claimed user's public keys.

So to answer your questions:

Mallory is unable to intercept the negotiated session key due to the Diffie–Hellman problem whereby it is hard to compute $g^{ab}$ given $g^a$ and $g^b$. He is unable to impersonate Bob if he does not prossess Bob's private keys.
Yes, your are correct. Mallory can only eavesdrop the encrypted ciphertext and is unable to learn its contents.
No, Mallory is unable to obtain the session key (of the communication between Alice and Bob) even if he has knowledge of Bob's private keys due to the Diffie–Hellman problem. Mallory is able to impersonate Bob when communicating to Alice but unable to impersonate Alice with communicating to Bob. However, if Mallory has access to both Alice and Bob's private keys then a MiTM attack is possible.
No, Bob has to change his public-private key pair including his certificate unless there is 2-factor authentication in place (e.g. via voice/text message or tokens).

Hope this helps.


What kind of ciphers does not depend on order of operation? What kind of cipher does not depend on order of operation ?

For Instance if we have two operations encryption Enc(m,k), decryption Dec(m,k) and some message m.

For which ciphers the following is true:

Dec ( Enc (m, k), k ) = Enc ( Dec (m,k),k )

I suppose ciphers in counters mode where Enc() and Dec() are identical operations provide such property.

What about AES_CBC ? ChaCha20 ? Camellia ?

What kind of cipher does not depend on order of operation?

Any form of PRP (block cipher) or PRG (stream cipher).

  I suppose ciphers in counters mode where Enc() and Dec() are identical operations provide such property.

CTR mode transforms a block cipher (PRP) into a stream cipher (PRG).

  What about AES_CBC ? ChaCha20 ? Camellia ?

CBC would pass your test but it'll xor the plaintext (instead of ciphertext) into the next block's ciphertext (instead of plaintext). This might weaken it. I'm not sure. You'll have to check the proofs if you want to invert CBC. PCBC would be probably safe (or safer than inverted CBC?) as it xors the plaintext and ciphertext into the ciphertext (normally plaintext) of the next block.

Chacha20 is a PRG where $\text{Enc} = \text{Dec}$, so it'll pass the test.

Camellia is a block cipher, just like AES.

Better questions:

Which modes support this without weakening it?

This is safe at least with CTR, OFB and wide-PRPs. Or even ECB, but you shouldn't use that anyway!

You can test all modes and try to prove or disprove their inverse-safety. But it is generally safer to use the right function for the named task.

Why do you need to invert these functions?

I see at least one use for this: to hide the encrypt vs decryption direction in onion routing networks like HORNET or Tor. In this case the relays would use the cheaper function (if one is cheaper). This use case relies on the stronger semantics provided by a wide-PRP. For more information on this see Onion-AE.


RSA public key and private key calculation: multiple answer Given N = 91
public key (11, 91)
Plaintext (88)

Ciphertext = 88 ^11 mod 91 = 30

to decrypt,
30 ^ 59 mod 91 = 88 (plaintext)
30 ^ 11 mod 91 = 88 (plaintext)
30 ^ 47 mod 91 = 88 (plaintext)

How can there be multiple suitable instance of private key such as 59/11/47?

Lastly, must public and private key always be a prime number?

[M]ust public and private key always be a prime number?

No, they don't have to be. Usually the public key is chosen as an odd prime though because it must hold that $\gcd(e,\lambda(n))=1$, which simplifies to "$e$ must not divide $\lambda(n)$" if $e$ is prime.

  How can there be multiple suitable instance of private key such as
  59/11/47?

Recall that all we need for correctness for RSA is that for each possible $m$ it holds that $m^x\bmod n=m$. It turns out that the smallest possible $x$ here isn't the euler-phi function $\varphi(n)=(p-1)(q-1)$ (in the two-prime case) but rather the carmichael function $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ (in the two-prime case), because it is defined to be the smallest such $x$.

Now what does this mean? It means that if $ed\equiv 1\pmod{\lambda(n)}$ then $e,d$ is a valid pair of RSA exponents. As you can individually reduce each factor in modular arithmetic this also means that for a fixed choice of $e,d$ for any integers $k,l$ the following is also a pair of valid exponents: $e+l\lambda(n),d+k\lambda(n)$ because $(e+l\lambda(n))(d+k\lambda(n))=ed+ek\underbrace{\lambda(n)}_{0}+dl\underbrace{\lambda(n)}_{0}+\underbrace{\lambda(n)}_{0}\lambda(n)\bmod\lambda(n)=ed$. What you have experienced was the choice $e=11,d=11$ and $k=0,3,4$.


What are access structures in Attribute-Based Encryption? I'm reading this article, but I could'nt figure out Definition 1 (Access Structure) on page 3, section 3.1.
It says:

Let $\{P_1, P_2,...,P_n\}$ be a set of parties. A collection $\mathbb{A} \subseteq 2^{\{P_1, P_2,...,P_n\}}$ is monotone if $\forall B,C:$ if $B \in \mathbb{A}$ and $B \subseteq C$ then $C \in \mathbb{A}$. An access structure (respectively, monotone access structure) is a collection (respectively, monotone collection) $\mathbb{A}$ of non-empty subsets of $\{P_1, P_2,...,P_n\}$, i.e., $\mathbb{A} \subseteq 2^{\{P_1, P_2,...,P_n\}}-\{\emptyset\}$. The sets in $\mathbb{A}$ are called the authorized sets, and the sets not in $\mathbb{A}$ are called the unauthorized sets.

First, what do they mean by access structure? And what is the power of a set of parties ($\mathbb{A} \subseteq 2^{\{P_1, P_2,...,P_n\}}$)? Is it meant as a power set? Could you give me an explanation about that, and/or give some examples?

An access structure is the set of sets that should have access. For example, if the set of parties is $\{P_1, P_2, P_3, P_4\}$ and the access structure, $\mathbb{A}$, is
$$\{\{P_1, P_2\}, \{P_3, P_4\}, \{P_1, P_2, P_3\}, \{P_1,P_2,P_4\},\{P_1, P_3, P_4\}, \{P_2, P_3, P_4\}, \{P_1,P_2,P_3,P_4\}\}$$
then $P_1$ and $P_2$ together have access, $P_3$ and $P_4$ together have access, but $P_2$ and $P_3$ together don't. Note that this access structure is monotonic. Since $\{P_1, P_2\}$ has access, $\{P_1, P_2, P_3\}$, $\{P_1, P_2, P_4\}$, and $\{P_1, P_2, P_3, P_4\}$ all have access.
Yes, it is meant to be the power set. $\mathbb{A}$ is a set of sets of parties.


What exactly are an untrusted memory and a trusted CPU? In the use of SGX and Oblivious RAM. There sometimes exist the notions untrusted memory and trusted processor.
What are the intuitions of those?

Can memory easily be hacked by adversaries? What about CPU?

As the name implies, the memory or CPU are partially or entirely untrusted.

An adversary who can control your memory and/or access patterns can learn a great deal about your data, even if it is encrypted. ORAM hides both the data and access patterns. ORAM may extend to disk or network storage, not just local memory.

An adversary who can control your CPU / program can do any arbitrary computations they want, including skipping safety checks or leak sensitive information outside the trusted container.

Trusting a public service on untrusted hardware

A public service may use SGX to verify to their users that they run the open source code that they commit to. I.e. to prove they don't have access to personal information, while their system actively processes the sensitive unencrypted information.

SGX only verifies the program that is running. Depending on the program and how it uses memory, a hypervisor may be able to observe the memory accesses (but not the internal program state) and learn properties of the secrets. ORAM protects against the latter case.

Neither trusted nor untrusted are ideal when we have more than 1 party. If you can use verified protocols instead, then you do not need to place trust in another party - because they cannot cheat (without being detected).


Breaking a Mersenne-twister RNG with unsequential outputs Pardon me for this newbie-ish question. I'm still a novice in cryptography . I have an application that outputs random numbers from 0 - 12 (endpoints inclusive) unsequentially (some outputs are thrown off) using the mersenne twister algorithm and i would like to break and predict its seed in Python but i don't know what to program?

Once again please pardon my little knowledge in this space.

If you can identify which outputs are revealed and which are thrown off (ex. every other output is thrown off), you may be able to successfully analyze the twister so that you can predict future outputs.
However, the bigger problem here is that you are limiting outputs to the range [0,12]. With a 32 or 64 bit word length, a set of numbers in that range will not reveal nearly enough information about the state (even if none were discarded and all outputs were revealed to you).


Would the Fiat Shamir identification scheme be more secure if I design it with an exponents higher than 2? Let's say both Prover and Verifier would use nth power instead of 2nd when creating public keys and when verifying. I know it would slow it down but would that cause the protocol to be more secure?

No, it wouldn't.

Very simply put: If you can compute square roots wrt. a composite modulus, then you can calculate other fixed roots, too. This is based on the fact, that being able to compute square roots allows you to factor the modulus:

Choose random $x$.
Compute $x^2$.
apply your square root algorithm to $x^2$.
The result $y$ will be a different square root than $x$ with probability 3 out of 4. And 2 out of 4 will allow you to directly factor the modulus.

When  you know the factorization, calculating any arbitrary root higher than 2 is easy.

The other way around is not known: When you can calculate roots for any degree with injective functions, then you can break the RSA assumption. But it is unknown, if that allows you to factorize the modulus or allow the computation of square roots.


Encryption in a Distributed PKI? Given a PKI infrastructure with a root node that signs CSR's for nodes Alice, Bob, and Carol.  Is it possible for Alice to encrypt some information, store it publicly somewhere, then later Bob or Carol can decrypt that information, without Alice, Bob, nor Carol directly communicating?

The only thing they have in common is their PKI (each their private key, their public key and root's public key), and the one-way transfer of ciphertext from Alice to the public storage, then on to Bob or Carol.

Neither Bob nor Carol's public keys are available to Alice (in the real problem, Bob and Carol don't yet exist but will in the future, after Alice has generated the ciphertext)

The root CA cannot participate in this other than as a typical signer; that is, we cannot ask the root to do the encryption/decryption for us.

This sounds like the scenario of identity-based encryption, or IBE.

In IBE, the ‘root CA’, called the private key generator or PKG in this scenario, doesn't handle encrypting or decrypting messages directly, but does have to furnish Bob and Carol with their respective private keys.  As long as Alice knows the names Bob and Carol, and the long-term master public key of the PKG, Alice can send encrypted messages to Bob and Carol—even offline, without contact with the PKG.  Then whoever can convince the PKG that they are named Bob or Carol will get a private key to decrypt those messages.

Of course, the PKG is a central point of failure: anyone who can compromise the PKG can decrypt all messages.


Getting the key used for HMAC given the hash and the plaintext? I'm working on a little exercise to understand the drawbacks of poor library choices and I've been presented with the following scenario.

The HMAC function in python is being used (md5). I know the message being hashed as well as well as the resulting HMAC for this message. The key being used is generated by random.getrandbits(128).

The only thing I can think of is to put the random.getrandbits(128) in some kind of while loop and generate HMACs for the message until I find a match with the given HMAC.

Is there any way I can extract the key being used by the hmac function knowing the message, the function used to generate keys and the message digest, that does not involve brute-force?

Is there any way I can extract the key being used by the hmac function knowing the message, the function used to generate keys and the message digest, that does not involve brute-force?

None are known; this remains true even if you have a huge pile of messages that you picked, and their corresponding HMAC-MD5's.

Collision-resistance for MD5 is completely and utterly broken; we can easily find pairs of messages that have the same MD5 hash, and we have a surprising amount of flexibility in choosing most of the contents of these messages.

However, HMAC does not rely on collision resistance of its hash function; as far as we know, HMAC-MD5 is still secure.  Now, we don't suggest people use it, but that's more of us btrying to get people away from anything that uses MD5, not of any specific known weakness.


Why a pseudorandom permutation is used in a simulation based proof but pseudorandom function is not? In this paper:

https://eprint.iacr.org/2011/272.pdf

the authors use peudorandom permutation in the protocols and proof rather than pseudorandom function. On page 31 (last two lines) they say:

"We also note that for the purposes of the simulation, we need to use a pseudorandom permutation rather than any pseudorandom function."

Question: Why can we use pseudorandom permutation in the simulation but we cannot use pseudorandom function?

I happened to be talking to one of the authors and asked about this. The short answer is: Eventually on page 34 they are considering a malicious adversary. The simulator has to extract the adversary's effective input but it only knows the messages sent by the adversary, which in this case are just the PRP outputs. The simulator knows the PRP key so it can invert the PRP to determine the adversary's effective input. A PRF wouldn't allow this, although a PRF is indeed enough for the semi-honest variant of the protocol starting on page 31.