texts: Modular Reduction of polynomials in GF(2^m)

texts:
I am having trouble understanding the algorithm implementation in the hardware of the reduction process over Galois fields of $F_{2^{163}}$
In the following process, it looks like we are calculating the $zc(z)$ value from 2m-2 downto m
which the first half of $c(z)$

but I am not getting to understand what is $r(z)$ and how it is obtained?
$r(z)$ shouldn't be fixed as $Z^m$ and if it s a polynomial what is its value and what is W?
and how is the process of $z^k * r(z)$ viewed as in hardware
is it only left shift by 1 for each k and an and gate with $r(z)$?


texts: Using HMAC-SHA256 with short passwords and sliced outputs for short-lived secure hashing

texts:
I don't have much background in cryptography, so forgive me if I'm using the wrong mathematical terms to explain my needs.

Following this question, I learned that taking a random secret 16-bytes password and some random 16-bytes msg, and calculating output = HMAC_SHA256(password, msg), it will take an attacker that knows output and msg an unreasonable amount of time (more than 20 years) to restore password, or even to find a different password (say password2) that gives a collision, i.e. the same output for HMAC_SHA256(password2, msg).

What would happen if I use a shorter password of 14 bytes (and the attacker knows that)? How much time would it take the attacker to find password or a colliding password2?

What if I slice the output and save only output[:14]? How much time would it take the attacker to find a colliding password2 such that:
output[:14] = HMAC_SHA256(password2, salt)[:14] ?

What about less than that, like 12 bytes or 10 bytes?

The hashing mechanism should be "unbreakable" for a really short time of only 1 minute - the final purpose is creating a hash-chain for an OTP with a dumb client that stores the whole list and each minute sends the previous "password" in the list (its hash gives the "password" that was sent a minute ago).
The memory on the client is limited (every byte counts), but I don't want it to make complex calculations than a lookup from an array.

According to my uneducated estimations, a 2 bytes shortening (to 14 bytes) means it would take at least $\frac{20}{2^{16}}$ years, which is around 2.7 hours. Am I right?

Thanks

--- New Estimations ---

Using a 14-bytes password for life time of 1 minute shouldn't be a problem. If an attacker had an algorithm to recover 14-bytes passwords in a minute, he could develop an algorithm to recover 16-bytes passwords in 65536 minutes (brute force the extensions), which is around 45 days (much less than 20 years).

Slicing the output is shouldn't be a problem even when it comes to finding collisions.
There are 65536 times more collisions that would match output[:14] than the full output, so it would be 65536 times "easier" to find one (i.e. $\frac{20}{2^{16}}$ years $\approx 2.7$ hours).
Saying that the password is 14-bytes is equivalent to saying that it is a 16-bytes password that ends with \00\00 (this is how HMAC treats short passwords anyway). This will only make it harder for the attacker to find a collision, because the collision must end with \00\00 too.

Does anyone disagree?

-- Newer Estimations --

Bad news - The output of HMAC_SHA256 is 32 bytes long, not 16!
Slicing the output to 14 bytes would make it $2^{8 \cdot (32-14)}$ times easier to find a collision ($\frac{20}{2^{144}}$ years $\approx$ no time at all).
Hmmm... right?


texts: How is the block size of a block cipher related to how susceptible the block cipher is to a birthday attack?

texts: For example what can you say about how susceptible Triple-DES is to a birthday attack due to the fact that it has a block size of 64-bits.


texts:
Someone I know showed this to me, and I can't put a finger to why it's happening. Am I missing something?
They encrypt the text, and the output is really guessable. $u\to t$, $i\to h$ (it's one letter behind), the $?$ are just spaces.


texts: I have a column in a database table called "Amount" that will store decimal values encrypted with AES. It's highly likely that the same amount will exist in multiple rows in the table and be encrypted with the same key. Furthermore, most of the plaintext values that will be encrypted are <5000. Are there any specific factors I need to consider or be aware of that might affect security in this sort of scenario vs a scenario where I'm storing some other data type such as strings with unique and unpredictable values? More specifically, I'm wondering if this scenario is vulnerable to known plaintext attacks.


texts: Longer IV generation from a single block IV for ICBC

texts:
I was reading a question about ICBC here and it mentioned that you would need a $s \cdot n$-bit $IV$ if you would use $s$ "stripes", where $n$ is the blocksize.

Say that we don't like transmit that amount of data, would it then be safe to use the following generation of $IV'$ for ICBC, so we can use an $n$-bit $IV$ again?

$$IV' = \operatorname{CBC}_k(0^n, IV \|  0^{(s - 1) \cdot n})$$

I think it is secure (other than that the amount of data that can be securely encrypted is diminished by the amount of data that is encrypted for
$IV'$, but that's as good as negligible, I suppose).

Of course, we assume the normal CBC conditions regarding unpredictability for the $IV$ in the scheme.


texts: Can I use a blockchain to lock access to some information before a certain amount of time has passed, without relying on third-parties?

texts:
Picture the following (the example is very similar to the real scenario):

I have a physical item in possession in which I want to lock myself (don't ask [1]) from accessing it until a n number of hours have passed.
I put the item in a box with a combination lock [2].
I change the combination, and somehow temporarily save it without looking at the new one (in my case I took a picture with my cellphone and didn't look at it).
However, I want to completely lose access to the new combination (i.e.: the picture) until a certain number of hours have passed.
In this particular case, I solved it using a third-party website that sends e-mails on a future date, so I attached the picture of my cellphone (w/o looking) and configured it to send it to me after n hours.

So far there's no cryptography involved above. See below an simpler example which may make more sense:

I have a file in which its contents I want to lock myself from accessing them until n hours have passed.
I encrypt the file with a random unknown password, so that I cannot access its contents anymore.
However, after n hours I am somehow able to figure out the password and decrypt the file, thus accessing its contents.

I searched around (before resorting to asking a question), and in fact cryptographic algorithms are not time aware, so there's no way to get the "self-time-capsule" behavior I need without relying on a third party.
However, it came to me that the Bitcoin blockchain (or any other blockchain) is basically a decentralized third party. So, would there exist any way to get the behavior I need by using the Bitcoin protocol, for example?
Feel free to suggest other solutions, it's quite possible I'm going all over the top here.
Oh, just for giggles: the timed e-mail service I used didn't work at all, I got no e-mail back. Well, that's the problem with trusting a third-party. Guess I'll begin picking the lock anyways...

[1] You can think of it as money, say 100 bucks I really can't/shound't spend it before n hours have passed.
[2] Assume the lock is not pickable or the time it would take to pick it or brute-force is way higher than n, so not worth it.


texts:
All zero-knowledge protocols I have read so far for discrete log works like this:

1) Prover generate a random number $r$, creates a commitment $t=g^r$ and sends $t$ to the verifier.

2) Verifier generates a random challenge $c$ and sends it to the prover.

3) Prover creates a response $s=r+x*c$ and sends it to the verifier

My question is: is the security affected in any way if, in step 3, the prover responds with $s=r+x+c$?

I don't understand why multiplication $x*c$ is used instead of sum $x+c$.


texts: Transferring Encrypted One-time pad over the internet

texts:
I was working with one-time pad, and as I understand , for one time pad to be 100% secure a key shouldn't be repeated. So assuming Alice and Bob have to exchange messages over the network secured over OTP, they both have to have the same key, which should happen by physically meeting and sharing the key on a drive for a example.

However I thought, if Alice and Bob had another type of encryption, symmetric encryption like AES, and they wanted security over OTP without meeting, couldn't just Bob generate OTP, encrypt it with AES, and send it to Alice over the network, and then it would be equally secure since the encrypted OTP was gibberish and still is gibberish before being encrypted and after being encrypted, therefore it is not susceptible to brute-force or cryptanalysis or other.

Am I correct ?


texts: Any white-box cryptography for asymmetric-key? What is the latest status of white-box cryptography?

texts:
I am learning white-box cryptography. So far, I find the following historical research or implementations, for examples:

Published white-box AES algorithms

E.g., Chow's WB AES and WB DES (2002), WB AES Dual Ciphers (2010), Lai's WB AES (2009), and more papers.

White-box crypto included challenges
E.g., NoSuchCon 2013, CHES 2017, and more red/blue team challenges on white-box

Published cryptoanalysis or tutorials
E.g., cryptoanalysis on WB AES and DES, WB AES tutorial, NXP's options, and much more.

Published individual projects on GitHub and another website

After I read this white-box related information, I have these questions:

All the white-box crypto are designed on symmetric-key algorithms (AES & DES). Is there any asymmetric-key based white-box algorithms?

Many published white-box algorithms had been broken (see my another post). It seems that the white-box is not widely adopted by industries. How white-box could be implemented (aka opportunities) in the real industrial applications? For example, protect secrets hardcoded in the non-free code?

What are the latest white-box crypto design/development trends? no matter for academic research or industrial implementation.


texts: What risks are involved when choosing a curve for an implementation of ECC?

texts:
What risks are involved when specific curves are chosen for an ECC implementation?

How should I audit a system that uses ECC with regards to a specific curve?

Bonus: How can I (or a cryptographer) determine if a curve is backdoored?


texts: Parameters for comparison of Salsa, HC-128 and SOSEMANUK

texts:
I am doing my final project of computer science and I need some help.

I understand how Salsa works, but I don't have the same knowledge of HC-128 and SOSEMANUK. I have to do a table with the advantages and disadvantages of each one.

What parameters can I compare?


texts: Does there exist a Cipher / Hash identification tool?

texts:
Let's suppose I have two strings

One string is plaintext

The other is the result of running the plaintext through an unknown cipher.

Does there exist a tool where I can enter the pre and post-cipher text and have the tool spit out which cipher or hash may have been used?

I understand that such a tool isn't guaranteed to be accurate, but if it exists, it would be very useful to me right now.


texts: Help with breaking AES reduced to 2 rounds

texts:
I was studying Rijndael AES proposal, and its cryptanalysis. I started with writing code to break AES reduced to 2 rounds. I am using 128 bit key size and 128 bit block size. 2 round AES means the following sequence of steps:

$AR \to BS \to SR \to MC \to AR \to BS \to SR \to AR$

where
AR = AddRoundKey
BS = ByteSub
SR = ShiftRows
MC = MixedColumn

One of the way of breaking the algorithm can be generating inputs following a particular pattern and analyzing the output. Following are patterns I consider:

$P:$ All values are distinct
$Z:$ Sum of all values in zero
$X:$ Any other pattern

I give 256 blocks of input to the algorithm at a time. The blocks follow the following pattern:

$$
\begin{matrix}
P & P & P & P \\
P & P & P & P \\
P & P & P & P \\
P & P & P & P \\
\end{matrix}
$$

i.e. all the elements at same position in 256 blocks are distinct. I will denote this matrix as $[P]$ for simplicity.

After applying the above AES steps following is the fate of these matrices:

$[P] -AR \to [P] -BS \to [P] -SR \to [P] -MC \to [Z] -AR \to [Z]  -BS,SR,AR \to [X]$

The last $BS$ operation destroys the structure of the matrix.

We can consider the last 4 steps $AR, BS, SR, AR$ to be a map (say $f$) from 256 inputs at each matrix position to outputs and try to obtain this map using the fact that the input has pattern $Z$. There will be 16 such maps. We can solve it in following way:

Lets consider we want to find the map $f_{00}$ i.e. for the first element in the matrix. We know what all outputs we are getting for the 256 inputs we have taken. Lets say they are:

$u_i, 0 \le i < 256 $

Lets denote:
$x_{u_i} = f_{00}^{-1}(u_i)$

Since the input has pattern $Z$, we can write the following equation:

$$\sum_{i=0}^{255} x_{u_i} = 0$$

This is a liner equation in 256 variables. We can take another set of 256 blocks of input of pattern $[P]$ and generate another equation. We can generate 256 of these equations and solve them to find $f_{00}$. Same we can do for other positions as well. Once we get all the maps. We can easily get the key of encryption.

However my problem is this: No matter how many equations I generate, I always get at max 247 equations that are linearly independent. This means they don't have a unique solution. But according to me they should get a unique solution. Where am I going wrong? Why only 247 equations?


texts: Multi Message security in Random Oracle Model

texts: I have been learning about ROM in class and was wondering what an example of an encryption scheme that is multi-message secure in the random oracle model would look like? I have learned how to prove multi-message security in the standard model but I'm not sure how this translates to multi-message security in ROM, what are the main differences / things I need to look out for between these?


texts:
Fix $n\in\mathbb{N}$ with $n > 2$ and consider the following method.
Pick relatively prime seeds $x_1, x_2 \in \{0,1\}^n$ (where $x_1, x_2$ are interpreted as binary numbers. Then proceed with the following algorithm (C code is given below):

Let r = x1 ^ x2 (bitwise XOR; the "Fibonacci" step).
Rotate r to the right by 1 position.
Let x1 = x2 and x2 = r.
Output x1 and repeat.

Question. Given some output of unknown seeds after an unknown number of steps, is it "computationally hard" to find a pair of seeds that produce the given output after a number of steps?
Here's the C code:

#include <stdio.h>

unsigned rotate (unsigned n, int len);
       // len == length of rotation (number of bits rotated)
unsigned fibo_xor_rotate(unsigned n1, unsigned n2, int len);

// ---------------------------------
unsigned rotate (unsigned n, int len) // l == length
{
  unsigned b = n & 1; // get right-most bit
  n = n >> 1;
  n = n | (b << (len-1));
     // insert right-most bit at left end
  return n;
}
// ---------------------------------
unsigned fibo_xor_rotate(unsigned n1, unsigned n2, int len)
    // Fibonacci XOR and then rotate
{
  unsigned result = n1 ^ n2; // "Fibonacci" step
  return rotate(result, len);  // "Scramble" step
}
// ---------------------------------
int main()
{
  int i = 0;
  unsigned x1 = 0xd;  // seed 1
  unsigned x2 = 0x80; // seed 2
  unsigned h; // helper variable
  int my_len = 8; // length of rotation, here: 8 (-> byte length)
  while (i < 100)
  {
    printf("%x,", x2);
    h = x2;
    x2 = fibo_xor_rotate(x1, x2, my_len); // fibo xor rotate
    x1 = h; // set x1 to "old" x2
    if (i % 10 == 9) {
       printf("\n"); // newline after 10 prints
    }
    i++;
  }
  return 0;
}


texts: How can a stream cipher encrypt one bit at a time and still be secure?

texts: I was reading the differences between stream ciphers and block ciphers, noticing that block ciphers, encrypted blocks of 64 bits or so at a time. But, stream ciphers encrypt 1 bit at a time, and to me it seems it would be easily reverse-able? If the stream cipher's algorithm isn't changing then what stops the adversary from easily decrypting the ciphertext generated by the stream cipher?


texts:
I need a way to protect my data.

More then encryption I need a way to guarantee integrity and authenticity but I also need to be the only one that can understand integrity and authenticity.

I found HMAC to be a good way for integrity and authenticity but it is based on a single key that I should share within my software and I don't like it.

Is there a something like HMAC but with public-private key so that I can share only one key?


texts:
I have a NoSQL key-value database. I want to insert couple million of records to it.

For the key generation, I'm, using a prefix (something like data-one-) and then concat the SHA-256 hash of something unique to the value stored. So the end key might look like

data-one-0000fdb60e164cf0bf07cef647354d26ed17c9492ca4bbf4114878325871fa1d

The problem is that the key is somewhat large and it will have impact of the DB performance. I want to chop off some of the hash to get a 64-bit string (so, 8 chars). So I'd chop the above key to

data-one-0000fdb6

But will it leave enough entropy for the remaining key? The DB will get large, and I don't want collisions, obviously. Will another hash be more suitable for this use, or is trimming SHA-256 fine?


texts:
Please forgive me if this is a basic question, I'm in high school so I still don't understand very much.

Let's say there are two servers, each with a set of public and private keys. These denote server one: $PK^1, SK^1$ and server two: $PK^2, SK^2$.
Each of the private keys stored on the servers are encrypted with the opposite public key. The private key on server one is encrypted with the public key of server two. The private key on server two is encrypted with the public key of server one.

Data $(D)$ is sent to server one encrypted with $PK^2$. Server one encrypts $D$ with $PK^1$
$D = Enc(PK^1, D)$

$D$ is sent to server two, where $D$ is decrypted so that $D = Dec(SK^2, D)$. This should mean that the data is still encrypted with $PK^1$. Server two sends the data back to server one, where server one gets the plain text by doing $D = Dec(SK^1, D)$.

The benefit of this should be clear, the hosting provider is unable to see either of the private keys, which is a massive benefit to software such as Tor. If a private key of a hidden service is stolen, it is disastrous. This way there is no chance of that happening, unless both of the servers are compromised.

Is encrypting a secret key and being able to decrypt plain text with it possible?


texts: AES-128: can any two keys generate the same ciphertext from the same plaintext?

texts:
This is a purely theoretical question. I've found some similar questions, but they're not what I'm asking.

Most importantly, I'm not asking whether anyone can find the hypothetical duplicate. I'm not asking about the probability of encountering a collision, or how long it would take. In short, for my purposes, pretend you're coming to this from a non-crypto math background, and consider all finite numbers to be small, and imagine that you're allowed to do exhaustive searches of any finite space.

For any given key, there is obviously a 1:1 mapping from plaintext to ciphertext.

Now, consider a specific fixed plaintext. There are 1<<128 possible keys. There are 1<<128 possible ciphertexts.

Either there's exactly one key that produces each ciphertext, or at least one ciphertext results from at least two keys, and at least one ciphertext results from zero keys.

If you imagine AES as simply selecting random permutations, this is the birthday problem, and it's effectively certain that there are duplicates -- at least two keys will produce the same ciphertext from your given plaintext, and at least one ciphertext will never occur from that plaintext.

But AES doesn't select random permutations. It selects pseudo-random permutations. The selection process can't select every possible permutation; it can only select some of them. And it is conceivable that the set of permutations it can select has such a trait.

It is trivial to devise a scheme which produces non-overlapping permutations, as long as the number of keys doesn't exceed the number of possible plaintexts. For instance, "treat key and plaintext as unsigned 128-bit values, add them, that's your ciphertext" would have this property.

I have no practical applications for this, but if you want an impractical application: If AES did have this property, then you could interchange the roles of key and plaintext. You could send people blocks that were AES encryptions of a known plaintext, and they could simply look up the key in their table of "which key produces each ciphertext from that fixed plaintext". (Sadly, that table appears to require more storage space than our universe has atoms, but practicality is not my strong suit.)

EDIT: I did find AES-128. Do there exist two different keys for a pair (text, encrypted text)?, but I think that answer contains a flaw, which is that it assumes that the permutations are random, and that the way they are generated isn't influencing the selection of permutations, for instance, making them less likely (or more likely!) to overlap. I'm questioning that underlying assumption.

Specifically, it's this bit here:

  What if instead of uniform random πi we had πi=AESki for uniform random strings ki? If you could predict how that would affect the distribution nonnegligibly, you could distinguish AES from a uniform random permutation, violating the pseudorandom permutation family property that it is conjectured to exhibit, and there would be lots of cryptographers who would like to have a word with you.

(sorry for cut and paste formatting)

This isn't right, though. Think about block-cipher mode with a fixed key, and cycling through the (1<<128) possible plaintexts. You can't distinguish the output from a series of 128-bit random values in any way... But with an actual series of 128-bit random values, you'd virtually certainly get at least one duplicate by the time you did all the inputs, and with AES-128, you won't. But that's the only observable distinction, so far as I know. There's no ranges that are more or less likely, there's no connection from one to the next, and yet, you will somehow just magically never hit a duplicate value.

So we already know that AES-128 has, in one context, the weird property that a series of values it generates is indistinguishable from a random series of 128-bit values, with the sole exception of "but you never get a duplicate until you've hit everything". I'm wondering if it might have that property in a different direction also.


texts:
In the "Introduction to Cryptography: With Coding Theory" by Trappe and Washington, in the chapter about DES algorithm the authors say that:

  "In a good cipher system, each bit of the ciphertext should depend on
  all bits of the plaintext"

Since it's not said why, are you able to explain it to me ?
Thanks


texts: Does CCA security imply authenticated encryption?


texts: What does the Double Ratchet algorithm need the Root Key for?

texts:
One of the basic ideas of the Double Ratchet algorithm is that it performs DH exchanges in-band using a clever “half-DH” trick.

For some reason, instead of directly deriving the Chain Key from the DH exchange, it adds another layer: the Root Key. The Root Key is stored by both parties and is updated on every “half-DH” using the DH result and the previous Root Key. In the same way a new Chain Key is derived from the DH result and the previous Root Key.

Why is this Root Key needed? What would go wrong if we used solely DH to derive Chain Keys?

I went through the original description of the algorithm and a number of papers that study the security of Signal and WhatsApp implementations, but no one mentions Root Keys.

The only plausible explanation I found is in this blogpost. Basically it says that if we are so unlucky that the attacker is capable of breaking DH, deriving the Chain Key from DH is completely insecure. The fact that the Root Key is also mixed in means that the attacker will have to intercept and break every single prior “half-DH”-exchange. That makes perfect sense, but is that the only benefit?


texts: Where to apply Montgomery Multiplication in GF(2^n)

texts:
I'm optimizing a Reed Solomon decoding library for several polynomials in $\operatorname{GF}(2^k)$, $k\in\{8,10,12\}$.
Reading about the Montgomery Multiplication from Çetin K. Koç & Tolga Acar's Montgomery Multiplication in $\operatorname{GF}(2^k)$ (in Designs, Codes and Cryptography, 1998), I'm wondering if and how the method could help in polynomial reduction after carry free multiplication.

$t(x) = a(x)b(x)$ is a full length (2k-1) polynomial from carryless multiplication
$u(x) = t(x)n'(x) \bmod r(x)$  returns lower half of the $\operatorname{GF}$ multiplication
$(u(x)n(x) + t(x)) / r(x)$ corresponds to the higher half of one $\operatorname{GF}$ multiplication and one XOR

Instead of calculating $a(x)b(x) \bmod n(x)$, I have now $a(x)b(x)r^{-1}(x) \bmod n(x)$, and there's just one place where I can imagine using it. In inversion by modular exponentiation, where instead of calculating $a(x)^{254}$, I can calculate $(a(x)r^{-1}(x))^{254}$ and multiply that with a constant $r^{254}(x)$.
But can it be used e.g. in polynomial evaluation (used e.g. in syndrome calculation) or for modular reduction after $\operatorname{GF}$ multiplication?


texts:
I come from an engineering background, but not from computer science or anything to do with pure math. I studied applied math in college--never abstract algebra, number theory, or discrete math, formally. I have been a programmer most of my career.
Having developed a keen interest in cryptography, I learned number theory and abstract algebra on my own, and I get the role of number theory:  in factoring prime numbers and the discrete logarithm problem for PKI. These are both hard problems.
However, why discrete log over a group? What is the significance of a group here? Why do we need a group?
Why use abstract algebra?  I know AES uses Galois fields. I understand how, but I cannot figure out why.
I mean, why use finite field arithmetic?
Why should the arithmetic be done in a group? Why an Abelian group? Why a polynomial? Why are the closure, inverses, and identities necessary to AES?
Likewise, what other advantages do groups, rings, and fields have for cryptography? How exactly are the characteristics of finite fields indispensable for AES and cryptography in general? Why couldn't this be achieved without finite fields? Likewise, for other uses of abstract algebra in cryptography...


texts: What does it mean : "Canonical representative of Sbox is 0123468A5BCF79DE"? and How can we calculate this representative for Sbox?

texts:
In paper :Cryptographic Analysis of All 4 × 4-Bit S-Boxes Saarinen has classified $4 \times 4$ S-Boxes and defined Canonical representative for each class of S-Boxes.

What does "Canonical representative of S-Box is 0123468A5BCF79DE" mean? And,
How can I calculate it for an individual S-Box?


texts:
I would like to know how secure is ccrypt to encrypt files (like images, videos and other non-plain text data) using single password of 20+ chars length.

It uses Rijndael with 256-bit block size and 256-bit key size.

Is there any better alternative to encrypt files of this kind or is it secure enough?


texts: Computationally secure ORAMs with O(lg n)-bit words: shouldn't they fail with $n^{-O(1)}$ probability?

texts:
Virtually all "hierarchical" Oblivious RAMs use "cryptographically secure" hash functions to determine the position of an item at a given level; and implicitly assume (as can be evinced from the cost analysis in the respective papers) that these hash functions can be evaluated in $O(1)$ steps.

Then it seems to me that, if one is using $b-$bit words and simulating up to $n$ accesses, at least one of the following three conditions must hold:

the hash functions are randomly selected at the beginning of the simulation from an ensemble of $n^{\omega(1)}$ functions and not revealed to the adversary (contrary to virtually all oracle/pseudorandom function conventions); this is never stated, and in many constructions the opposite is stated.
the number of simulated steps, $n$, is such that $2^{b}=n^{\omega(1)}$, i.e. the size of each word in bits must be strictly superlogarithmic in $\lg n$.
the probability that an adversary can distinguish the simulations of two given computations is $n^{-O(1)}$ and not $n^{-\omega(1)}$, i.e. polynomially but not negligibly small in $n$.

The argument is very simple: since each hash function is computed from the virtual address to be accessed and up to $O(1)$ additional words, i.e. $O(b)$ additional bits, the adversary who knows that at a given step one of the two possible computations will access virtual address $addr_1$, and in the other virtual address $addr_2$, can guess the remaining bits with probability $2^{-b}$. And if he guesses correctly and has access to the hash function he can distinguish between the two computations with probability $1$. Then the adversary with access to the hash function can distinguish between the two computations with probability $2^{-b}$, and either this probability is $n^{-O(1)}$ or $b=\omega(\lg n)$.

The original Goldreich-Ostrovsky construction made it clear that $n$ could grow up to $2^{\Omega(b)}$, so it was considering case 3. But virtually all  hierarchical ORAM constructions in the literature of this decade (e.g. the Goodrich-Mitzenmacher "cuckoo" ORAM, the Kushilevitz-et-al. "rebalanced" ORAM, Pyramid ORAM, and several others) are very explicit about the fact that words are of $O(\lg n)$ bits, and at the same time that the adversary succeeds with probability $n^{-\omega(1)}$ ... so we can be neither in case 2 nor in case 3. Yet I find it hard to believe that we are in case 1, an incredibly non-standard model for pseudorandom functions/random oracles that is in fact never made explicit.

It seems to me I am missing something, but I have no clue about what. Even the smallest hint would be greatly appreciated.


texts: How is pre-master secret encrypted when ECC is used?

texts:
The certificate used in https://de.wikipedia.org/wiki/Authenticated_Encryption
has

public key ECC
public key parameter ECDSA
key usage digital signature

It is used to setup a secure TLS connection.

So far I know, that a so called pre-master-secret is generated by client ant sent encrypted to the server, using its certificate.

But what crypto-primitive is used for encryption in that case? The public key is used for digital signature, ECDSA, but signing something is NOT encryption.

How then is the pre master secret encrypted?


texts: How to cipher bocks with RSA in ECB mode?

texts:
I'm trying to implement a very basic RSA with functions that should generate RSA keys and cipher some text. GenKey function returns a tuple (p,q,n,e,d) like the following.

p,q large prime numbers with 1024bits each
n = p*q
phi(n)=(p-1)(q-1)
e as gcd(phi(n),e)=1 and 1 < e < phi(n)
d = e⁻1 (mod phi(n))

At the end I'll get a public key like kp={e,n} and a private one ks={d,n}. So far everything is working as expected.

Now suppose that cipher function receives a string of binary data as the plaintext to cipher and outputs a ciphered text in ECB mode(a binary string aswell). I Know that in order to cipher I can do the following: C = M^e (mod n) if M is an integer. If it's not I think I have to break my binary string into say 32bit length substrings, calculate it's integer value, apply C = M^e (mod n), get the new integer and last represent it back into binary. Please correct me If I'm wrong at this point.Am I thinking it right?

So my question is, when calculating C is it possible that returned value is too bigger for representing (as binary) on my block size decision (those 32bit). How block size should be picked?


texts: Secret key and Decryption oracle in the revised Fujisaki-Okamoto transformation

texts:
Recently, Fujisaki and Okamoto provided a revised version of the Fujisaki-Okamoto transformation [1], a generic transformation for achieving IND-CCA2 security in the Random Oracle model. This new version is slightly different than the original [2] and the security proof does not define a knowledge extractor (the original version actually proved that the transformation satisfies the Plaintext Awareness (PA) notion and used the fact that PA $\Rightarrow$ IND-CCA2 in the random oracle model). Instead, they directly provide an algorithm for the decryption oracle. When describing the decryption oracle construction, they stress that it does not require the secret key (in a similar way than the original version), and it only uses the information from previous random oracle queries.

Is this characteristic (i.e., not using the secret key) relevant in general for proofs for the IND-CCA2 notion, or is it simply something inherited in this particular case from the original transformation, aimed at the Plaintext Awareness notion? In other words, is there any inherent drawback in using the secret key in the decryption oracle when facing a security proof for IND-CCA2? I know that, usually, proofs are constructed as reductions to hard problems, which may force to define the decryption oracle without knowledge of the secret key. However, this does not seem to be the case.

I think I may be overthinking the problem, and that the answer may be a simple "No".

Update: I added some possible explanations in the comments. I'm starting to lean towards the answer "It is important in this particular proof, but not in general".

References:

[1] Fujisaki, E., & Okamoto, T. (2013). Secure integration of asymmetric and symmetric encryption schemes. Journal of Cryptology, 26(1), 80-101.

[2] Fujisaki, E., & Okamoto, T. (1999). Secure integration of asymmetric and symmetric encryption schemes. In Crypto (Vol. 99, No. 32, pp. 537-554). [link]


texts:
This is a curiosity. I don't see any value (yet) of using this.

Is it possible to have a signature that signs itself?

What I mean is that when you send a signed message, you send something like $(message \mathbin\| signature)$, where $signature = Sign(message)$. Is there a signature scheme in which $signature = Sign(message \mathbin\| signature)$?

Because the message should be hashed, you can't solve for $signature$ or do some sort of meet-in-the-middle solution.

My initial thoughts are (1) using SHA-2 or some other hash functions vulnerable to a length extension attack or (2) use homomorphic hash in some fashion. (1) would still require brute-force, but it would reduce computation. I haven't figured out how to use (2), especially since all the homomorphic hashes I know about aren't homomorphic w/r/t concatenation.


texts: Are there hash algorithms with variable length output?

texts:
I understand that for example MD5 produces a 128 bit hash value from a given text of variable size. My question is if there is a hash-like algorithm that will produce a hash value where one can specify the length of the outcome? So one would specify that that given any input the hash value (output) should be say 1000 bits.

For example, I would like to produce a hash value of the same length as the input. One way that I had thought of doing this would be to just encrypt the input somehow, but this would probably be easy to break, since one would just decrypt.

Another way I had thought about would be to divide the input up into say 128 bit chunks and then do MD5 (or some other hash) on each part and then just create one long string with the hashes of all the strings. However, I can see that a change in the input in one byte only would change 128 bits of the output.


texts: Is AES still secure considering all this NSA/Snowden scandal?

texts:
Im trying to understand if nowadays using AES is secure or not, after reading some arguments on Schneier’s blog (to be more exact, a comment to “The NSA Is Breaking Most Encryption on the Internet”) it seems like it is not secure:

Now as the NSA GCHQ et al know very well the more efficient you make the implementation of crypto code the more side channels it has unless extreme caution is observed. One thing we do know is that optimized for speed and minimized number of gates is an almost certain guarantee of side channels no matter how clever you are. Also the NSA knew that developers would not write their own code they would simply download and use the competition candidate code.
As was pointed out and demonstration code exploited implementations of AES were subject to timing attacks that could fully leak the key across a network connection due to "cache hits" on the Intel x86 platform from base level pentiums upwards within weeks of the winning candidate being announced. Even today there are very side channel suseptable AES implementations in use in fact the majority of those implementations on the likes of routers and switches are timing channel cursed as are most application level software implementations that are more than a year or so old...

…at least not if the computer used is connected to external network.
Is this true or just based on assumptions?


texts:
I am reading a book on cryptography and the author states that one of the complaints of the research community was that DES key length was chosen to be too short.

I am trying to depict how DES would look like if the key was 128 bits instead of 56(64) and why it would be more secure. I managed to express some ideas, but I am not sure how to evaluate them.

Expansion Permutation Effect: If the key length used after Expansion Permutation E(R-1) is increased, than R-1 expands to more bits (and then hashes
with longer subkey). This means that the diffusion is greater.
Less overlapping in key scheduling: Key length also affects how key scheduling is executed. A longer key
length means that shifts can be greater but I am not sure how this
affects security.

I'd love to hear an authoritative answer to my pondering. Have I missed something?

Feistel network:

Key schedule

In 4 rounds, a single left shift occures, in other 12, 2 bits are shifted in each of the key halfs.


texts: Why are they called "commitment", "challenge", and "response"?

texts:
I'm reading Proof Systems for General Statements about Discrete Logarithms, and I think I'll have a better understanding of the process if I can understand where the terms come from. They give a basic example which I'll just post a snapshot of below:

Can someone explain the logic behind the naming of these terms?


texts: What is the difference between non-programmable random oracle model and standard model？

texts: I know Common ground of them is that in both model the simulator cannot choose the reply for the query, and the difference between them is that in NPROM the simulator can still see the query/answer list, while in standard model it cannot. Anything else about them?


texts: Need help finding keysize for Vigenere cipher

texts:
I am doing a crypto challenge for breaking a Vigenere style repeating XOR encryption (https://cryptopals.com/sets/1/challenges/6).
I have looked at similar questions asked here, mainly this one: Finding a keylength in a repeating key XOR cipher But I am still unabe to determine whats the best way to find the length of encryption key.
I have a Base64 text (which I converted into hexadecimal value) that has been encrypted using repeating XOR encryption (a key of unknown size was repeated and sequentially XOR-ed across bytes of the plaintext).
The challenge suggests taking first and second keysize worth of bytes (for each keysize in some range) and counting Hamming or edit distance between them (and normalizing them by dividing by keysize). And that keysize with lowest distance should be the length of the key (no explanation is given why this should work, and I dont quite understand it). I have tried this method, but unfortunately I am not getting the correct keysize. Here's my pseudocode
for keysize in 2..100:
    a = bytes[0:keysize]
    b = bytes[keysize:(2*keysize)]
    score = hamming_distance(a,b) / (8*keysize) // mult by 8 since each byte is 8 bit and edit distance is counted by bits

(I tested this on my own encrypted message which I encrypted with keysize: 3 and it did not give me the correct result)
I have also tried calculating edit distance across several adjacent keysize worth of bytes and then averaging them (like the answer on linked post suggested), but that too didn't work.
I also tried doing Friedman's test, but later realized that this couldn't really work in my case as encrypted message consists of random binary characters, not 26 English alphabet letters.
What is the best approach for finding the correct keysize?


texts: Difficulty of finding partially matching ciphertexts for a given plaintext when encrypted with two different keys

texts:
I'm trying to find a simple, practical proof-of-work scheme based purely on encryption (due to wide availability of optimized, hardware accelerated AES execution on most platforms, including modern mobile devices).

I've considered the following:

Let $k_1$ and $k_2$ be two different randomly selected keys.

Find a counter value $c$, where $0 \le c < n$ such that:
$$\mathit{Prefix}_m(\operatorname{AES}_{k_1}(c)) = \mathit{Prefix}_m(\operatorname{AES}_{k_2}(c))$$

Or in plain words: find a counter value in a given range such that when independently encrypted with two different keys would result in two ciphertexts sharing a minimum prefix of $m$ bits.

By successive trials with $c = 0, c = 1, c = 2, ...$ the probability of finding a match by brute force is $\frac{1}{2^m}$ in each trial and $1 - (\frac{2^m-1}{2^m})^t$ after $t$ trials. The maximum counter value $n$ is adjusted such that it allows for sufficient number of trials such that a solution is found with high probability (say $0.99$ or more). If the client fails to find a solution in the given counter range they must try again with a different pair of keys.

The question is, since both keys (and the underlying algorithm) are known, is there a way for an attacker to use this knowledge to find a solution faster than brute-force?

I'm aware of known-key distinguishing attacks, but not sure if they are relevant here?

(I've intentionally chosen an approach where two keys are used, rather than just one, with the intuition that each permutation path would be defined by a completely different set of subkeys)

Edit 1: it seems reasonable that using two, completely different, encryption algorithms, one for each key (say one key with AES, and the other with Salsa20), might be stronger? (though the original goal was to use the same one - as AES is currently the only one with widely available hardware acceleration)

Edit 2: this is not intended to be a memory-hard PoW. I'm also working on one that is (also using purely encryption), separately, so memory-hardness isn't relevant here.


texts: Decrypting Ciphertext with partial Key Fragment using LFSR and Berlekamp-Massey

texts:
Edit

Does the state register (the LFSR) always have to remain with 16 bits (I'm assuming yes).

If so, are we shifting the register right by one (lfsr>>1) and inserting the output bit onto the left-most bit (lfsr>>1 | bit<<15) which allows us to wraparound within the same 16-bit address space.

So with this in mind, how does one generate the continuous keystream given:

seed: 1100101001110101

taps: 3, 12, 14, 15

Assuming you are given the following information:

Seed: 1100101001110101

Key Fragment: 000100011110101100001101101111101

And the following ciphertext/encrypted stream: 10101011000000010010110011001100101000010101010101010111101111110111010000010011

I am seemingly unable to decrypt the entire text into some ASCII values (UTF-8 decoded). I initially wrote a Berlekamp-Massey implementation and an online calculator to grab the tap positions of the above key fragment, which returned the following polynomial:

$$x^{15} + x^{14}+x^{12}+x^{3}+1$$

Fibonacci LFSR implemented in Rust:

fn next(&mut self) -> Option<(u16, u16)> {
    self.bit = ((self.lfsr >> self.taps[0]) ^ (self.lfsr >> self.taps[1]) ^
                (self.lfsr >> self.taps[2]) ^ (self.lfsr >> self.taps[3])) & 1;

    self.lfsr = (self.lfsr >> 1) | (self.bit << 15);

    if self.lfsr != self.seed {
        Some((self.bit, self.lfsr))
    } else {
        None
    }
}

The key fragment never appears in the generated key stream, indicating something probably went wrong.
The decrypted cipher doesn't map to ASCII values, just cryptic UTF-8 symbols.

The Berlekamp-Massey implementation is based off of the following whitepaper - https://www.osti.gov/servlets/purl/12658

And the full code can be found here - https://gist.github.com/JuxhinDB/ef8dac92b5af5de2e365d326b8dbc410


texts:
Alice has a single bit of information, b, that she wants to send to Bob (over an unalterable but possibly-monitored channel) but  in such a way that without the cooperation of Bob she cannot prove to anyone else (Eve) besides Bob after-the-fact that she sent b and not 1-b.

Is this possible? I am thinking perhaps not, because in any protocol Eve could step through the inputs Alice receives from Bob with both b and 1-b, and check which one of those the output she sends back to Bob matches. Even if the protocol is non-deterministic Alice could record the random values for Eve - but perhaps there is some way in which the random values could be set up to be trivially spoofed to indicate the other value to Eve after-the-fact (and hence Eve would not be able to trust Alice)?


texts: Private Key Sharding - How is it Secure in a Distributed Network?

texts:
In a Distributed Network in order for a private key not to be compromised sharding will have to take place off the network, correct?

If so: Why is it when a Distributed Network shards private keys that they are so worried about it being comprised in the network when the sharded keys are encrypted? Does decryption take place in the Network? If so: Why can decryption not be done off the network?


texts: How does the attack on MD5 work that allows a file to show its own (full) hash?

texts:
I've recently stumbled across this "moment" on Twitter, where there are three files, that show their own MD5 hashes.

As an example, this GIF (screen-shotted in the following image), has the hash:

f5ca4f935d44b85c431a8bf788c0eaca

They obviously match. Also this looks like the sort of attack that would normally take $2^{128}$ evaluations instead of the usual $2^{64}$ for a collision because you're going for a very specific message-hash pair.

So, how does this work, that a file can display its own MD5 hash?


texts: CRC32 catches errors, but then what's the point of SHA?

texts:
If crc or CRC32 is specially designed to catch errors, then what's the point of SHA or md4-5 or any other hashing function? What I did was, I had a 190 mb png file (rendered in 16k resolution with blender lol) and I took its sha256 and CRC32 hash, then I did the same, only changing 1 bit of the image. Just 1 bit. And I got a different crc, but also a different sha256

190 mb ~ 1 520 000 000 bits,

So what's the point then, if they both detect such small errors?


texts: Leighton-Micali Hash-Based Signature key sizes

texts:
I am working with the RFC for Leighton-Micali Hash-Based Signatures: RFC-8554.
The question is if I understood it correctly and my calculations of the key sizes are correct.
Basically, LMS uses several Winternitz-One-Time-Signature keys.

Winternitz-OTS
In chapter 4.1 of the RFC the parameter sets of the OTS keys are mentioned:
  |------------------------------------------------------------|
  | Parameter Set Name  | H      | n  | w | p   | ls | sig_len |
  |------------------------------------------------------------|
  | LMOTS_SHA256_N32_W1 | SHA256 | 32 | 1 | 265 | 7  | 8516    |
  |                     |        |    |   |     |    |         |
  | LMOTS_SHA256_N32_W2 | SHA256 | 32 | 2 | 133 | 6  | 4292    |
  |                     |        |    |   |     |    |         |
  | LMOTS_SHA256_N32_W4 | SHA256 | 32 | 4 | 67  | 4  | 2180    |
  |                     |        |    |   |     |    |         |
  | LMOTS_SHA256_N32_W8 | SHA256 | 32 | 8 | 34  | 0  | 1124    |
  |------------------------------------------------------------|

Where n is the number of bytes of the output of the hash function and p is the number of n-byte string elements. This means basically for the OTS private key we have n * p keys (+ 4 bytes for the typecode). This would also fit for the given signature length sig_len (n * p + 4 + 32 bytes for the checksum). The OTS public key is of equal length of the private key.
LMS
In chapter 5.1 of the RFC the parameter sets of the LMS keys are mentioned.
+--------------------+--------+----+----+
| Name               | H      | m  | h  |
+--------------------+--------+----+----+
| LMS_SHA256_M32_H5  | SHA256 | 32 | 5  |
|                    |        |    |    |
| LMS_SHA256_M32_H10 | SHA256 | 32 | 10 |
|                    |        |    |    |
| LMS_SHA256_M32_H15 | SHA256 | 32 | 15 |
|                    |        |    |    |
| LMS_SHA256_M32_H20 | SHA256 | 32 | 20 |
|                    |        |    |    |
| LMS_SHA256_M32_H25 | SHA256 | 32 | 25 |
+--------------------+--------+----+----+

Where m is the number of bytes associated with each node and h is the height of the Merkle tree.
One LMS private key consists of 2^h OTS private keys.
Questions

Is it correct that any LMS parameter set can be used with any OTS parameter set?
e.g. LMS_SHA256_M32_H25 for the Merkle tree and LMOTS_SHA_256_N32_W2 for the OTS keys.

Are those calculations of LMS private key sizes correct:
Formula: 2^h * ((n * p) + 4)

LMS_SHA256_M32_H5 & LMOTS_SHA256_N32_W8: 2^5 * ((32 * 34) + 4) = 34 944 bytes ~ 34 KB
LMS_SHA256_M32_H5 & LMOTS_SHA256_N32_W1: 2^5 * ((32 * 265) + 4) = 271 488 bytes ~ 271 KB
LMS_SHA256_M32_H20 & LMOTS_SHA256_N32_W8: 2^20 * ((32 * 34) + 4) ~ 1.1 GB
LMS_SHA256_M32_H20 & LMOTS_SHA256_N32_W1: 2^20 * ((32 * 265) + 4) ~ 9 GB
LMS_SHA256_M32_H25 & LMOTS_SHA256_N32_W8: 2^25 * ((32 * 34) + 4) ~ 37 GB
LMS_SHA256_M32_H25 & LMOTS_SHA256_N32_W1: 2^25 * ((32 * 265) + 4) ~ 285 GB

If those key sizes are correct then how would someone store them securely? Are those deep Merkle trees realistic? I guess calculating the corresponding public key can be done on demand.


texts: Digital signature algorithms within the European Union

texts:
I've just noticed that US NIST has accepted DSA as a digital signature standard. Does the European Union have a similar standard, specifying an algorithm to use when digitally signing messages?

I have been looking this up for some time now, but I fail to find a reasonable answer.


texts: The Collision Differential for MD4 - a question on notation (Wang, et al)

texts:
In the paper "Cryptanalysis of the Hash Functions MD4 and RIPEMD" the authors introduce the following notation (paragraph 4.1):

$\Delta$$H_0$ = 0 $\xrightarrow{(M_,M')}$ $\Delta$$H$ = 0

What exactly does this mean? I understand that  $\Delta$$H$ is probably the difference between hash outputs, but what about  $\Delta$$H_0$?

Disclaimer: I have zero knowledge about differential cryptanalysis, so my apologies if the formula above is some kind of standard notation there.


texts: File format of an $2048$ bits RSA public key

texts:
From here, there are $14$ bytes specifying the file format of the key. I am still quite confused about the format bytes. For example, the following public key
30 82 01 0a 02 82 01 01 00 8e a3 d1 c7 9c 86 05 52 3d 70 9a 5b 24 8a 6e ab 8f 5d 8d 9a 44 5f 25 78 c7 ba bd 3a a6 e1 36 b8 55 88 18 d7 ea e8 14 2c 68 8f e7 fe 94 4c f3 fd ad 0b e6 d2 eb 9e d2 66 b4 3a 3b d1 bb 5d d5 2a 53 7e 0f 1d ba ec 03 29 9d 47 50 3b 99 fb 4a 3a 80 a2 23 3e d7 11 e3 de a8 8d ab 7c 90 d0 92 af 36 b8 8b 28 fd 80 ec bc 37 6d 23 44 86 4e 28 19 1d 18 37 af 44 a9 40 b3 f6 e7 6c ad 56 5d 6f ff 3b e3 a5 cc 23 5c 54 2a 47 28 5b 29 f3 45 8e 69 98 ad 57 45 2e 60 bd ac 55 fc 35 e8 47 9f 98 0d f9 ea 9d 55 35 c9 db af 24 d2 bc 18 12 02 53 d6 aa ef 9c c9 11 c9 8e d7 7c 4f 2f 22 0f 66 b1 bf 06 a5 fa 87 22 9f ff f6 20 75 e7 51 87 26 30 c2 e1 a5 30 2c a1 fc 47 a5 f7 a5 38 d3 cc 8d 0e ee 5a 54 ee a2 f9 ff d0 0a 0f 18 7f 94 d2 04 5e 1f 25 ca be 4e 30 c3 40 00 ed a4 ce 58 ab 23 39 2d 02 03 01 00 01
is taken from google's certificate. The first byte $30$ means it is a sequence. Then I don't know what is the meaning from 2nd byte to 9th byte. Can anyone explain to me?
UPDATE: The 2nd byte (82) means that the following 2 bytes give the length of the sequence. The 5th byte tells us that it is an integer. The byte following it tells us the length and the value of the integer (I guess). Then the rest I have no idea.
Also what do the last 3 bytes stand for? I can't find format start with $01$.


texts: How come hash salt doesn't make a hash ineffective?

texts:
I am not a cryptography expert. I watched this video regarding hashing and salting as part of the course User Authentication With Express and Mongo in teamtreehouse.com.

I understand from the video that a hash is a representation of a password stored in the DB, used to prevent say company workers from copying password (the hash will be suited to a password given in authentication) and first created by passing the password in a hash function (simple hash function in this case).
I also understand that salting a hash is randomizing the hash.

What I didn't understand from the video is how would an hash keep being evaluated properly if we change it (salting it), each authentication anew. In other words, how could it still match the password.

Edit: Maybe I should have ask: What is the mechanism that creates the salt, juxtaposing it to the hash, and make sure the password will comply to the hash+salt combination.


texts: Is there any course video for lattice cryptography?

texts:
Recently, I started doing research about Lattice Based Cryptography. and searched on YouTube a lot of public talks or seminars about it.

But is there any course video (graduated course) related to it?


texts:
I am looking for a decentralised leader election protocol where each node knows whether or not they were elected leader, but nothing else. In particular, this "blindness" property means a node that was not elected leader does not know which node was elected leader.

Do you know of a decentralised blind leader election protocol?


texts: SHA algorithim with different hash value

texts:
I am new in hash cryptography. I am trying to build the sha256 hardware accelerator. I am thinking about using the different hash value to optimize the performance. I am trying to fetch custom hash initial value which already computed sometime ago. Does this approach valid and what problem i would get.

Thanks


texts: Password Entropy in bits for passwords of a certain structure

texts:
I have read this post and this post about how best to calculate a pseudo accurate entropy in bits of a password.
I can do this fine for passwords of a uniform nature, such as 8 letters of an a-z range is:
26(a-z)^8(length) = 208,827,064,576

Then to bits:
log2 (208,827,064,576) = 37.6035177451 = 38,

So it's guassable entropy S is 38 - 1  = 37 bits.
My problem:
Now, I have a password made up of the following structure:
A-z, 0-9, a-z, 0-9 .... to ten characters long (5 of each type).

Example:

A9B8C7D6E5

I figure the entropy value of that would be:
(b): 26 * 10 * 26 * 10 * 26 * 10 * 26 * 10 * 26 * 10 = 1,188,137,600,000

I had tried other variations for shorter syntax such as (26 * 10)^5 but these figures didn't seem to corellate.
Anyhow the above gives entropy bits of:
   log2(1.1881376e+12) = 40.1118390651

So S is 40. This strikes me as being only a tiny bit larger than the first example, and I think I'm working this correctly, and I am aware the numeric characters do severely limit the potential entropy of the whole password.

Is my caculation and conclusion (S~40) correct?

If so; is there a more efficient way of working out equation (b)?

Thanks.


texts: What's the difference among Vector Commitment, Zero-knowledge Set, Zero-knowledge Accumulator, and Zero-knowledge Elementary Database?

texts:
Vector commitment allows one to commit to an ordered sequence of $q$ value ($m_1,\cdots,m_q$) in such a way that one can later open the commitment at specific positions(e.g., prove that $m_i$ is the $i$-th committed message).
A Zero-knowledge set means that users commit to a set and subsequently prove the (non-)membership of some elements without revealing any further information (not even the cardinality of the committed set).
Accumulator allows to succinctly present a set by an accumulation value with respect to which short (non-)membership proofs about the set can be efficiently constructed and verified. Zero-knowledge accumulator additionally provides hiding guarantees: Accumulation values and proofs leak nothing about a set.
Zero-knowledge Elementary Database allows to commit a database that consists of the pairs $(i, DB[i])$ and prove that $DB[i]$ is the value on position $i$  without revealing any further information.
I confuse these primitives. The zero-knowledge set and Zero-knowledge accumulator set are designed for unordered data. Vector commitment and Zero-knowledge Elementary Database are designed for ordered data. Could these primitives be transferred mutually? What's the difference. Could we say that Vector commitment is Zero-knowledge Elementary Database?


texts:
I am a newbie in cryptography (I know the basic RSA, AES stuffs) and am interested in anonymous authentication systems. Looks like David Chaum is the godly figure in the field. I see lots of people citing his anonymous credential system paper  and his
paper.

Can someone explain in simple language (and simple maths), the concept behind David Chaum's anonymous credential system? I find the papers too heavy to understand. I probably have lots of follow up questions.


texts: What if n of RSA is same for two people over the network?

texts: I was just going through RSA encryption scheme and was trying to figure out how to do all maths. I was suddenly struck by the question that (e,n) is public to the people. How easy it becomes to attack one's system if you find out that you are using same n as someone else?


texts: Running Crypto on hardware -- e.g., AES in hardware

texts:
I am trying to understand the difference between a crypto algorithm run in hardware from that run in software. From a previous post (see here: Difference between Hardware implemented algorithm and software implemented one?), I have a partial answer to the question. The answer is that running a crypto algorithm in software typically means that it is run on CPU or GPU while running a crypto algorithm in hardware means that it is run on FPGA or ASIC.

Here is my confusion: In both cases the algorithm is still passed as a set of instructions to the CPU, GPU, FPGA or ASIC. For me this means that the algorithm is compiled into a set of instructions that are passed to the underlying hardware (where hardware means CPU, GPU, ASIC or FPGA). So this means all four cases operate in exactly the same way-- which makes me wonder why some are called hard-ware-based and others are called soft-ware-based.

Would someone please clarify?

**This question is not a duplicate of the earlier question because I am looking for the operational differences between the two. To put it differently, lets say I have some data to encrypt. Can some one give me the step-by-step process from start to end of encryption for (1) the hardware case, and (2) the software case? I am not looking for the advantages and disadvantages of either; I am only looking for the differences in how they work.


texts: Implementing CBC Encryption Using Decryption

texts:
I've implemented this algorithm, which, working from the end of the message backwards, creates a valid CBC ciphertext from any plaintext, using the block cipher's decryption operation instead of the encryption operation.

I bet this is described in the literature, somewhere. Possibly as a bad idea.

My questions:

What is this method/algorithm/construction called?
Is it as secure as CBC implemented the normal way?
Do the normal rules for CBC IV apply to the last ciphertext block or not?

For those wondering why I would want to encrypt my message from the end, this is an exercise in exploiting a padding oracle attack (against my own dummy code running on my own server).


texts:
I have a small embedded device (let's call it "eDev") that needs to upload sensitive information to a cloud storage server (lets call it "CSS").

The requirements for communication are as follows:

Strong Asymetric encryption on the communication between eDev and CSS.
eDev and CSS should be authenticated to each other (certificate).
Data sent from eDev to CSS needs to be encrypted in such a way that the eDev has no way to decrypt it (in other words, I as the developer of eDev should have no way of decrypting data uploaded by a user).
All encryption should support perfect forward secrecy.
In case eDev is lost or malfunctions, there should be a way for the user to still be able to retain his decryption key for the cloud stored data.

Here are my constraints and assumptions:

eDev (the user) registers to the CSS using email only, no password needed.
initially, I control the eDev hardware and can write anything to it.
The only place that can store any unencrypted user data (including encryption/decryption keys) is eDev.

What encryption types do I need to fulfill these requirements?


texts:
Is Paillier cryptosystem commutative?

If not, how can we construct an oblivious decryption protocol based on Paillier?


texts: Modes of operation that simply uses the tweak of a tweakable block cipher

texts:
What is the name of the mode in which we simply change the tweak for each block without the need for complex chaining modes? Is this mode secure?

Are there any other recommended modes for native tweakable block cipher like Threefish?


texts: Converting raw ECC private key into ASN.1 DER encoded key

texts:
I created a random integer array of 32 bytes to use as my private key for secp256k1 curve.

const uint8_t secret[] = {0xb2,0x9a,0xc6,0xbd,0xc7,0x3d,0xc4,0xe1,
                          0x85,0xa7,0x3c,0x96,0xf8,0x1c,0x58,0x43,
                          0xe2,0xbf,0x2d,0x68,0xe5,0x6f,0xf6,0xae,
                          0x4f,0xe7,0x51,0xcd,0x9d,0x47,0x00,0xfa}

I want to turn this hex array into a ASN.1 DER encoded key so I can further use it with my hardware which expects the keys to be ASN.1 DER encoded.

Can you point me in the right direction on how to achieve this ?

Edit , I found an encoded key-pair, maybe I can pick up from this. Does the array below contain both public and private key parts ?

 keyPairData[] = { 0x30, 0x81, 0x87, 0x02, 0x01, 0x00, 0x30, 0x13,
    0x06, 0x07, 0x2A, 0x86, 0x48, 0xCE, 0x3D, 0x02,
    0x01, 0x06, 0x08, 0x2A, 0x86, 0x48, 0xCE, 0x3D,
    0x03, 0x01, 0x07, 0x04, 0x6D, 0x30, 0x6B, 0x02,
    0x01, 0x01, 0x04, 0x20, 0x78, 0xE5, 0x20, 0x6A,
    0x08, 0xED, 0xD2, 0x52, 0x36, 0x33, 0x8A, 0x24,
    0x84, 0xE4, 0x2F, 0x1F, 0x7D, 0x1F, 0x6D, 0x94,
    0x37, 0xA9, 0x95, 0x86, 0xDA, 0xFC, 0xD2, 0x23,
    0x6F, 0xA2, 0x87, 0x35, 0xA1, 0x44, 0x03, 0x42,
    0x00, 0x04, 0xED, 0xA7, 0xE9, 0x0B, 0xF9, 0x20,
    0xCF, 0xFB, 0x9D, 0xF6, 0xDB, 0xCE, 0xF7, 0x20,
    0xE1, 0x23, 0x8B, 0x3C, 0xEE, 0x84, 0x86, 0xD2,
    0x50, 0xE4, 0xDF, 0x30, 0x11, 0x50, 0x1A, 0x15,
    0x08, 0xA6, 0x2E, 0xD7, 0x49, 0x52, 0x78, 0x63,
    0x6E, 0x61, 0xE8, 0x5F, 0xED, 0xB0, 0x6D, 0x87,
    0x92, 0x0A, 0x04, 0x19, 0x14, 0xFE, 0x76, 0x63,
    0x55, 0xDF, 0xBD, 0x68, 0x61, 0x59, 0x31, 0x8E,
    0x68, 0x7C };


texts: Can I use zero-knowledge proofs on pre-image of symmetric encryption?

texts:
Let $e_x$ be a symmetric encryption function in regards to key $x$. Let $y_1 = e_1(x_1), y_2 = e_2(x_2)$.
My goal is to prove that:
$$x_1 = x_2$$
Is there a way of proving this using ZKP? I can't seem to find anything on zero-knowledge proofs on symmetric encryption.
My ultimate goal involves a hash function $H$ and $y_1 = e_1(x_1), y_2 = e_2(H(x_2))$ where I want to prove that $x_1 = x_2$, but that may be too much to ask for right now.


texts: Convert m-Sequence into a de Bruijn Sequence

texts:
In his paper Alternating Step Generator Controlled by de Bruijn Sequence, C.G. Günther states on page three that

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

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


texts:
I am trying to understand XL algorithm and F4/F5 algorithms for solving multivariate polynomial systems.
Is XL related to the Grobner basis?
I would be grateful if anyone could suggest me the topics (related to solving degree, groebner basis?) I need to read to understand these algorithms.
Thanks!


texts: How to formally prove that random guess is the best attack

texts:
How to formally argue that there exists no efficient $A$ who can come up with a $e$ such that $$\begin{align}x&=PRF(e,0) \land \\ y &= PRF(e,1) \land \\ x &= H(y)\end{align}$$ where $H$ is a secure hash function and $|x|=|y|=\ell$?
Note that it's easy to argue that if $A$ just guesses randomly, the success probability for each guess is negligible (something like $\frac{1}{2^{\ell}}$). But how to argue there is no better algorithm than guessing?


texts:
Lets assume we have a DRGB (deterministic random bit generator) which is seeded by a good true RBG (random bit generator). Before any bit has been read from the DRBG, the entropy is clearly the number of bits of the seed.

But is entropy lost, when I read out the bits of the DRBG?
From an information theoretical point , one could say that entropy will diminish by 1 with every bit I read from the DRBG.
But how could this be defined from a complexity theoretic point?
Does there exist a precise mathematical definition of a "complexity theoretic entropy measure" ?

Maybe that question sounds a bit philosophical, but it also has practical impact, because one can decide when its time to reseed.


texts: How do I classify my RSA encryption strength?

texts: So I generated 2 1024 bit prime numbers, I generated N and got a 2048 bit number, does that make my encryption 2048 bit or 1024 bit?


texts: Designing Secure Multi-Party Computation Sub-Protocols Based on Homomorphic Encryption

texts:
When designing SMPC protocols using secret-sharing, it is a common approach to compose a protocol from several sub-protocols (each proven secure under the formal definition of security w.r.t. semi-honest or malicious adversaries) by applying the sequential composition theorem. These sub-protocols obtain shared input and provide shared output.

When designing SMPC protocols (independent of a specific framework) using a (semantically secure, probabilistic) homomorphic cryptosystem, e.g., Paillier, it is desirable to modularly compose protocols, too. In order to prevent the leakage of intermediate computation results, usually it is necessary to define sub-protocols in such a way that they get (homomorphically) encrypted input and provide (homomorphically) encrypted output. In some of these sub-protocols, ciphertexts $c$ are computed (e.g., the encrypted result of a multiplication of two encrypted integers) which can not be simulated by generating ciphertext $c’$ of the same plaintext (i.e., $\text{Decrypt}(c) = \text{Decrypt}(c’)$) from simulator's input only. Some authors which propose such kind of sub-protocols let the simulator simulate such ciphertext by an arbitrary ciphertext or a random encryption of $0$ (under the corresponding public key) and refer to the semantic security of the underlying cryptosystem in the corresponding security proof when arguing that the simulated view is computationally indistinguishable from the view of a (real) protocol execution.

The question is whether it is correct to simulate such ciphertext by a random ciphertext or a random encryption of $0$? Since the keys are fixed from beginning (the sub-protocols input are ciphertexts), isn't it possible to give the secret key to the (non-uniform) distinguisher as an extra advice (the only restrictions for the advice is that its bit-length is polynomial in the security parameter), and thus allowing the distinguisher to decrypt? With the ability to decrypt, the distinguisher would be able distinguish between a random ciphertext (or a random encrypted of $0$) in the simulation and a ciphertext of the correct plaintext in the (real) protocol execution.


texts: Plaintext for randomness evaluation of cryptographic algorithms?

texts:
I’m running an experiment to test the randomness output of many cryptographic algorithms based on INST test suite to measure the randomness of their outcome.

However I’m searching to a sample data set to perform the experiment. Based on my understanding the data set should be non-random to be able to measure the randomness after applying the cryptographic algorithm.

What plaintext should I use for this?


texts: Authentication and encryption of messages

texts:
I have a hybrid scenario of public key cryptography in which messages between users are encrypted using AES with a symmetric key generated ad hoc.

A typical hybrid system scheme considers for every message to send the couple composed of:

The message encrypted with the symmetric key
The symmetric key (using AES GCM I suppose I have to include also the IV used and additional data? - And what additional data could I use?) encrypted with the recipient's public key

I want to sign the messages in order to authenticate the sender and - if possible - to authenticate also the data.

I want to ask you if in my scenario would it be better if:

1) I authenticate the message in plaintext enciphering it with the sender private key, then encipher the result (x) with the AES KEY obtaining y and lastly send the pair (AES key enciphered with recipient's public key; y)

2) I encipher the message with the AES key, then I encipher the AES key  with the recipient's public key obtaining x and then I apply my private key to the pair (symmetric encyphered message, x). Finally I send the result.

I also checked the answers to this question in order to understand better this topic:
Should we sign-then-encrypt, or encrypt-then-sign?

In order to allow data authentication should I add to one of the above schemes a MAC? How?

And, finally, does AES GCM provide for authentication in itself without other constructs to work with?


texts: I want forgery ECDSA when prime p is form of 2*n+1, n is order of Elliptic curve

texts:
I have parameters of an elliptic curve s.t $p=2n+1$ , when $n$ = order of elliptic curve over finite field of order prime p.

If I want to forge any message for such ECDSA, What can I do? Maybe the condition $p=2n+1$ will be helpful, but I have no idea for this.


texts: Is a cryptographic key of size $N$ equivalent to $N$ bits of entropy?

texts: Are there any caveats to the claim that a cryptographic key of size $N$ bits and $N$ bits of entropy are equivalent?


texts: Shamir Secret Sharing: Why cannot we recover polynomial's root if we have $t-1$ shares?

texts:
Imagine we have $t-1$ shares in $(t,n)$ shamir secret sharing. So at least $t$ shares are needed.

Question: Why cannot we use $t-1$ shares to find a root of the polynomial and then recover the secret?


texts: Why is a 1 added after the message input and before adding padding zeros (if necessary) when using SHA256 or RIPEMD160?

texts: In preparing an input for SHA256 or RIPEMD-160 a single bit (1) is appended to the message before adding any necessary zero padding and before adding the bitlength (64 bits) to form 1 or more 512 bit blocks. What is the purpose of adding the single bit (1)?


texts: Forging RSA1024 signature with e=3 where hash is right justified

texts:
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?


texts: Why did the MARS cipher receive such a high number of negative votes in the AES competition? As I understand only MARS and Serpent implement measures to counter future cryptoanalytic attacks, so it would seem that it is one of the most secure ciphers in the competition. Am I missing something?


texts:
I have spent some time studying the "Mental Poker" protocol (sometimes
called SRA), initially proposed by Shamir, Rivest, and Adleman --
http://people.csail.mit.edu/~rivest/ShamirRivestAdleman-MentalPoker.pdf

Much of the current literature surrounding SRA deals with
implementations, most of which seek to address specific problems like
handling of the virtual card deck, player dropouts, and so on. I
understand these to be protocol problems, not algorithmic problems or
problems specific to the cryptosystem (algorithm + key generation and
management). I'm interested in finding flaws or weaknesses within
the cryptosystem.

So far I've noted:

Information leakage via quadratic residues / non-residues with a prime
modulus (Legendre symbol)
Unpadded or poorly padded "plaintext" numerical values
Potentially novel approaches to the discrete logarithm problem (such as
http://link.springer.com/chapter/10.1007%2F978-3-642-55220-5_1)
Short key lengths (similar to RSA key-pair bit lengths)
Use of a composite modulus rather than a prime
Weak Pseudo-Random Number Generator

Assuming one can sufficiently address known performance issues (like
Crepeau's 8-hour-long card deal), does SRA have additional known
weaknesses or drawbacks? Would some RSA caveats apply here too?

I noted the answer to What is the theoretical and practical status of mental poker?. This was an
excellent reply but I did not notice mention of specific publications
such as Don Coppersmith's "Cheating at Mental Poker".

I appreciate your comments.


texts: How does RSA public and private key structure look like?

texts: So I was reading this wiki about the RSA algorithm and I read this article to understand it better. My goal was to create a simple program that would generate private and public keys. I got to the point where I have the e and n variables for the public key but I have no idea what should I do with them. What's the rule to follow while connecting two of this variables? Sure I can just do it my way because it's not a big deal to transform them into strings and put "&" between them, but this way this key would be readable only by my program and this is not what I try to accomplish. I can't find anything about it on the internet so I ask here for help.


texts:
By the standard security definition of a Pseudo Random Generator, if $G$ is a PRG, then $G'$ such that $G'(0\mathbin\|x)=0\mathbin\|G(x)$ and $G'(1\mathbin\|x)=1\mathbin\|G(x)$ is a PRG. We can build a PRG which output starts by some bits of its input, to some arbitrarily large extent.

This means that feeding a practical source of entropy to a PRG secure by that standard security definition can be very unsafe.

Do we have a stronger security definition of PRG (or some other standard cryptographic construction) that avoids this pitfall, and insure security of the output when the input as some (min)entropy?

Addition: there's nothing wrong with the standard definition of PRG. It is consistent, and useful. It's just not what's needed in some cases, including stretching an imperfect entropy source. I'm asking if we have some stronger security definition of crypto-gismo-with-a-PRG-interface avoiding such issue. Much like for hash we have security in the ROM that's stronger than collision and (first and second) preimage resistance.


texts: What's the reasoning behind the design of the TLS 1.2 PRF?

texts:
TLS 1.2 defines a PRF-like construction $P_{hash} : \{0,1\}^* \times \{0,1\}^* \rightarrow \{0,1\}^l$ for key derivation, etc. To quote the spec:

  We define a data expansion function, P_hash(secret, data),
  that uses a single hash function to expand a secret and seed into an
  arbitrary quantity of output:

P_hash(secret, seed) = HMAC_hash(secret, A(1) + seed) +
                       HMAC_hash(secret, A(2) + seed) +
                       HMAC_hash(secret, A(3) + seed) + ...

  where + indicates concatenation.

  A() is defined as:

A(0) = seed
A(i) = HMAC_hash(secret, A(i-1))

Why does $P_{hash}$ invoke HMAC twice per block of output? Are there valid security arguments for doing so?

In particular, why not a simpler, faster, counter-based scheme such as:

  $P_{hash}(\text{secret}, \text{seed}) = B(\text{secret},\text{seed},0) \| B(\text{secret},\text{seed},1) \| \dots
\\ B(\text{secret},\text{seed},i) = \text{HMAC}_{hash}(\text{secret}, \text{to_byte}(i) \| \text{seed})$

If there is no technical advantage, what are the historical reasons behind this design?


texts:
Considering public message M and private key K, would it be safe to create the MAC tag this way:
$$MAC(M,K) = AES(m_1) \oplus AES(m_2) \oplus \cdots \oplus AES(m_n)$$
when $m_1,m_2,\ldots,m_n$ are n blocks of fixed size (let's say 128).
I can't prove that it's secured although my intuition says it is.


texts: Consider I have two ciphertext $c_1$ and $c_2$ encrypted using RSA encryption. By definition if I multiply them I'd get $c_1.c_2 \ modN$. My question is what would happen if $c_1.c_2 >N$. Can we still decrypt it and obtain the product of two plaintext?


texts: How to require two PRIVATE keyholders to decrypt a document?

texts:
Consider 3 entities A,B and C. I want A to be able to encrypt a document that can be decrypted only when keys of both B and C are combined. This question talks about a similar problem, but it uses AES.

In my usecase, I don't want the keys to be shared across the entities. There is one solution that was coming to my mind:
A encrypts the document (with RSA) first using public key of B and then public key of C. Then the document is decrypted using private key of C and then private key of B.

Is this approach feasible? Is there a better way?

Note: I tried doing this but got this error when I was doing encryption for the 2nd time: Data must not be longer than 117 bytes.


texts: Generating Diffie-Hellman parameters efficiently

texts:
I am working on an Android project for school and I am supposed to do a DHKE (Diffie Hellman Key Exchange). Everything works well.  The problem is that it takes a lot of time (really a lot) to generate DHParameters. Basically, in my code, this is the part that is the most time (and battery) consuming:

KeyPairGenerator kpgDH = KeyPairGenerator.getInstance("DH");
kpgDH.initialize(512);
KeyPair kpDH = kpgDH.generateKeyPair();

As you can see, the key length is only 512 bits, so it's not long, and it still takes at least 30-40 seconds (best case scenario), but it can go up to 400 seconds. I've tested it on several phones: Samsung Galaxy s2 (quad core), Samsung Galaxy s4 (quad core), Samsung Galaxy note 10.1 (quad core).

Does anybody know an alternative to generate more quickly the $p$ and $g$ for the Diffie-Hellman in order to speed up the process?


texts:
I was wondering if it is possible to decrypt a cipher-text using a single key which was encrypted twice.

For example: Let's assume that we encrypt a plaintext using AES-CTR and encrypt the output again with AES-CTR using a different key. It's clear that there exists a keystream that can be used to decrypt the message in one step. However, I do not know if this keystream can be generated by the AES algorithm and if we can calculate the respective key efficiently.

Dos anyone know if this is possible or has a keyword, article, blog post I could look for?

PS: I know that this will NOT increase the security.


texts:
On a few occasions I've converted URLs with authentication via a session cookie to deep link URL's with no cookie authentication. These are URL's with simple id's like /download/pdf/1.

I convert them to deep links either by appending a HMAC of the ID (/download/pdf/1/7e3aefd25fb9…) or encrypting the ID using AEAD and omitting the id from the url (/download/pdf/7e3aefd25fb9…).

In both cases I store a longterm key on the server which is used for all deep links.

I was wondering: which (if any) of these approaches is best practice?

I like the HMAC approach because it clearly states the intent.
I like the AEAD approach because the programmer cannot read the ID from the url and then accidentally forget the authentication.

(I realize there is a third option which is to use an entirely random number for the deeplink. This is the simplest cryptographically speaking, and the best practice I suspect. But it has downsides because you must store these numbers and references to which resources they belong. Generating the URLs can't be done "on the spot" any more, you must push to the centralized storage.)

Usage scenarios:

The URL must work inside an iframe where cookies cannot be used in some browsers
The URL is automatically opened by another application such as Androids PDF reader which has no access to your browser cookies
We send an email with the resource URL and the recipient has no account in the system
We wants the users to be able to share the resource without sharing their credentials

Description of the attacker:

he uses HTTP
he might have access to the website as a cookie-authenticated user but NOT to all resources
he might have some valid deep links in his possession
he can easily guess a valid ID
he should not be able to create a valid URL from an ID unless it was provided to him
he should not be able access the resource


texts:
This is a purely hypothetical example but is provable ignorance useful in cryptography?

For example, let's say I have a trapdoor collision resistant function. I know the trapdoor and therefore some $x_0 \neq x_1$ such that $f(x_0) = f(x_1)$. This is however, hard to find. If someone proves they know $x_0$, I can conclude that they do not know $x_1$.

Is there any context where more complicated versions of such problems is useful?


texts: Generating unbiased numbers with a biased six sided die?

texts:
Eve takes a fair six-sided die and adds some heavy paint to the side of the die with the 6 on it. This results in a biased die that rolls a 6 with probability 2/7, and each other number (1-5) with probability 1/7.

If Alice learns that the die is loaded in this way, only has this die, and must generate 20 fair/unbiased random numbers between 1 and 6, what procedure can I propose that she can use to generate these fair numbers with this unfair die and computing how many times (exact or on expectation) Alice will have to roll the tampered die to conduct this procedure.


texts:
Reading through the DSA signature specification, one thing stood out for me.

$r = (g^k \bmod{p} ) \bmod{q}$

Then $s$ is computed. In the computation above, why is the modulo $p$ required, given we are anyway reducing it with a modulo $q$?

To clarify, just doing a modulo $q$ will achieve the result of reducing the number to within the bounds of q. Doing a modulo $p$ seems like an extra step and that indicates that a simple reduction of the number to the bounds q is not the only objective. Why is modulo $p$ needed, cryptographically speaking?


texts:
Can SHA-256 be substituted for Blake2 in the Argon2 algorithm?

I am working my way through the C reference source code for Argon2 and hand-translating it to Go. I was just wondering why Blake2 was chosen instead a well-tested algorithm like SHA-256.


texts: EC ECKA-ElGamal Key Agereement availability in Bouncy Castle Java library

texts:
I am trying to generate shared secret from remote EC public key(static) and client EC private key(ephemeral). In this process I am successfully able to generate shared secret using ECDH Key agreement available BC library.My work requirement is to use ElGamal key agreement but there is no specific supported Key agreement representing ECKA-ElGamal.

I was wondering if you can help confirm that ECKA-ElGamal is indeed a version of ECKA-ECDH where remote public key is static and client ephemeral key is dymanic.

Code snippet:

//I am using ECDH
KeyAgreement ka = KeyAgreement.getInstance("ECDH","BC");

// clientEphemeralPrivateKey is Client ephemeral Private key already generated
ka.init(clientEphemeralPrivateKey);

//serverECCPublicKey is remote server public key
ka.doPhase(serverECCPublicKey, true);


texts: Why can't you decrypt an encrypted message with just the public key?

texts:
How does asymmetric crypto work?
For example, if you use PGP in emails, you generate a private key that is known only to you and a public key, which is available to everyone.
Is there a simple way to explain, why you need a private key and why no one can decrypt the message with just the public key?
I think of an explanation like for example with prime numbers:

If you multiply two large prime numbers, you get a huge non-prime number with only two (large) prime factors.
Factoring that number is a non-trivial operation, and that fact is the source of a lot of Cryptographic algorithms. (See one-way functions for more information.)
The product of the two prime numbers can be used as a public key
The primes themselves as a private key. So the private key is the knowledge of two very large prime numbers

for easy understanding lets take the simple example (very large) prime numbers: 3 and 5:

private key: the knowlege of 3 and 5
the public key is just those numbers multiplied: 15
you cannot find out 3 and 5, so the message encrypted with 15 is ...

Here is a quite good explanation already, but it is not clear enough:
Is there an intuitive explanation as to why only the private key can decrypt a message encrypted with the public key?
Can you please add an example with those numbers?


texts: What does "learnable with oracle queries" mean?

texts:
I came across the following quotes in reading papers on obfuscation (1, ibid, and 2):

  The next result follows from the fact that point functions are not exactly learnable (since a uniformly chosen point function is statistically indistinguishable from the all-zeroes function given a polynomial number of membership queries).

and

  A family of circuits $C \in C_n$ is obfuscatable against general adversaries iff $C$ is (nonuniformly) efficiently and exactly learnable using membership queries.

and

  Of course, if the function is (exactly) learnable via oracle queries (i.e., one can acquire a program that computes the function by querying it at a few locations)

What does it mean to say a program is learnable using membership queries? Or alternatively, I've seen it as "learnable with oracle queries". And what is the impact of it? Does it mean that we can learn what exactly the program does or just enter input and receive the result of the program running in each step? Without knowing which mathematical action influenced it?


texts: How exactly is an enigma simulation software supposed to encrypt alphabets?

texts:
EDIT: The model I'm trying to make is "Enigma 1". I learned initially about it from a book called "Code Book" and then looked at it in detail from its wikipedia page. The rotor wiring and other details from https://en.wikipedia.org/wiki/Enigma_rotor_details

I am trying to make an enigma machine simulating software. I know how the machine works but am having trouble trying to understand what my code's logic should be BEFORE the alphabets get to the reflectors.

Suppose 1, 2 and 3 represent each rotor's settings in an enigma machine (they're what I got from wikipedia):

  abcdefghijklmnopQrstuvwxyz
1:ekmflgdqvzntowyhxuspaibrcj

  abcdEfghijklmnopqrstuvwxyz
2:ajdksiruxblhwtmcqgznpyfvoe

  abcdefghijklmnopqrstuVwxyz
3:bdfhjlcprtxvznyeiwgakmusqo

And suppose the message is "A". Here's what I think should happen: From the first rotor, the message could have become "E" but because the rotors spin by one unit before the encryption, it is encrypted to the next letter in the setting: "K".
Now to find what happens in the second rotor, we need to see the 11th letter in the setting (or the letter below K) which is "L".
Similarly for the final rotor, we see the 12th letter (below "L") which is "V" and that from my understanding should be what is transferred to the reflector and then back.

Though my software is complete with ring settings, plugboard and all the other stuff and it can decrypt it's own encrypted messages the way it is supposed to, the ciphertext is never the same as what online enigma simulators produce for the same settings, nor can it decrypt original messages even if I know all the settings. If you go here:
http://people.physik.hu-berlin.de/~palloks/js/enigma/enigma-u_v20_en.html
click "show monitor" button and type "a" you will see that before it reaches the reflector, it is translated as "H". So clearly I'm doing something wrong.

Can somebody please help me out?


texts: Are points in Elliptic curve uniformly distributed?

texts:
I need to find an isolated point in an elliptic curve that has the farthest distance from other points.

For example, if we take an elliptic curve $E_{13}(a,b)$, then according to Hasse's theorem, the possible number of points $\#E(p)$ lies between $(13+1-\sqrt(13),13+1+\sqrt(13)) \approx (11,17)$. Considering the worst case, we take $\#E(13)=11$. One of the points is $(0,0)...1^{st} point$. Since elliptic curve points often come in pairs let us take the other points as

$(1,y_1)...2^{nd} point;$  $(1,13-y_1)...3^{rd} point;$

$(2,y_2);...4^{th} point;$  $(2,13-y_2);...5^{th} point;$

$(3,y_3);...6^{th} point;$   $(3,13-y_3);...7^{th} point;$

$(4,y_4);...8^{th} point;$   $(4,13-y_4)...9^{th} point;$

The remaining two points be $(12,y_5)...10^{th} point;$   $(12,13-y_5)...11^{th} point$.

In the recent experiments I have performed, I have found no such curve where a cluster of points exist farthest away from an isolated point pair.

My question: Is there an Elliptic Curve that exhibits such a characteristic ?

OR

Are points in an elliptic curve always uniformly distributed ?


texts:
This question is a follow up to the question I asked here. Basically, the protocol I described  has a flaw (as pointed out in this answer), and I am trying to figure out how to address it. The setup is:

Alice has a secret value $a$ to which she's publicly committed by sharing $A=a∗G+X_a$, where $X_a$ is her public key
She calculates a new value $a' = a - c$
And then  publicly commits to $C = c *G$ and to $A′=a'∗G+X_a$

An independent observer can check that the math was done correctly by verifying that $A=A′+C$. However, this doesn't quite work because Alice can underflow $a$ and the verification would still pass.

One way to address it that I can think of is for Alice to prove that $a > c$ (or that $a' < a)$, but I'm not sure how this can be done without revealing $a$ or $c$.

Edit2: removed a potential approach because it doesn't seem to work.


texts: Comparing DES and DES-X variation: $Enc(m) = DES_{k_1}(m \oplus k_2)$

texts:
I came across this question:

Test the security of the following variation of DES-X cryptosystem, which uses 2 keys $k_1$ and $k_2$:
$$Enc(m) = DES_{k_1}(m \oplus k_2)$$

(Basically, it uses the 2nd key to xor the text before the DES encryption)

So, I've started researching it and i got confused.

In general, lots of people suggested that XORing the original text or the ciphertext provides extra security only against brute-force attacks.

However, in this very-similar-question, the first answer states that the extra XOR " has almost no advantage compared to DES (even) in term of resistance to brute force".

Both got me confused because, in this illustration of the simple DES, lots of different keys are generated to XOR blocks of the text several times, so I guess the same is happening twice in the variation above (or 3 times in case of DES-X). As I see it, something like this really messes things up.

Is this really so useless even against brute-force attacks? And if so, can you explain it a bit?


texts: What (if any) information can an eavesdropper infer in this scenario when using DES in OFB mode?

texts:
Assume that a company wants to use DES in order to encrypt messages
to remotely control its manufacturing machines. The company uses different
messages types of 8 ASCII characters length each. The message payloads consist of
simple operational orders like starting machines, stopping them, speeding up, etc.

The company considers to run DES in OFB mode (i.e., as a stream cipher). Assuming
the eavesdropper has somehow figured out that the majority of all exchanged
messages carry the payload INACTIVE. What (if any) information can
an eavesdropper infer?

Any suggestions ???


texts: 2PC Private Set Intersection Optimized for asymmetrically sized sets

texts:
I am researching some concepts of practical 2 party computation and was curious if anyone could point me to a research paper that is focused on private set intersection where one party has a very large set and the other has a comparatively small set.  Specifically, a user has a small set and the server has a large set.  Since the server will handle thousands or millions of requests, I am more concerned about the performance for the server.

The specific use case that I had in mind is contact discovery.  Meaning, a user wants to know who else is using a service but does not want to disclose their contacts to the server in plain text.  Ideally the server does not learn the outcome of the intersection.  At a minimum the server should only learn the size of the users contact list and the results of the intersection.

I found this paper that appears to be a breakthrough in performance but it's benchmarks are based on two sets of equal size.  Is there existing research on a PSI that is optimized for non-equal set size?


texts: Multiplication vs exponentiation in pairing based cryptography

texts:
$$P\in G_1$$$$Q\in G_1$$          $$a,b \in Z_q$$         $G_1$ isadditive cyclic group of prime order $q$
$$e(P^{a+b},Q)------(1)$$
$$e(aP+bP,Q)----(2)$$
(1) and (2) will give the same pairing result $e(P,Q)^{a+b}$.
In (1) and (2), despite of same pairing result, is there difference in terms of security or performance for different operations (exponentiation, multiplication and addition) in $P$?In (1), I don't know clearly about exponentiation is allowed or not with randomly generated $P$ value from additive group.


texts: Efficient pen-and-paper calculation of the Galois Field multiplication?

texts:
I have been reading on multiplication over GF for the Inverse Matrix Step in AES, and I feel like converting the hex numbers to binary, multiplying them and then doing the modifications required for GF arithmetic is too time-consuming when done by hand.

It would be very helpful if someone could help me with a faster way to do it.


texts:
I want to implement computing ECC operations (i.e., multiplication) in a BMR scheme (secure multi-party computation)
What is the best way to do it?
I found Fairplay MPC - to allow BMR computation through ASFL language, but it does not provide a good library for ECC operations.
Instead, CHARM implements several cryptographic functionalities, but without MPC.
Is there anything that combines the two approaches? (Both MPC and ECC operations)?
Edit: This question is about ECC operations as one component in a general MPC scheme.
CHARM
FairPlay


texts:
Can anyone provide an extended (and well explained) proof of correctness of the RSA Algorithm?

And why is it needed?

I can't say that this or this helped me much, I'd like a more detailed and newbie like explanation, if you don't mind too much... ;)


texts:
I'm not a mathematician, and i would like to understand in the most concise way (if possible) why choosing linear S-Box functions makes the DES algorithm attackable.
Thanks


texts:
I am building a simple one time pad system using a low-power microcontroller to XOR a stored key with an input string, and vice versa. Due to several internal factors, it's very preferable for the system to use only the 95 "printable ascii" chars instead of full 256-values bytes to represent pad keys. Since the input is restricted to simple plain-ascii as well, that should be enough coverage if I understand the OTP process correctly.

My pad-making question is about converting random 0-255 values to plain-ascii chars, representing 0-94 or so. Would it be more secure to convert each 0-255 value (x) using:

x % 95 (x mod 95) to get all the possible chars, but with the 65-94 values being 50% more likely than 0-64 values.
int(x / 3), to get a uniform distro of keys chars from 0-84 value, where each value has odds of 3/255 (~1/85) of being used.

While #1 has 10 more key possibilities, #2 has uniform distribution, and I can input from an 85 "letter" alphabet if needed (instead of 95).

Given a random 0-255 input, which down-conversion likely results in better security?

edit: fixed the unclear range "0-85" and "0-95" to reflect 85 and 95 possibilities.


texts: If they exist a relation between decisional Diffie-Hellman assumption and composite decisional residuosity assumption

texts:
From the cryptographic hardness assumptions, we have DDH and CDR assumptions.
It is known that the composite decisional residuosity assumption is related to a factoring problem, while the DDH is related to a discrete logarithm problem. I need to know if there is a method or a mathematical theorems that can provide ways to map from DDH to CDR assumptions and if the mapping between the two assumptions is possible.


texts: Best attack on double DES followed by XOR with third key

texts:
What is the best attack here?

  $E_k(m)=DES_{k1}(DES_{k2}(m)) \oplus k3$