texts: How to test an implementation of a homomorphic scheme?

texts:
I want to implement the following homomorphic encryption scheme from On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption by Lopez-Alt et al. I use C++ and I want to know before start to write code how am going to test my application, what test cases would be useful to imagine for such an application ?

I think to feed my application with inputs behind limits and other tests like this which are considered for every application, but maybe there are some kinds of tests for cryptographic implementations, special things that must be taken account.

For example, if I were to implement a hash function I would test it so that it hasn't significant more collisions than expected by theoretical results. I believe that the same stragegy applies in my case.


texts: Is "double-and-add-always" a good mitigation against side channel attacks?

texts:
In Discrete Log based Cryptography, one of the core operations that one, has to perform is modulo exponentiation. There are many algorithms to choose from, especially, when considering my point of interest "scalar multiplication" of a point (generator) of an Elliptic Curve. The most fundamental algorithm is the double and add method, that runs in logarithmic time. But since, the cost of point doubling is different, from the cost of point addition, branching based on secret bits will cause, the secret bit to be leaked to the adversary.
As a mitigation to this, we could do a sort of, dummy addition every iteration and hence the "double and add always" algorithm ! This will camouflage the time difference, I guess. I realize, that there are other algorithms like Montgomery Ladder but Wikipedia says that there exists FLUSH+RELOAD attack on an OpenSSL implementation that uses it.
But are there better algorithms ?
Will there be performance/ security benefits if we migrate to a different coordinate system?
I'm asking this, because I coded an Elliptic Curve implementation from scratch using my custom multiprecision library written in C as a learning project. But in my library, I use extended euclidean algorithm for calculating modulo inverses (for performance sake) in $F_{p}$. And also, my multiprecision division algorithm is not constant time, it runs in logarithmic time depending on the dividend bit length. These are some bottlenecks that I think is difficult to overcome as far as multiprecision is concerned !  Still my overall working implementation is no way as fast / secure as OpenSSL or other amazing libraries out there and it is not intended to be! But, I would love to know more about secure & fast implementation!


texts: Are multi move proof protocols still "sigma protocols"?

texts:
Conventionally, sigma protocols are defined as being a three-move protocol (1. commit, 2. challenge, 3. response). Reading papers like "Bulletproofs" (Bunz, Bootle, Boneh et al., 2018), it feels like the authors avoid to call their protocols "sigma protocols", although their protocols are always repeats of either 1, 2 and 3 or only 2 and 3; i.e., the verifier only issues (field element) challenges and the prover repeats a response and commit.

Is there a technical reason that the term "sigma protocol" cannot be generalised to multi-move protocols?


texts: Is the random oracle commitment scheme secure against PPT active adversaries?

texts:
The probability that a probabilistic polynomial adversary corrupting the sender can finds two pairs $(m,r)$ such that the output of the random oracle $c$ is the same (break the binding property) is negligible.
At the same time, the probability that a probabilistic polynomial adversary corrupting the sender finds a pair $(m,r)$ starting from the commitment $c$ (break the hiding property) is negligible.
Is there any difference between the case in which the adversary is semi-honest or active in this context? The only threat I see is that an active adversary could change the message of the sender, but this is not relevant since the sender could have chosen that message.


texts: Prevent hash collisions with HMAC secret as IV

texts:
Our organistation would like to hash large file paths to asssign to a specific object. To prevent hash collisions, I thought we can use the same sort of technique as we use to prevent rainbow tables in password hashes. When you hash the value 'sample data' we will first prepend an IV, which will be used as hmac secret to verify the hash.

function makeHash($data,$algo='sha256',$ivKey=null) {
  if(empty($ivKey)) {
 $ivKey = openssl_random_pseudo_bytes(16);
  }

    $result = $ivKey.hash_hmac($algo,$data,$ivKey,true);
 return base64_encode($result);
}

function verifyHash($data,$hash,$algo='sha256') {

  $result = base64_decode($hash);
   $ivKey =  mb_substr($result,0,16,'8bit');
   $dataHash = makeHash($data,$algo,$ivKey);

  return $hash == $dataHash;
}

Usage example:

$hash = makeHash('sample data');
echo $hash;
var_dump(verifyHash('sample data',$hash));
/**
Output:
 I9Kl9Mkq/6ee3xQixrDn3YImRAywz0rhmBBxRjrfRWiGeRuBrIkREirgKBDr8Gzh
 bool(true)
*/

Would this be a good way to prevent collisions?


texts: How to figure out the size of the output of a cryptographic checksum function

texts:
In Bishop's Introduction to computer security, on page 118, we see the following:

  Definition 8–2. A cryptographic checksum function (also called a strong hash function or a strong one-way function) $h: A → B$ is a function that has the following properties:

  For any $x ∈ A$, $h(x)$ is easy to compute.
  For any $y∈B$,it is computationally infeasible to find $x∈A$ such that $h(x)=y$.
  It is computationally infeasible to find $x, x' ∈ A$, such that $x ≠ x'$ and $h(x) = h(x')$. (Such a pair is called a collision.)

  The third requirement is often stated as:

  Given any $x ∈ A$, it is computationally infeasible to find another $x' ∈ A$
  such that $x ≠ x'$ and $h(x') = h(x)$.

  However, properties 3 and 4 are subtlely different. It is considerably harder to find an $x$ meeting the conditions in property 4 than it is to find a pair $x$ and $x'$ meeting the conditions in property 3. To explain why, we need to examine some basics of cryptographic checksum functions.

  Given that the checksum contains fewer bits than the message, several messages must produce the same checksum. The best checksum functions have the same number of messages produce each checksum. Furthermore, given any message, the checksum it produces can be determined only by computing the checksum. Such a checksum function acts as a random function.

  The size of the output of the cryptographic checksum is an important consideration owing to a mathematical principle called the pigeonhole principle.

  Definition 8–3. The pigeonhole principle states that if there are $n$ containers for $n + 1$ objects, at least one container will hold two objects. To understand its application here, consider a cryptographic checksum function that computes hashes of three bits and a set of files each of which contains five bits. This yields $2^3 = 8$ possible hashes for $2^5 = 32$ files. Hence, at least four different files correspond to the same hash.

  Now assume that a cryptographic checksum function computes hashes of 128 bits. The probability of finding a message corresponding to a given hash is $2^{–128}$, but the probability of finding two messages with the same hash (that is, with the value of neither message being constrained) is $2^{–64}$ (see Exercise 20).

How to get the final $2^{-64}$ mathematically?


texts: As the Logjam attack allows a Man-in-the-Middle attacker to downgrade vulnerable TLS connections to 512-bit export-grade cryptography by modifying the ClientHello and ServerHello, can the Logjam attack be avoided by verifying the integrity of the ServerHello?


texts:
$F_k$ is a PRF , $k\in\{ 0,1\}^n$ , is $H_k(x) = F_{k_1}(x)||F_{k_2}(F_{k_1}(x))$ a PRF?
when $k=k_1||k_2$ , $k_1,k_2\in\{ 0,1\}^n$ and $k\in\{ 0,1\}^{2n}$ are random strings ,
im trying to prove it using the hybrid argument such that :

$H_0$ be $F_{k_1}(x)||F_{k_2}(F_{k_1}(x))$
$H_1$ be $f_1(x)||F_{k_2}(f_1(x))$ when $f_1$ is a random function
$H_2$ be $f_1(x)||f_2(f_1(x))$ when $f_1 , f_2$ are a random functions.

$H_0$ is $H_k(x)$ and the underlying assumption between $H_0$ and $H_1$ is $F_k$ .
$H_2$ is equal to a random function and the underlying assumption between $H_1$ and $H_2$ is also $F_k$  .
im not very sure about it so i’m asking for opinions and suggestions or maybe a counter example for not being a PRF.


texts: I checked RSA's patent application, which was registered in 1983. As patents don't last more than 20 years, it seems to me it should be free. But my friend said to use RSA I have to buy a license from MIT. Is it true ?


texts: How many Hashes to find a digest of 2^{n−k}?

texts:
Given an n-bit cryptographic hash function $H$, how many messages should we expect to hash before  finding a message $x$ such that $H(x) < 2^{n−k}$ for some integer k?

My take: Shouldn't it simply take on average $2^{n-k}/2$ to find the hash?


texts: Is an invulnerable code possible (including brute force attack)?

texts:
If I double encrypted a text with for example AES wouldn't it be invulnerable to bruteforce attacks due to the computer not knowing when it has reached the plain text?

Plain text->1st layer of encryption->2nd layer->output


texts: Choice of padding scheme to prevent CBC padding oracle attacks?

texts:
I was watching a lecture about the padding oracle attack on CBC mode block ciphers, where the padding scheme used was PKCS#7.

My question is can padding oracle attacks be prevented (without any use of a MAC) solely by choosing a suitable padding scheme?

In the lecture, the attack first finds what the actual padding of the plaintext will be. I assumed that the rest of the attack outlined in the lecture worked only because PKCS#7 is a predictable padding scheme. Which means that once the adversary gets a BAD_PAD error, he will know that there is only one possible pad that will be the correct pad.

If the padding scheme used is unpredictable, would the CBC mode be secure against padding oracle attacks?

I was thinking of the following padding scheme:

Choose distinct and random bytes X and Y, which will be different every time you encrypt a message. Pad with X and at least one copy of Y. So if the block length is 8 bytes and your message is ABCD, you can pad the block to be ABCDXYYY, ABCDXXYY, or ABCDXXXY.

Would this padding scheme prevent padding oracle attacks? Because now when the attacker gets a BAD_PAD error, he will not know for sure what the correct pad should be.


texts: Is it possible in PGP to provide verification/verify the ownership of a public key?

texts: I am new to PGP/GPG and I am somewhat confused by the idea of the Web of Trust (WoT). Isn't signing a public key with its private key enough to prove the ownership of it? if it is so, why don't key servers just do that before storing the keys instead of relying on users to trust each other?


texts: Constructing secure key exchange protocol

texts:
I have $\Pi=(Gen,Enc,Dec)$ and let it be semantically secure public-key encryption scheme. Security parameter is $n$, then the message space of plaintext is always $\lbrace 0, 1 \rbrace^n$.

By using $\Pi$ I want to construct key exchange protocol $\Theta$. There should be 2 rounds (i.e. one for Alice and one for Bob). It must be secure against eavesdroppers (and it'd should be possible to prove it :) ).

Of course the only assumption is security of $\Pi$. For example Diffie–Hellman key exchange protocol fits to this exercise (if we assume somethink), but I don't know how to generalize it.

P.S. The key Alice and Bob establish $\in \lbrace 0, 1 \rbrace^n$.


texts: In W-OTS, is it trivial to forge smaller N values?

texts: Just read about W-OTS. Since the signature is the private key hashed 256-N times, is it trivial to forge a signature with a smaller value for $N$ when having access to original signature? I.e. just hash it one more time and it represents 9-1, etc.


texts:
I am looking at a tutorial on the Oracle Padding Attack, and I wondered, how do you find the rest of the blocks(not the last one), if there's only padding on 1 block?

Am I not understanding padding correctly?


texts: Randomized public-key encryption as binding commitment / "collision-resistance"?

texts:
I am looking to use randomized public-key encryption in a context where it should also serve as a sort of "binding commitment". That is, I want to encrypt a value $x$ with some randomness $rnd$ under a public key $pk$, denoted $enc(x, rnd, pk)$ for short, such that it is infeasible to find a different plaintext $x'$ and randomness $rnd'$ such that $enc(x, rnd, pk) = enc(x', rnd', pk)$ (the ciphertexts are the same).

I want this because a party A should be able to convince a party B that a given ciphertext $c$ is an encryption of a plaintext (known to the parties) $x$. For this, A would send the ciphertext $c$ and the randomness $rnd$ to B, and B would re-compute $enc(x, rnd, pk)$. When this equals $c$, then B should be convinced that $c$ is an encryption of $x$.

Is this a property that randomized public-key encryption schemes usually have, or can be derived from another property?


texts: Why are iterated substitution-permutation product ciphers only used on fixed-size plaintext blocks?

texts:
Another way to ask this question: when block ciphers were invented, why did they add the restriction that the block cipher would be restricted to blocks of a fixed size?
From my laymen's point of view, I don't see why rounds of S-box and P-box operations couldn't be performed with inputs of variable size.


texts:
My question is a follow-up to a recent question regarding quantum-secure time-lock puzzles (TLPs). TLPs can be built (in principle) from indistinguishability obfuscation (iO) [BGJ+,BGL+] as noted in this thread. As a corollary, quantum-secure iO would lead to quantum-secure TLPs (provided that there are inherently-sequential languages in the quantum world, which seems plausible).

So it boils down to whether any of the candidate constructions of iO are quantum-secure. It seems that some of the candidates are broken given a quantum computer [PM]. The question is whether any remaining candidate construction of iO is believed/conjectured to be quantum-secure?

[BGJ+]: Bitansky et al., Time-Lock Puzzles from Randomized Encodings, ITCS'16

[BGL+]: Bitansky et al., Succinct Randomized Encodings and their Applications, STOC'15

[PM]: Pellet-Mary, Quantum Attacks against Indistinguishablility Obfuscators Proved Secure in the Weak Multilinear Map Model, Crypto'18


texts: Does it increase security if the CBC chunks of a AES-256 encrypted bytestream are uploaded to different clouds?

texts:
I want to backup my data according to the 3-2-1 rule. I am already back up to 2 different drives (2 different systems) at home. In addition, I would like to use cloud storage (Google, Amazon, etc.). Considering the future weakening of cryptography by advancements in computing power (e.g. key guessing by quantum computing) I want my data to be as safe as possible because once it's uploaded it's prone to decryption in the future (i can't guarantee the data is deleted if I delete it from the cloud(s)).
Does it increase the security of my data if I split the CBC chunks to let's say 2 clouds? Uploading the even-numbered CBC elements to e.g. Google and the odd-numbered elements to Amazon. Since one storage hoster is constantly missing the next part of the CBC-Chain (1/2 in total) shouldn't this increase security of the data even if the AES key is known by the hoster(s)?


texts: Choosing between different Gaussian Sampling algorithms?

texts:
Is the gaussian sampling described in the original paper (https://eprint.iacr.org/2013/383.pdf) faster (samples/sec) than the Knuth Yao sampling.
As far as I know KY sampler is the fastest discrete gaussian sampler.
I found one survey here https://www.sav.sk/journals/uploads/0212094402follat.pdf. It mentions both of these algorithms but without any comparative analysis.


texts:
I remember I read that a MAC can be considered as a PRF.

Can a variable-length input keyed-PRF be considered as a MAC?


texts:
So we've got to do this assignment for our study, but we can't figure out what to do, can someone help?

Assume that Alice and Bob want to communicate via encrypted email. To this end, they first meet in person
and agree on a common secret key k and block cipher $(P,C,K,E,D)$ with plaintext space $P$, ciphertext space $C$, key space $K$ , encryption function $E$, and decryption function $D$. Afterwards, all email communication will be encrypted by using this chosen key and block cipher. Furthermore, assume that Alice and
Bob choose a specific block cipher in ECB-mode with $P = C = K = \{0,1\}^{128}$ and with the property that
$$E_k(m\oplus m_0) = E_k(m)\oplus E_k(m_0)$$
for the key $k$ and all messages $m,m_0 \in P$.

Now, assume that one day, Alice is using her computer in her office at work and forgets to lock her computer while she is just quickly out of office to get her lunch. In the meantime, you as the hacker go into her office (which is also left unlocked) and get access to her computer. Although you cannot get access to the secret key $k$ (which is securely stored), you can use her email client to decrypt any ciphertext of your choice.

Since you do not have much time as Alice is already coming back to her office, you are able to decrypt
exactly 128 ciphertexts.

Which are the 128 ciphertexts that you would choose to decrypt so that later on you are able to decrypt all email communication encrypted under the key $k$ (although you’ve never seen that key)?
Describe how you successfully decrypt any encrypted e-mail by using your 128 decrypted ciphertexts
selected in (1). Concretely, this means that you need to explain, how you compute the plaintext $m$ of
an arbitrary ciphertext $c = E_k(m)$ that was encrypted under the above block cipher $(P,C,K ,E,D)$.

Hint. Since Alice and Bob use ECB-mode, we can assume, without loss of generality, that all e-mails have a length of 128 bits.


texts: Is the One Time Pad secure in additive Rings?

texts:
Let's assume all operations are done on $\mathbb{Z}_p$ where $p$ is a large non-prime number.

To mask a value $a$, we do the following:

Pick a uniformly random value: $r$, from the ring.
Do as follows: $c= r+a \bmod p$.

Question: Is the above one-time pad secure?


texts: How can I match each encrypted message with the public key used to encrypt them for a common encryption attack RSA

texts:
I have five encryption mods ($n_1$ through $n_5$) with the same encryption exponent ($e$) and the same message encrypted using the five public keys giving $E_1$ through $E_5$ that were not given in a particular order. I am trying to use the Chinese remainder theorem attack (common encryption exponent attack). My question is as follows:

1) How can I match each encrypted message with the public key used to encrypt them?  Do I just have to try all possible combinations until I get readable output? Since I have five pairs it would be a lot of permutations to try...


texts: Non-interactively share secret with group without revealing to generator?

texts: Imagine someone knows a set of $n$ ECC public keys $\mathcal R = \{K_1, K_2, ... K_n\}$ but they don't know the corresponding private keys $k_1$, $k_2$ ... $k_n$. They wish to create a public key $sG$ such that anyone with a private key $k_i$ belonging to a $K_i \in \mathcal R$ can retrieve/calculate $s$. This scheme should create $sG$ such that not even the executer of the scheme can retrieve $s$. Is this possible without having to interact with the private key holders?


texts: Benchmark differences between SHA-512 and bcrypt

texts:
So I recently made a benchmark SHA-512 vs bcrypt with hashcat CUDA.

Here are the results :

bcrypt : bruteforce : ~                              400 H/s
         Wordlist + dive.rule :  ~                   550 H/s

sha512 : bruteforce : ~          870 MH/s ->   870000000 H/s
         Wordlist + dive.rule :  ~ 640 MH/s -> 640000000 H/s

Factor sha512 -> bcrypt : 1:1589473

SHA-512 is a cryptographic hash function right? So why is it so fast?

For example VeraCrypt uses it as KDF .

I am still a beginner so please explain to me in which scenarios SHA-512 is used and in which bcrypt.


texts: In what aspects is the function based on four iterations of SHA-256 compression function weaker than the SHA-512 compression function?

texts:
Let $F_{512}(B, C)$ denote the underlying function (single block manipulation function) of SHA-256. This function takes a 512-bit block $B$, 256-bit initialization vector $C$ and produces 256 pseudo-random bits (eight 32-bit words). Then I can define the following function (that operates on a 1024-bit block $B$ given a 512-bit initialization vector $C$ and outputs 512 pseudo-random bits):

$$G_{1024}(B, C) = (x_1 \oplus x_3) \mathbin\Vert (x_2 \oplus x_4),$$

where $$\begin{array}{l}
{x_1} = F_{512}({B_1}, {C_1}),\\
{x_2} = F_{512}({x_1} \oplus {B_2}, {C_2}),\\
{x_3} = F_{512}({x_2} \oplus {B_1}, {C_1}),\\
{x_4} = F_{512}({x_3} \oplus {B_2}, {C_2}),
\end{array}$$

$B_i$ denotes the first/second half of the 1024-bit block and $C_i$ denotes the first/second half of the 512-bit initialization vector.

Let $F_{1024}(B, C)$ denote the underlying function (single block manipulation function) of SHA-512. This function takes a 1024-bit block $B$, 512-bit initialization vector $C$ and produces 512 pseudo-random bits (eight 64-bit words).

Yes, $G_{1024}$ may be slower than $F_{1024}$, but is $G_{1024}$ weaker than $F_{1024}$ from the cryptographic point of view? If yes, in what aspects?

EDIT

I think that xoring the 256-bit $x_k$ with the 512-bit $B_i$ was a mistake, but I can also define the following function (that operates on a 1024-bit block $B$ given a 512-bit initialization vector $C$ and outputs 512 pseudo-random bits):

$$H_{1024}(B, C) = (x_1 \oplus x_3) \mathbin\Vert (x_2 \oplus x_4),$$

where $$\begin{array}{l}
{x_1} = F_{512}({B_1}, {C_1}),\\
{x_2} = F_{512}({B_2}, {C_2}),\\
{x_3} = F_{512}((x_1 \mathbin\Vert x_2) \oplus {B_1}, {C_1}),\\
{x_4} = F_{512}((x_1 \mathbin\Vert x_2) \oplus {B_2}, {C_2}),
\end{array}$$

$B_i$ denotes the first/second half of the 1024-bit block and $C_i$ denotes the first/second half of the 512-bit initialization vector.

Similarly, $H_{1024}$ may be slower than $F_{1024}$, but is $H_{1024}$ weaker than $F_{1024}$ from the cryptographic point of view? If yes, in what aspects?


texts: ElGamal with elliptic curves for security

texts:
I only know that ElGamal belongs to CPA based on DDH or CDH hard problem.
But, if i want to proof the CPA security for ECC-ElGamal, then, what hard problem should i based?DLP?
ECC-ElGamal algorithm: ElGamal with elliptic curves
It would be better if there is a source of relevant literature!!! Thank you very much!!


texts: How to name a signature algorithm that has no hashed component

texts:
I have an API-based service that digitally signs messages with RSA or ECDSA (system decides during runtime). The input is base64 encoded SHA-256 hash and the output is:

signature of this hash
signature algorithm, something like: "SHA256WithRSAEncryption" - to indicate if RSA or ECDSA was used by the system.

I now want to add functionality to also allow authentication (using a different certificate pair). For authentication, I don't want users to hash anything, I want the clients to generate random bytes with length (256/8)=32 and pass me the Base64 encoded version of this.

Now I have a problem how to correctly name the signature algorithm since the actual input is not a hash but random bytes. I was thinking like "Raw256WithRSAEncryption" to indicate that it wasn't a hash. But then I started to think if there was some hash algorithm that would actually return the thing itself, something like "Nohash256WithRSAEncryption".


texts: Calculating $\mathbb F_{p^2}$-rational points of an elliptic curve defined over $\mathbb F_p$

texts: How can I calculate points on an elliptic curve defined over $\mathbb F_p$, for example $y^2 \equiv x^3 + 1 \pmod p$, with coordinates in $\mathbb F_{p^2}$? (points might have complex number format in $\mathbb F_{p^2}$)


texts: Which cryptography technique does not increase the size of the plain data?

texts:
I want to encrypt some data(text/voice/video) but it is essential that the size of the cipher data remains the same as the plain data.

Which techniques can I use, and how secure are these techniques as compared to the ones which increase the size of the data?


texts: Tips on conceiving safe software messaging platform

texts:
I have a personal project in mind in which I plan to use cryptography in order to let the users be confident in the fact that, even if all data get's stolen, it would be virtually impossible to crack in the next few decades.

I would like some advice on the way I planned it until now:

All data resides in two key/value stores:

Store 1 - contains messages:

key   : msg_id (numerical)
value : AES encrypted message with random key K1.

Store 2 - links users to messages:

key   : hash H1 of (user identification + password + X)
value : AES encrypted data containing the msg_id and key K1, encrypted with key K2 (identification + password + salt/padding)

( X increments from 1 to N, per message linked to user. I use this to create more noise, should there be an attack, and to differentiate the hash H1 with key K2).

Without any regard to the way it should work (which is quite specific): is the data contained in the two stores safe even if an attacker knows their architecture and has access to the application's source code ? They may know some user id's, but not their password.

BTW: I'm quite new to cryptography. I'm reading through the basic materials (applied cryptography by Bruce Schneier, for one), so please be indulgent.


texts: DSA signatures with related k and unknown payloads

texts:
Suppose that we are given DSA parameters $p$, $q$, $g$, a public key $y = g^x$, and two signatures $(r_1,s_1)$ and $(r_2,s_2)$. We are told that $(r_1,s_1)$ and $(r_2,s_2)$ were produced by related nonces $k_1 = k$ and $k_2 = k+1$, but we do not know the value of $k$, and we do not know the messages.

(In practical terms: the PRNG is broken, but it's somehow well-seeded, and we can't submit any messages for signing. We cannot guess the contents of the messages, e.g. they're encrypted with a secret key.)

So we know
$$ \begin{array}{lll}
  r_1 = (g^k \bmod p) \hphantom{(g\cdot{})} \mod q &&
  s_1 = k^{-1} (h_1 + x \, r_1) \hphantom{{}-s_2} \mod q \\
  r_2 = ((g \cdot g^k) \bmod p) \mod q &&
  s_2 = k^{-1} (h_2 + x \, r_2 - s_2) \mod q \\
\end{array} $$
but we don't know the $h_i$. Can we find the private key?

Does it help to have more (but $\ll q$) known signatures made with $k+2, k+3, \ldots$ (but with unknown messages)?

(Inspired by Attack on DSA with signatures made with k, k+1, k+2)


texts: Explanation of the Fiat-Shamir heuristic

texts:
The Wikipedia page on the topic (http://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic) is completely useless as it only explains what it is and not how it works. I looked at the original paper by Fiat and Shamir, but it only contains a single construction. In other words, the so called heuristic must be an idea extracted from that specific construction.

Could anyone provide a more detailed explanation of how it works and also why the interactive proof system must be public-coin?


texts: What is the difference between forward secrecy and key freshness?

texts: Is all random private key that generating a unique session key is both forward secrecy and key freshness?


texts:
One question I had to answer in my crypto exam today was:

  Do we need symmetric cryptosystems?

As it stands, that's probably a debatable question, so I'd like to reformulate this as:

  Are there any situations where symmetric cryptosystems could not be replaced by asymmetric cryptosystems without serious downsides?

I'm not thinking of performance-related issues here; rather, I'm looking for things that would be impossible to achieve in an asymmetric-only model, or at least that would require prohibitively complex or costly implementations.

I would be interested to hear of any answer, since my teacher seemed to suggest that I was missing something, but he wouldn't say what (this was an oral examination).

Here's my personal thinking and answer:

I'd tend to say that symmetric crypto is not absolutely necessary, since:

For two-party communication, using two asymmetric key pairs should be enough to make do without symmetric crypto.
Generalizing to broadcasting or more-than-two-party communication, the sender would need to have keys for all recipients, but that should be sufficient.
Signatures should be able to emulate MACs (with the requirement that every group member who would have shared the MAC key now needs to have every group member's public key)
For encrypting data for personal use (single party), asymmetric encryption should be fine.

The only situation where I can think of difficulties is the distribution of public keys in the absence of a trusted party: in the contrived setting where Alice can securely send data to Bob, but Bob can't securely reply, Alice could transmit a symmetric key to use for subsequent exchanges, while in a fully asymmetric context Bob wouldn't be able to reliably send his public key to Alice. But this sounds like a somewhat contrived example, and I have no doubts that their are good ways of circumventing this (for example, Alice could generate a key pair for Bob, and send it to him).

Other weaknesses that I could think of were encryption & decryption speeds, and resistance to an hypothetical quantum computer, since current symmetric systems just need a doubling of the key length to maintain security, while asymmetric systems based on factoring would be brought to their knees. But then again we have lattice-based cryptography, so that's not a definitive reason why symmetric systems are needed.


texts: Message mapping to elliptic curve in BLS signature

texts:
In the BLS signature the subgroup $G$ of elliptic curve constructed with point $P$ with prime order $q$ by $G=\langle P\rangle $. The $h(x)$ is a hash function. The point $S$  is map (image) of $h(m)$ on elliptic curve. The signature is multiplying the private key in the point $S$.
Is the point $S$, also in $G$ and a multiple of point $P$ such as $kP$?


texts:
There is already a great survey on how to do range checks in a zero-knowledge setting. A range check allows to constrain a variable to be in a certain range. Comparisons seem to be similar, but they are actually very different in that they're allowed to be false.

E.g. if we write a range checks like this:

0 <= n < c

we can be sure that validation will never succeed if n is not in the given range. However if we have something like

if 0 <= n < c then x else y

then validation is supposed to succeed regardless of whether n is in the given range or not (provided the prover did its work honestly).

A similar issue arises in other situations such as n /= 0. It is trivial to require n not to equal 0:

n * inv n = 1

(because only 0 doesn't have an inverse) however in order to compile

if n /= 0 then x else y

we need to make use of non-determinism and introduce an auxiliary variable.

So my question is: how to compile 0 <= n < c when it's not a constraint, but rather a regular expression that I can use as a condition in an if statement?


texts: How does hash function in Elgamal signature scheme prevent existential forgery attack?

texts: I have heard that hashing the message M prevents an existential forgery attack. I was wondering how.


texts: AES MixColumns Predefined Lookup 2D Tables and Rcon Predefined Lookup 2D Table

texts:
I need to have the  a copy of predefined 2D table lookup for AES MixColumns when state is multiplied by 2 and 3, 9,11,13,14 and also the Rcon predefine table. I search it everywhere but I couldn't find it. I don't want how to generate it. I just want the tables. Can someone provide me with a link or even a title of a paper containing it. Thank you so much. I really need to have it.

I just want the actual 2d table: the mul2, mul3, mul9, mul11, mul13, mul14 and the rcon table. I want the 16 by 16  table version of mul2, mul3, mul9, mul11, mul13, mul14 and rcon table, not the array format of it. Thanks.


texts:
On many Linux/GNU distributions CCrypt (ccrypt) by Peter Selinger is available as a command line utility to encrypt files. How does the protocol work and is it secure?

Note: this should not be confused with the  CCCrypt API by Apple.


texts: Why the contrapositive proves a given hash is collision resistant?

texts:
So I am working on a problem as follows, it's a pretty basic standard question that I think I figured out, but I am confused as to why it works out the way it does.

Essentially, we are given a hash function $H$ that is collision resistant and maps to a fixed output length.

We want to create a new hash $H'$ such that

$H'(n) = H(n)||x$

Where we say, $x$ is just a random string of a given arbitrary length $m$.

Now what I think is the right thing to do is to use the contrapositive to say, if $H'$ is not collision resistant, than we can build an adversary to work in time ε. Thus we can alter our adversary easily by just cutting off the last m bites to get an adversary to solve for $H$

My question is that why can't we just use a direct proof to solve this? Must we use a contrapositive? I believe that it has to do with proving something is secure is a lot harder than proving it isn't, but I'm unsure.


texts: How can one build $2^{c/2}$ attack on sponge hash?

texts:
Let $H$ be a sponge hash with rate $r$ and capacity $c$, built from a permutation $\pi: \{0, 1\}^n \rightarrow \{0, 1\}^n$, where $n = r + c$.

Assuming $r \ge 2c$, how can I find a collision with probability at least $0.5$ in time $O(2^{c/2})$.
The colliding messages can be $2r$ bits each.

I'm pretty sure I have to use birthday paradox, but I still don't know how to apply it.


texts: How to construct encrypted functions (with either public or private data)?

texts:
Homomorphic encryption is often touted for its ability to

Compute on encrypted data with public functions
Compute an encrypted function on public (or private) data

I feel I have a good grasp of #1 as most of the papers I've come across on homomorphic encryption (both partially and fully) seem to deal with this type of problem, but #2 I haven't been able to wrap my head around.

So, to whittle this down to the simplest case, given a fully homomorphic encryption scheme, let the public input be $a,b,c,d$ (each is a single bit for simplicity). How would I construct a function to compute $(a\vee b) \wedge (c\vee\neg d)$ such that whoever I give it to will not know what the actual function is (granted this is such a simple example they could easily create a brute-force lookup table)?

I'm not looking for an exact function, but how this would be done in general. How does it change if I make it that $a,b,c,d$ are private (to the function creator)? Is the process similar for partially homomorphic (where only the $\wedge$ or $\vee$ operations are possible)?


texts: Tests on /dev/urandom entropy can be considered useful or not?

texts:
i want to test the entropy of my seed generator: in my case is /dev/urandom.
I've read that this operation is non useful because it is the result of CSPRNG (normally not accessible).

But what i obtain from urandom is the seed for my RBG algorithm and than it is the real seed for me.

Do you think the test can be useful or not? Do you have any suggestion on how it should be performed?


texts: How does Bluetooth pairing (SSP with numeric comparison) work?

texts:
I have a question concerning the pairing of two Bluetooth devices using Simple Secure Pairing with numeric comparison.
The NIST document I am looking at states on page 14:

  Numeric Comparison was designed for the situation where both Bluetooth devices are capable of displaying a six-digit number and allowing a user to enter a “yes” or “no” response. During pairing, a user is shown a six-digit number on each display and provides a “yes” response on each device if the
  numbers match. Otherwise, the user responds “no” and pairing fails. A key difference between this operation and the use of PINs in legacy pairing is that the displayed number is not used as input for link key generation. Therefore, an eavesdropper who is able to view (or otherwise capture) the
  displayed value could not use it to determine the resulting link or encryption key.

And on page 15, there is a graphic that illustrates the “Link Key Establishment for Simple Secure Pairing”:

Now…

To check on things, I've used a Bluetooth packet capture to sniff the traffic on my phone to see the pairing details. I expected the Bluetooth packet capture to log the details about the $PK$ that was sent and received by the controller. I do see the User Confirmation Request containing the number for the numeric comparison, but I am not able to detect any infos about a $PK$ exchange – as if such an exchange never happened. Therefore, it would be nice to get a confirmation if Simple Secure Pairing indeed uses a $PK$ – and at what point it actually exchanges it.

TL;DR:

I don't understand how the “Link Key Establishment for Simple Secure Pairing” prevents a MITM attack. It seems as if attackers could send a false $PK_2$ nevertheless… or did I miss something?


texts: What is difference between meet in the middle attack and man in the middle attack?

texts:
From my understanding man-in-the middle attack works as follow:
Alice   and Bob agreed  to  use Diffie-Hellman  using   $a$ and    $q$.   Alice sends $Y_A$.   Before  it  reaches Bob,
Charlie intercepts  it  and sends   $Y_{C1}$ instead.    Bob    believes    to  have    agreed  on  a   key $K_B$ with   Alice,  but
the key is  actually    only    shared  by  Bob and Charlie since   $K_B = a^{X_{C1}X_B} \mod q$.

Bob sends   back    $Y_B$, and   it  is  again   intercepted by  Charlie.    Charlie sends   $Y_{C2}$ instead,   and Alice   sees    that    Bob has replied.    Alice   believes    to  have    agreed  on  a   key $K_A$ with   bob,    but they    key is  actually    only    shared  by  Alice   and Charlie since   $K_A = a^{X_{C1}X_A} \mod q$.

So how does meet-in-the middle attack compare to this example?


texts: Does Curve25519 only provide 112 bit security?

texts:
In a recent mail on the IETF CFRG mailing list it was claimed that:

  The (currently missing) security considerations (or somewhere) should describe why Curve25519 is ok when used in contexts where we'd
  otherwise ask for 128 bit strength, (basically because it's close
  enough), and also why the 224 bit level is considered a good choice.
  There was a lot of debate on the list about that, and I've seen the
  issue come up elsewhere so this text will avoid re-litigating that and
  should be worthwhile even if it takes a little time to agree.

I read this such that Curve25519 only provides security on the 224-bit level i.e. 112 bit security.
But when I look up Curve25519 on Wikipedia I get to see in the very first line that

  Curve25519 is an elliptic curve offering 128 bits of security

Wikipedia itself references to Bernsteins original paper "Curve25519: new Diffie-Hellman speed records" which indeed confirms Wikipedia as follows:

  Every known attack is more expensive than performing a brute-force
  search on a typical 128-bit secret key cipher.

So my question is:
Does Curve25519 indeed provide significantly less security than 128-bit?


texts: Chosen Ciphertext Attack on the Public Key in PGP

texts:
In Secrets & Lies (2000), Schneier describes a chosen ciphertext attack on the public key under PGP:

  "Since RSA and ElGamal are malleable, known changes can be made to the symmetric key that is encrypted. This modified (encrypted) key can then be sent along with the original message. This opens up the possibility of related-key attacks on the symmetric algorithms. OR, a weak ciphertext can be found whose decryption under the symmetric key algorithm reveals information about the modified key, which then leads directly to information about the original key." [P. 327-328. Schneier, Bruce. Secrets & Lies. 2000]

Could you explain (a) how this attack works and (b) whether it's still feasible in 2016?


texts: handling junk bytes in chi squared character freq analysis

texts:
I'm doing the Matasano crypto challenges. After implementing a naive character frequency scoring (that worked), i was looking for something mathematically more precise and found this thread: Developing algorithm for detecting plain text via frequency analysis

While the Chi Squared analysis does work for me, I encountered a problem.
My current code just sets the score to infinity if I encounter a nonprintable character.
I want to avoid doing that, since a possible plaintext could contain a few ascii non printable characters. (for example it is actually unicode and contains a greek word)
But when I ignore every non printable character for scoring, as I already do with chars like ".,!\n\t", I run into the problem that strings with a few high scoring characters and lots of junk get scored better than actual english plaintext.

My current code is as follows: (frequency is a dict that associates ord(character) with its frequency for a-z and space)

import frequency
import copy
from math import inf
from string import printable

def score_string(inp):
exp_dist = copy.deepcopy(frequency.frequency)
length = len(inp)
for key in exp_dist:
    exp_dist[key] *= length
dist = dict.fromkeys(exp_dist.keys(), 0)
for char in inp.lower():
    if chr(char) not in printable:  # This is the part i like to avoid
        return inf
    if char in dist:
        dist[char] += 1
score = 0
for key in exp_dist:
    score += (dist[key]-exp_dist[key])**2/exp_dist[key]
return score

If I understand what is going on correctly, my issue is that for shorter strings (the example i worked with was 34 characters) the negative impact of even a single low scoring printable charater outweights the negative impact of a character that is ignored by the scoring by alot.

I'm looking for an elegant way of guaranteeing that nonprintables affect the score worse than any printable character but don't dismiss them completely.


texts: I'm looking for course material on the subject of proofs, reductions, and games, as used to prove cryptographic schemes secure. What are the methodologies? What are the preferred ones? In what cases is it best to use a method rather than another?


texts:
The XOR operator seems to be a frequently used building block inside many cryptographic primitives.  As far as I can see, its most desirable properties seem be that for the XOR of two bits $a\oplus b=c$:

The information is preserved.  Either $a$ or $b$ can be recovered from $c$ and the other bit.
The information is hidden.  An adversary can not learn anything about $a$ or $b$ from $c$ alone.

Neither AND nor OR has these properties but XNOR does.  It seems like any cryptographic application using XOR could be constructed equivalently with XNOR, without incurring any loss in security.  One possible reason to prefer XOR might be that XOR is equivalent to addition modulo 2, whereas XNOR would be addition plus 1 modulo 2, but this seems to be entirely mathematical, and I'm not sure if it actually results in any additional hardware complexity in practice.

Is the choice of XOR then an arbitrary one, made for historical reasons, or is there any tangible underlying motivation for using it over XNOR?


texts: Linear approximattion of $(x+y) \bmod 2^n$ in FSM of SNOW 2.0 where $x,y$ in $F_{2}^n$

texts:
I would like to understand the linear approximation of $(x+y) \bmod 2^n$ by linear masking method in the paper refereed ""Improved Linear Distinguis'hers for SNOW 2.0" by Kaisa Nyberg and Johan Wall´en."
In  Page number 14 to 15, one theory has been given. I am unable to understand the $A_r$ matrix computation. Specially what is $v$ in this matrix. Advance thanks for anyone's kind explanation.


texts: Are "non-mathematical" encryption algorithms comparably secure against brute force key recovery?

texts:
I recently learned about a desktop encryption application called ALKEMI, which does not use mathematical encryption according to the website, which I understand to be a misnomer, at best:

The encryption Alkemi uses was written by me starting in 2005. It is
NOT MATHEMATICAL in nature.

From what I found, it appears to be similar to, related to, or directly using libraries from Yull Encryption. The algorithm is described as using combinations of different routines:

The data submitted to the encryption class goes through a series of
routines. There are 64 unique routines (procedures). The order of the
routines is determined by a hash of the key. Furthermore, often
certain subsets of the data is run through the routines. Routines
(procedures) can and of course are reused. Typically, routines are
invoked several hundred thousand to millions of times. And some
routines call others which call others. The number of combinations is
meaninglessly huge.

The author goes on to address how difficult it would be to recover the plaintext without knowing the key:

In order to force decrypt Alkemized data, you would have to try all the decryption routines (64 of them), in the precise reverse order.
But as you can see, the amount of routine combinations is gigantic.
There isn't enough time left in Earth's existence to try them all.
..., if you have the encrypted text and the program or even the source
code but not the key, your choices are pretty limited, in my view. You
have two choices: Try all the key combinations. There are a range of
217 letters and symbols, including foreign languages, and a possible
32765 of them in various combinations.

The screenshot of Wolfram Alpha shows this totalling ~10^76554.
First off, these projects raise red flags in my head for any serious use, as I fully believe in the mantra of "don't roll your own crypto". The author admits that it is a home grown algorithm, but still puts it out there recommend for public use.
More importantly to the question, I am struggling to wrap my head around how "safety in numbers" is really sufficient against a brute force key attack. My understanding is that part of the reason it is  difficult to brute force a conventional symmetric encryption key (e.g. for AES) from ciphertext is that the encryption algorithm is computationally expensive, making it difficult to feasibly brute force a reasonably strong key. I didn't find a description of the 64 functions that ALKEMI/Yule uses, so I do not know how they compare in terms of compute cost, although the author says it took 27 seconds to encrypt 12000 characters.
I believe the author also claims it is secure because you can create very long keys in any charset, but regardless it is ultimately limited to the 64 bytes it is hashed to with SHA512, which I guess I can't complain too much about. But I believe this means the key space should be 2^64 rather than 10^76554.
My question is, do these (and any other?) "non-mathematical" [sic] encryption algorithms have theoretical or actual resilience to brute force of the key comparable to a modern standard like AES?


texts: What can be learned from an encrypted text?

texts:
I assume nowadays crypto algorithms are well-built, so one can't make a difference between a ciphertext and random bit stream. This way the method used for encryption can't be figured out either.

I am curious, if there is perhaps something else that can be derived from a ciphertext, some meta data for example.


texts: Combining share decryption on Paillier threshold scheme

texts:
I am trying to implement the Paillier threshold scheme described by Fouque, et al, but I am having an issue when combining share decryptions.

The scheme calculates the plaintext $M$ with the formula:

$M = L\left(\prod\limits_{j \in S} c_{j}^{2\mu_{0,j}^{S}} \mod n^{2}\right) \times \frac{1}{4\mu^{2}\theta} \mod n$

Where $\mu_{0,j}^{S} = \Delta \times \prod_{j' \in S \setminus \{j\}} \frac{j'}{j' - j} \in \mathbb{Z}$

For a list of shares $S$, where on code it is represented by a list of objects $(id: i, value: c_i)$ where $i$ is the share ID and $c_i$ the value, I am trying calculate $\mu_{0,j}^{S}$ with the following pseudocode Python code:

def combine(shares: Set[Decryption], key, params) -> int:
    n = key.n
    n_squared = n * n

    threshold, Δ = params.threshold, params.Δ
    c = 1

    shares = shares[:threshold]
    for i in shares:
        µ = Δ

        for j in shares:
            print(i.id, j.id)
            if i is j:
                continue

            µ *= j.id // (j.id - i.id)
        c *= pow(i.value, 2 * µ, n_squared)

    L = 4 * Δ * Δ
    c //= L * key.θ
    return ((c - 1) // n * modular_inverse(L, n)) % n

The problem is when I get to the second iteration, where i.id is 2, and the inner for starts with j.id as 1. Thus, $\mu$ is negative when I calculate $\frac{j'}{j' - j}$ because $j'$ (j.id) is smaller than $j$ (i.id), then $j' - j$ becomes negative.

The effect is that $\mu$ is negative (every other iteration yields positive factors to multiply), so $c_{j}^{2\mu_{0,j}^{S}}$ elevates $c_j$ to a negative exponent.

Did I miss something from the paper, or is it working as expected and I have to handle this negative exponent some other way?


texts: Is this a PRP? How can I create a distinguisher to show it isn't?

texts:
Consider the keyed permutation $F_k : \{0,1\}^2 \to  \{0,1\}^2$ with two-bit keys defined as $F_k(x) = k\oplus x$.

Is this F a PRP? How can I create a distinguisher D and calculate the difference when using this D?

I know that $F_k(x_1) \oplus x_1$ will give me the key and that all $x$ and $F_k(x)$ in the same permutation use the same key. Can I use this to create a distinguisher?


texts: Is there an input length range for SHAKE128 hash function?

texts:
For SHAKE128 hash function in SHA3VS document, I find this paragraph:

  Therefore, for testing SHAKE128, (168*2)+1) = 337 unpredictable messages will be
  generated with lengths from 0 to 337 336 bytes (omitting 0 if zero length is not
  supported) and SHAKE256, (136*2)+1) = 273 unpredictable messages will be
  generated with lengths from 0 to 273 272 bytes (omitting 0 if zero length is not
  supported).

I know the hash digest length is flexible:
Hash(input, length N) = N-byte digest

Question:

Is there any requirement for input length (minimum or maximum no. of bytes) to achieve 128 security level?


texts: Is it possible to 'fake' time for TOTP? (Time-based One-time Password)

texts:
TOTP (Time-based One-Time Password) Algorithm is used in Two factor authentication. I understand the algorithm and that current time is used as a variable to generate a token. Wiki page for reference: http://en.wikipedia.org/wiki/Time-based_One-time_Password_Algorithm

My question is, can current time be faked?

Suppose you have tokens T(0),...,T(n) where T(0) was generated at time = 0 and T(n) was generated at time = n.

Suppose I have the initial seed value for the algorithm, and I know current time is k, is it possible to generate T(k) without having generated T(0),...,T(k-1)?

In other words, can time elapsed be 'faked'? Or is T(k) based on every token in the set of tokens, T(0),...,T(k-1). If it is based on every previous token, does generating T(k) require at least (block of time) * (k-1) time to generate or can the process of elapsed time be fed to the algorithm to generate T(k) in less time?

Thanks.


texts: Security issues with computing parallel hashes?

texts:
One issue with most hash algorithms like SHA-256 is that it is inherently serial.  You can't effectively use SIMD to parallelize a single SHA-256 calculation.

However, you can calculate multiple SHA-256 hashes in parallel efficiently, because you can keep each algorithm in a lane of the SIMD registers.

Take SSE as an example: each register has four 32-bit lanes.  Computing SHA-256 four times in parallel makes sense.  We can define a new hash algorithm for computing the hash of a single file as slicing the input into four pieces, computing the hash of each of the four pieces (in parallel), then produce the final result by hashing the final four sub-hashes together.  Obviously, this would be a new hash function, not matching a normal SHA-256.

Are there security problems with such a design that wouldn't exist with a normal hash algorithm?


texts: How much plainext could be known without reducting security of RSA?

texts:
It is known, for example, that exposing 50% of the most significant bits of RSA private exponent does not provide security risk (when a small public exponent is used). So how to qualify security degradation of partial exposure of plaintext in RSA encryption? Can we say, for example, that exposing 50% of plaintext does not reduce security? And, is there a limit when it starts to actually reduce it?
I think that, probably, the answer should be related to 1) how many remaining bits are left to brute force (if 99% of plaintext is exposed it will be easy to just brute force the remaining 1%, so if non-exposed bits size is above 128 then security is 'not reduced'), and maybe 2) exposure for Coppersmith’s methods (if non-exposed bits size is more than $N^{1/e}$ than security is not degraded), but this should not even be relevant for $e=65537$ which is common.
Thus, can we say that the security of partial plaintext exposure of properly done RSA encryption is bound to as much is left for brute force?


texts: Using the hash of the user's password for encrypting/decrypting an E2E encryption/decryption key: is this good practice?

texts:
I am developing an app in which the user data is encrypted in the client before the data is transmitted (over SSL) and decrypted after it is received. If the database is ever compromised, without the user's decryption keys the attacker knows nothing.
Of course, when the app is hosted on a web server, an attacker could still inject malicious scripts, but that's always a risk. The idea is that the user data is encrypted by default. As long as no malicious code was added to the client code, the server should not be able to obtain the user data.
The title summarises how I intended to do this, but actually it's a bit more convoluted:

On account registration, a secure random string is generated as (AES) encryption key (could also be private/public key generation here I guess). Let's call this key K1.

All data will be encrypted/decrypted (e.g. using AES) with this key.

The plain text password is hashed to create another key. Let's call this K2 = hash(plain password) (for example using SHA256)

K2 is used to encrypt K1 for secure storage of the key in the remote database in the user profile.
If the user changes his password, all that needs to be done is re-encrypting K1 with K2 = hash(new password), so not all the data has to be decrypted and re-encrypted.
K2 is stored in localStorage as long as the user is authenticated: this is used to decrypt K1 at bootstrap.

K2 is hashed again to generate the password that is sent to the API: P = hash(K2) (also using SHA256 for example)

This is to prevent that the decryption key K2 (and therefore, K1) can be deduced from the password that the API/database receives.

In the API, the password P that is received is hashed again before it is compared/stored in the database (this time with a stronger function such as bcrypt).

My question is: does this mechanism make sense or are there any gaping security holes that I missed?
The only downsides that I see are inherent to end-to-end encryption in apps:

Forgotten password = all data is lost (cannot be decrypted). This is why the user is recommended to write down the encryption key K1 after creating the account: then the data can always be recovered.
Searching, indexing, manipulating, analysing the data is limited because everything has to be done client-side.


texts: I couldn't understand the avalanche effect in DES. Could someone explain how avalanche effect happens in DES


texts: Can any hash function based on the sponge construction work as extendable output function?

texts:
Keccak provides a sort of very useful XOFs.

Can other sponge construction hash function like  Spongent work as XOF?
Is there any lightweight XOF for hardware or software implementation?


texts: Is CBC mode encryption vulnerable to a reordering attack?

texts:
I know that, if CBC-MAC is used in such a way that the tag is the concatenation of all the blocks' outputs (and not just the last one), it's insecure under CPA for the simplest case of 2 blocks CBC-MAC where:

the message is $m=m_1\mathbin\|m_2$, where $|m_1|=|m_2|$ equals the block size of the cipher, and
the tag is $t=t_1\mathbin\|t_2$, where $t_1 = F_k(m_1)$ and $t_2=F_k(t_1\oplus m_2)$.

In this case, the attacker can change the plaintext and create a valid tag of reverse order. The new message will be $m'=m'_1\mathbin\|m'_2$, where

$m'_1=m_2\oplus t_1$,
$m'_2=m_1\oplus t_2$, and
$t'=t_2\mathbin\|t_1$.

Is a similar attack also possible for the CBC encryption mode (where we have a random $IV$ xored to $m_1$)?

EDIT: My question actually is whether a CPA attacker (who knows $c=IV\mathbin\|c_1\mathbin\|c_2$ and $m=m_1\mathbin\|m_2$) can modify the ciphertext that is sent to the destination and be able to predict what the plaintext resulting from it will be?


texts: Is it feasible to build a stream cipher from a cryptographic hash function?

texts:
A few years ago I devised a symmetric-key system that worked like so:

H()   = some hashing function
h     = the number of bits in the result of H()
key   = bits to be used as a key
^     = the XOR operation
+     = concatenation
len() = the length function (in bits)

max = ceiling(len(cipertext) / h)
pad = pad_0 + ... + pad_max
pad_0 = H(key) ^ H(plaintext)
pad_n = H(pad_(n-1))
cipherpart_n = plaintext_n ^ pad_n
ciphertext = H(plaintext) + cipherpart_0  + ... cipherpart_max

Basically, it builds up a "pad" based on the hash of the message and hash of the key and XORs the message against it.

I am not actually an expert, so I was wondering why an approach like this isn't very common.


texts: How are side-channel attacks executed? What does an attacker need to execute a side channel attack?

texts:
I've been reading about side-channel attacks on Wikipedia, and it seems that some of these can only be executed on the victim's computer. (I am specifically asking about the side-channel attacks listed on the Wikipedia page and any more that are theoretically possible)
What would an attacker need to execute each side channel attack?
How are side-channel attacks executed?


texts: What is the proper way to implement AES CTR with 128 bit nonce and 64 bit counter?

texts:
While encrypting AES in CTR mode, the input to the AES encryption function is the either a combination of IV + $m$ bit counter or is either $0$ IV bits with an $m$ bit counter. It is however rare to see the full usage of the input block ($128$ bits) as just a counter.
Since CTR mode essentially converts a block cipher to a stream cipher, the implementer must be careful that the XOR of ciphertexts should not reveal XOR of plaintexts. For this requirement, the $(nonce, key)$ pair should be unique for each invocation.
I'm particularly interested in file encryption, or a large (in size) session of encrypted communication over a network , (say file download > 64 GB).
My encryption scheme:
Use a 128 bit IV to populate the initial block. For every requirement of a 16 byte keystream increment the counter and add it with the initial block populated with the IV. (EDITED)
This will be the protocol: $C_{i} = AES_{k}(IV  + i) \oplus P_{i}$  where $i$ is 64 bit counter, $IV$ is $128$ bit nonce and $+$ is arithmetic addition modulo $2^{128} -1$.

Is this secure (confidential sense)?
Will there be collisions in the input
block to the AES function since we have already populated the initial
block, with random IV (Can modular addition of counter cause collision) ?
Is this a standard way of doing AES CTR ?
What is the proper way to check for overflow? Should I check whether initial block (treated as a big endian integer) equals to $2^{128} -1$ or only whether $i$ equals $2^{64} -1$ and then raise an exception?


texts: Difference between Multi-linear and Multi-Secret Sharing Schemes

texts:
I've been reading papers on secret sharing schemes and came to two different terms, namely, multi-linear secret sharing schemes and multi-secret sharing schemes. As an example, the term multi-linear is used by Beimel et al. in Multi-linear secret-sharing schemes publication.  On the other hand, the term multi-secret is used by Yang et al. and Chien et al. in A $(t, n)$ multi-secret sharing scheme and A Practical $(t,n)$ Multi-Secret Sharing Scheme respectively. Are these two terms the same?
I would appreciate someone helping me with this.


texts: Asymmetric password encryption - Viable? Which algorithm?

texts:
We have an application that requires cleartext passwords for user authentication because of the authentication mechanism in use (RADIUS/CHAP), which unfortunately we cannot change. Since we don't want to store cleartext passwords, an idea is to use asymmetric encryption to secure them as good as possible.
After creating/chaning a password, it will be encrypted with the public key and replicated through more or less unsecured channels to the authentication systems. When a user tries to authenticate, the encrypted password will be decrypted with the private key (which has to be available on the authentication servers, obviously).

So we would have a database with lots of encrypted passwords, but all encrypted with the same key. After some research I see that this not the way asymmetric encryption is commonly used. Usually the payload is encrypted with a block cipher and the symmetric key is encrypted with an asymmetric key. But since passwords are quite short I wonder if this additional encryption layer can safely be avoided or if this would be simplification would be a serious risk.

Related to this: What algorithm would you recommend? I kind of narrowed it down to RSA and Elgamal, mostly because these two seem to be most widely used and are available through well-known libraries (OpenSSL, gcrypt). RSA seems to require longer keys to provide the same security, so Elgamal seem to be the better option there's no other argument against it.

Comments?


texts: Is a changing public truecrypt container secure?

texts:
I have a Truecrypt container which I want to synchronise between computers (i.e. different people, that I want to share the data with).

If I used Dropbox for synchronisation and someone downloaded all the different versions of a publicly accessible Truecrypt container over time, whenever it gets changed, is it then easier for them to find the password than if they just had one version?


texts: Constructing set membership proof for private set

texts:
Is it possible to construct a set membership proof to show $\delta \in \Psi$ where $\delta$ is publicly known and $\Psi$ should stay only known to the prover?

It seems rather impossible but I would like some confirmation.


texts: Is a message digest useful with symmetric encryption to check for integrity?

texts:
I have some confusion that concerns the message digest.

I know that the message digest is the real message hashed with function and we use it to verify the integrity of the message.

I understand the usefulness of using this with asymmetric encryption but I can't find the utility of this with symmetric encryption.

I will explain my self:

We have Alice and Bob. Alice wants to transmit a message m to bob with symmetric encryption. Suppose that the two of them know the encryption key in advance.

Alice encrypts m with the key, hashes the message as hash(m) and sends it to Bob as (encrypt(m), hash(m)).

Bob decrypts the message and then hashed to verify the integrity.

In this case I think that the hash(message) is not needed because:

Case 1: If someone doesn't have the key they cannot cipher a message and send it to Bob pretending to be Alice because Bob will know that the message wasn't encrypted using the key. (We didn't use the hash message in this case).

Case 2: If someone has the key, they intercept the message of Alice and modify it to m2 then they encrypt and hash the new message and send it as (encrypt(m2),hash(m2)). When bob tries to verify the integrity of the message, the process will succeed (in this case using the hash didn't help to check the integrity of the message).

So in both cases the hashed message is not (or cannot) be used to check the integrity of the message.

Is this correct? Because I have argued with my teacher and he said that hashing the message helps to check for integrity in both symmetric and asymmetric encryption.

Is there some cases that hashing the message is useful?


texts: Attack vector difference when not allowing repetitions in BIP-39

texts:
We are using a 12-word scheme BIP-39 mnenemonic key generating scheme that creates an entropy of 128-bit that is then used to generate a seed that in turn derives a private key for the user. It chooses randomly 12 words out of 2048.

There are $2048^{12} = 5.444518 \cdot 10^{39}$ combinations that form the entropy for the seed.

This scheme allows duplicate words. Some users are irritated by that and write emails to support and I wonder how much entropy would get lost by only allowing unique words.

That would be $\frac{2048!}{(2048-12)!} = 5.271538 \cdot 10^{39}$ variations.

In conclusion the latter solution has only $\frac{5.271538 \cdot 10^{39}}{5.444518 \cdot 10^{39}} \approx 96.8\% $ the number of possible seeds than the non-unique one.

Is that mathematicallly correct and is that a neglectible hit on security given the increase in user friendliness?


texts: Constant time multiplicative inverse within a word

texts:
I was playing with an algorithm which at one step, calculated $f(x) = x^{-1} \mod p$ for $0 < x < p = 2^{64}-59$ (note $p$ is a prime). I used Knuth's Vol 2 Algorithm X algorithm for calculating inverse modulo a prime, using the Extended GCD, but I was wondering if there was a way for making it run in constant time, within a word?

The trick I found online for producing constant time inverses used Montgomery Multiplication, and therefore wouldn't fit within a 64-bit word.

My objective is to write a 64-bit cipher which (is probably insecure, definitely slow, and) uses inversion for confusion and diffusion.

Edit: Specified $p = 2^{64}-59$, a prime.

Edit2: Specified the algorithm attributed to Knuth with link to page which has attribution.


texts:
I read about sercurity section of AES in wikipedia. It wrote "In November 2009, the first known-key distinguishing attack against a reduced 8-round version of AES-128 was released as a preprint... It works on the 8-round version of AES-128, with a time complexity of $2^{48}$, and a memory complexity of $2^{32}$".
I know that distinguisher can somehow weaken the cipher, but how does it directly attack the cipher? Can someone explain to me how known-key distinguishing attack work, or provide some resources to learn about known-key distinguishing attack? Thank you.


texts: What is $z_b$ in this introduction to Private Information Retrieval?

texts:
I was trying to read this introduction to private information retrieval. On page 12 of the document, a scheme for 1-DB private information retrieval is discussed. I was unable to understand one of the steps of this scheme, I will reproduce it below so you can look at it, and hopefully, someone can clarify what is meant by the step I don't understand.

An integer $n$ is defined ahead of time, the database $x$, is a $\sqrt{n} \times \sqrt{n}$ array of bits, whose elements can be indexed as $x_{nm}$.
We now describe the protocol for Alice to privately determine the quantity $x_{ij}$ for some specific pair $i,j$ as follows:

Alice generates two primes of equal length $p_1, p_2$ such that $m = p_1 p_2$ is a semiprime with length $n^{\delta}$  for some  choice of $\delta > 1$.

Alice generates $\sqrt{n}$ elements of the multiplicative group $Z_m^*$ called $r_1 ... r_\sqrt{n}$ with the property that ALL except $r_i$ (where $i$ is the same as the $i$ in $x_{ij}$) are quadratic residues modulo $m$, and $r_i$ is a quadratic non square modulo $p_1$ and $p_2$.

Alice sends $m, r_1 ... r_\sqrt{n}$ to the database.

The Database now computes a matrix $c_{ab}$ defined as follows:

$$ c_{ab} = z_b^2 \ \text{if } x_{ab} = 1 \\ c_{ab} = z_b \ \text{if } x_{ab} = 0 $$
Now I'm totally lost, what is $z_b$? Where did it come from? How is it defined?


texts:
I wanted to know if my understanding is correct!
I have been reading up on aes encryption and modes(specifically CTR and CBC) and it took me sometime to understand the concept of IV.
If the IV is generated randomly then:

In CBC mode typically IV is prepended or appended after the encryption,So the first block of the cipher text is decrypted using this first block of data recieved which is the IV and from there on the previous cipher block is the IV for the next block.

I am not sure about the practice in CTR mode but there is a counter(or nonce) that increments the IV for each block for decryption adn encryption.

If the IV is generated value then well both parties need to agree on how it is generated.
And using a constant IV is not really recommended to use a fixed IV for any mode.

I also want to know, what other standard practices are in use to communicate the IV in between two parties in different AES modes?


texts: Why does rsyncrypto require a public key during decryption?

texts:
I recently came across a project called rsyncrypto that sacrifices some security so that you can have rsync-friendly files. My understanding is that it works by generating a symmetric key for each file you're encrypting, and saving that symmetric key to a file. It then encrypts the file using that symmetric key, encrypts the symmetric key with a public key, and concatenates the encrypted symmetric key to the encrypted file. The purpose of this is so that each file can be encrypted with a different key, but even if you lose the symmetric key file, the data can be decrypted by using the private key (private key decrypts symmetric key in the file, symmetric key decrypts the file itself).

The project seems to require the use of the public key in addition to the symmetric key file for decryption, however, and I'm confused as to why this is. It seems like if you have the symmetric key in a file already (which you do, generated by the program), you could just decrypt the data and disregard the embedded copy of the same symmetric key. I know that this is a question better posed to the maintainer, but he seems to have disappeared years ago. Anyone familiar with the program (or even if you're not) that could explain to me why you might need the public key in addition to the symmetric key for decryption? The most likely explanation I can think of is that I'm missing something about how this program works, but all the reading I've done doesn't seem to have cleared anything up about this.

Disclaimer: Thusfar my google-fu has been strong and I have never needed to post a question on any forum before, so this is my first. Please be gentle. =)


texts: Why use symmetric encryption with Public Key?

texts:
A. From what I heard (and I am beginner at a security/cryptography), if you have a payload that is very large, asymmetric is a no-go.

B. Also, if you do have secret symmetric (e.g. AES) keys, you might not want to share them with others, if they have high importance to you.

I am trying to understand things and I cannot find good enough internet resources explaining this use case.

Here is the reasons I have thought of, for doing such an encryption:

asymmetric encryption is not available; e.g. due to large data size
symmetric keys are available but you do not want them to be shared with other parties
sender/encryptor needs to send data to the receiver securely (encrypted)

Please validate/criticise my ideas or add others.


texts: How do Edward curves scale better in computation time compared to Weierstrass curves?

texts:
I see people talk about Edward curves (when I discuss Ed25519) as better curves than Weierstrass for computations. Now I get that Edward curves have the nice addition formula, but if we have a specific Weierstrass curve, wouldn't addition also involve the same computation, since we have fixed equations for that, that we solve analytically once and then just compute them?
To put the question from a different perspective: Some people also mention "constant time scalar multiplication" with Edward curves. I didn't find any constant-time formula for multiplication, I just found one for addition and doubling of points (so doubling + addition is not constant, or is it constant with respect to something else?), which brings me back to the comparison with Weierstrass curves. Don't we have fixed formulas for that too (after calculating some derivatives analytically) that can be seen as constant-time?
I would appreciate explaining the computational features of Edward curves compared to their math. I couldn't find that information online.


texts: How were the AES key and block length subsets of Rijndael selected?

texts: My intuition tells me it's a trade off between speed and security, but how did the standardisation process select these three seemingly arbitrary key lengths (namely, AES-128, AES-192, AES-256).


texts: Is it safe to use the same key for different variants of the HMAC-SHA algorithm?

texts:
I need to apply HMAC-SHA hashes in my application. Depending on the context I'll use either HMAC-SHA512, HMAC-SHA256 or HMAC-SHA1.

Is it safe to use the same key for all of these algorithms, or do I need to use a different key for each hash type? I plan to make the key 128 bytes which I understand is long enough for all of them.


texts: On randomness related terminology clarification

texts:
It was suggested to provide a new question in the comments in
How to combine $n$ 'less random' bits to generate one 'more random' bit?.

Why there is no unbiased randomness (seeking theoretical underpinnings)?

How can a hash function extract randomness (seeking theoretical underpinnings)?

Is there intuition behind leftoverhash lemma and can it useful in correlated randomness (seeking theoretical underpinnings)?

Is there references for 1. and 2.?


texts: Besides key and ciphertext sizes what are other advantages of elliptic curve versions of various protocols?

texts:
There are elliptic curve variants of Diffie-Hellman, ElGamal, DSA and possibly other protocols/algorithms. I know that these elliptic curve variants have smaller key and ciphertext sizes which will make communications (or storage) more efficient.

  Are there other advantages to the elliptic curve variants of these standard protocols/algorithms?

Specifically I am interested in speed and power consumption, but other potential advantages like resistance to side-channel attacks are also of interest.


texts:
The private key is any random 256 bit (but smaller than prime p) number or must be prime or other condition?
For selected $x$ can be found $y$ - decompressing key:
#! /usr/bin/env python3
import binascii
import math
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
def decompress_pubkey(pk):
    x = int.from_bytes(pk[1:33], byteorder='big')
    y_sq = (pow(x, 3, p) + 7) % p
    y = pow(y_sq, (p + 1) // 4, p)
    if y % 2 != pk[0] % 2:
        y = p - y
    y = y.to_bytes(32, byteorder='big')
    return b'\x04' + pk[1:33] + y

print(binascii.hexlify(decompress_pubkey(binascii.unhexlify('0229b3e0919adc41a316aad4f41444d9bf3a9b639550f2aa735676ffff25ba3898'))).decode())
print(binascii.hexlify(decompress_pubkey(binascii.unhexlify('02f15446771c5c585dd25d8d62df5195b77799aa8eac2f2196c54b73ca05f72f27'))).decode())
print(binascii.hexlify(decompress_pubkey(binascii.unhexlify('0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798'))).decode())

Only last x,y pair fulfill (x3+7-y2) % p is zero. Two previous pairs are wrong?


texts: How to prove that the concatenation of two secure PRG is secure?

texts:
Given $G:\{0,1\}^s \rightarrow \{0, 1\}^n$ a secure PRG, how can one prove that $G'(k_1, k_2) = G(k_1) \cdot G(k_2)$ is secure ($\cdot$ means concatenation)?

In other words, I'd like to show that if there is a distinguisher for $G'$ then this implies that there exists a distinguisher for $G$.

For example, could this distinguisher be as follows?

$A(x) = \text{round}(\frac{1}{2^n} \sum_{y \in \{0,1\}^n} A(y \cdot x))$


texts: Is this problem still as hard as discrete logarithm (modified ElGamal)?

texts:
I am trying to find a vulnerability or proof for the following problem:

ElGamal part.

Given $g\in\mathbb Z_p$ where $g$ generates $\mathbb Z_p^\star$, select randomly $k\in\mathbb Z_p$ and calculate $h=g^k \mod p$. The public key is $(p, g, h)$ and private key is $k$.

To encrypt message $m\in\mathbb Z_p$, randomly select $r\in\mathbb Z_p$ and publish $(g^r, m\times g^{rk})$.

Additional part

Let $s$ be randomly selected from $\mathbb Z_p$. Publish $k+s$ and $g^{rs}$.

Problem

If we know $k+s$, $g^{rs}$ and public key $(g,g^k, p)$ is it possible to get $k$, $s$ or $g^{kr}$?

I have found this article (Is this problem same as discrete logarithm?) which is similar, but I cannot find a way it could help me with my problem.

Is this construction easily breakable? Can it be proved by transformation to discrete logarithm problem or other crypto problem?


texts: 2 round GOST_28147-89 cipher distinguisher

texts:
So, here is the scheme of how this will look graphically:

The deal is to present distinguisher for this cipher.
First of all here is my drafts:
Way 1
Assume that distinguisher displays in constant time two plaintexts of  P and $\widehat{P}$ both consist of $P_1$ and $P_2$ parts respectively. The same construction either for cyphertexts C and $\widehat{C}$ with $C_1$ and $C_2$ parts.
I think following formula will be valid for my case too:
$P_2$ $\oplus$ $\widehat{P_2}$ $\oplus$ $C_2$ $\oplus$ $\widehat{C_2}$ = 0 (source) because GOST is Feistel cipher either.
So now I'm stuck here, because I assume that keys are not known as in presented model and that's why further calculations can't be applied to my model.
Maybe I did put too tough conditions about about the key uncertainty?
Way 2.
This comment give alternate vision of problem. Assume that chosen-plaintext attack is selected. This leads to one half arbitrary plaintext encryption and the other half and another side differs only in one bit.
The right half will be fully changed after encryption and in the left half should have changed only in one bit that was inverted.
I do not know how to express all the things that are stated in Way 2 mathematically rigorous and would this finally be distinguisher for cipher once this statement expressed?
Anyway all tips and "to read"-links would be appreciated.


texts:
It is being speculated that one of the ways that NSA leaker Edward Snowden may have created his "insurance policy" – distributing sensitive documents to various individuals with instructions to disseminate them should anything happen to him--is through the use of a partial key escrow.

The concept is described vaguely in the article:

  Modern crypto has lots of ways to accomplish this, including partial key escrow, in which a bunch of encryption keys are distributed to various parties; the individual keys aren't sufficient to decrypt the file, but a quorum of them are. For example, you can release a key to ten people and configure it so that any three can, in combination, unlock the file.

From a technical standpoint, how does partial key escrow work, and how is it most often implemented in practice?


texts:
I read the document(not the whole document) from Shannon where he speaks about the concepts of confusion and diffusion. I read in many places(not in the document but around the internet) that confusion is enforced using substitution. Diffusion is enforced using permutation/transposition. Ciphers must use both of them because either confusion or diffusion alone are not enough. I read that a substitution cipher can apply by itself confusion(only). Permutation/Transposition applies by itself diffusion(only). It's precisely the last case that bothers me: Can a permutation/transposition cipher by itself apply diffusion?

Shannon explains diffusion as a property that spreads statistic properties of text all over the text preventing statistic analysis. It's frequently translated to: an alteration to a plaintext symbol affects many cipher text symbols. Assuming permutation of bits or characters, how can diffusion be achieved by simple permutation? I mean, if you permute bits, there will be no other bits affected.
But if you consider a symbol a character and you permute bits, a change in a character will affect many other characters. It's a question of what is a symbol.

I also read versions of this diffusion concept where the point was just changing bits order just to avoid pattern analysis of the text. But, where is the avalanche effect in simple permutation?

So, what is the correct definition and the implications of diffusion?

I hope you understand what is troubling me.

Thank you once more


texts:
I am working on a device whose OS provides an RSA Private primitive, where the inputs are the message, and the usual components of a private key. Unfortunately it is bugged so that in some cases of supplying garbage for the private key, the device panics instead of returning an error code.

To try and avoid panics I would like to perform some pre-checks on the private key components. However, due to limited device resources, I'd prefer not to install a full Bignum library.

Are there any simple calculations I can do on the key components to check the key is valid?  Time-efficiency is not a problem.

For example I can do peasant multiplication to verify $n = pq$; but what about validating $d_P$, $d_Q$, $q_{\mathrm{inv}}$ and $d$ ?


texts:
I have the following problem: I have a series of numbers (6, 9, 6, 2, 6, 3, 4, 7, 3, 5, 4, 3, 2, 5, 8, 6, 2, 6, 3, 4, 5, 8, 7, 8, 2, 7, 7, 4, 8, 3, 3, 2, 8, 8, 4, 3, 2, 4, 7, 7, 6, etc.), each number instance can correspond to 3-4 different letters (I know the correspondences, for example 2 can be A, B or C, 3 can be D, E of F, etc.).
The sequences of numbers represent sentences of English words (blank spaces are not encoded, so words are concatenated). I know where sentences end, but not where words end.
I have a list of English words, but the sentence may also contains proper nouns, for which I have no list.
I was planning to write a program to search all combinations, starting with the longest words and going through all combinations until the end of each sentence is reached (still I don't know how to deal with proper nouns that are not in my list). Before doing that I just want to ask the question:
Do you know of any existing software that may be adapted to do this?


texts: Where can i find relative software for differential cryptanalysis?

texts: Is there any publicly known software for differential cryptanalysis over some cryptographic building blocks as blocks ciphers or cryptographic hash functions


texts: PRF that can be distinguished after $k$ queries?

texts:
In adaptive attacks, if we design poorly, adversary can modify his queries and break the given pseudo random function (that is being able to distinguish it from uniform randomness).

Is there a poor way to design a PRF such that in one round of query, the adversary cannot distinguish but in two rounds the adversary can?

How about adversary failing to break at $k-1$ queries but breaking at $k$th query?


texts: Impact of distinguishing between random text and cipher text?

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

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


texts: Why does a primitive root mod n gives a uniform distribution over n?

texts:
The result from a primitive root mod n seemly has a uniform distribution over n, is it true? For instance, 3 is a primitive root mod 7, and the result seems to be randomly distributed over 1 and 6,

I wonder why is it, or should I just take it as a basic fact of our universe?


texts: A question about verifier in zero knowledge proof

texts:
I found an article about zero knowlegde authentication and I have question
ethesis.nitrkl.ac.in/5755/1/110CS0371-2.pdf

It said
"In Cryptography, the Zero Knowledge confirmation/convention is a sort of convention in which one entity (claimant) demonstrates an alternate entity (verifier) that a certain information is genuine separated from the way that it doesn't pass on that the data given is genuine or false."

Does this mean that the verifier does not (and will not) know whether the data from the claimant is true or false? Because using the cave analogy, the verifier will know about the genuineness of the data, since the verifier will see where the claimant will come out from (either from the wrong / right path).

From that paper, what I got is: The verifier doesn't know what the data is, and it also doesn't (and won't) know whether the data is genuine or not

Edit: English is not my first language, so maybe I got the wrong conclusion / translation from that bolded part...


texts: Can you fake messages from recorded message-history?

texts:
Lets assume Eve has a lot of PGP conversation with Alice and records all those messages. Bob is also regularly communicating with PGP with Alice.

If Bob doesn't care about not having a signature from Alice, could Eve send any of those recorded messages unchanged but without signature to Bob pretending it came from Alice?


texts: Does there exist a cryptographic algorithm for comparing 2 encrypted strings

texts:
I would like to know if there exists algorithms A and B such that the following is possible.

Say Alice has 2 binary strings S1 and S2 both of length n and 2 keys k1 and k2. She encrypts each string with the corresponding key resulting in S1' and S2' respectively and gives these to Bob. Via algorithm A on S1' and S2' Bob produces R which he returns to Alice. Alice then uses algorithm B to determine x, which is 0 if S1≠S2 and 1 if S1=S2.

Additionally, algorithm B must have constant time complexity with respect to n (the lengths of S1 and S2). Also, at no point should Bob be able to determine the values of S1, S2 or x.

If no such algorithm exists or no such algorithm is known to exist, I would be happy to weaken the time complexity condition so that algorithm B need only be sub linear in terms of n.

Note that I have no particular encryption algorithm in mind, the process of
encrypting S1 and S2 can be anything so long as Bob is unable to decrypt S1' and S2' in addition to not being able to determine x.

Just as with most encryption schemes by "unable to decrypt" I mean "unable to decrypt consistently in a reasonable amount of time".

This is a special case of the more general problem of having another individual do computations on some data without ever seeing the data or the resulting output. This is a problem I have been interested in for some time. If you know of any resources on this topic I would be interested to know about them.

Thanks


texts:
I'm curious about the design of the P_BOX of DES.
I found a paper on this topic, but it dates back to 1989.
This means the effect of p-box values of the cipher immunity against Differential Cryptanalysis and linear cryptanalyisis is not mentioned since they were Publicly discovered during the 90's (According to Bruce Schneier's book "Applied cryptography , the NSA and IBM knew about the attack since the 70s). I tried to look online, but it seemed to me that unlike the S-boxes which have considerable amount of literature, there are no good resources on the p_boxes.

The placement of the p_box in the Feistel function is shown here:

The permutation itself is shown here:

Previously on Crypto.SE, we explored the roles of the initial and final permutations and how they impact security. What about the permutation in the Feistel function? What impact (if any) does it have on security?


texts: SHA3 Keccak, absorbing data to the state

texts:
I'm working on implementation of keccak algorithm and have one problem. Tell me please, takeing an example "test": will state (before block permutations, but after padding - pad10*1) look like this:

{80...0 0 0 0 0} {0 0 0 174736574 0} {0 0 0 0 0} {0 0 0 0 0} {0 0 0 0 0}

or maybe like this:

{80...0 0 0 0 0} {0 0 0 0 0} {0 0 0 0 0} {0 174736574 0 0 0} {0 0 0 0 0}

assuming that padded "test" look like this:
0x0000000174736574,
0x0000000000000000,
0x0000000000000000,
0x0000000000000000,
0x0000000000000000,
0x0000000000000000,
0x0000000000000000,
0x0000000000000000,
0x8000000000000000,

I mean: 174736574 will be on A[1,3] or A[3,1] or somwhere elese?

It's hard for me to understand, because i implemented all functions. I checked all functions - they work properly. But my hash is still different that proper hash calculated on the websites. I suppose that mistake is in absorbing phase. I will be gratefull for answer.
And if i am wrong, how properly put data into the state?


texts: Main purpose for Carmichael's Function in RSA

texts:
I'm trying to understand the RSA cryptosystem, these are the steps:

Generate two large different prime numbers $p$ and $q$.
Calculate modulus $n$ ($n=pq$)
Calculate: $λ(n) = \operatorname{lcm}(λ(p), λ(q))$

I'm trying to understand the step 3. As we know, the original RSA document uses Euler's Totient Function - $\phi(n) = (p-1) \cdot (q-1)$ (which outputs the amount of numbers that are coprime to $n$).

But, Carmichael's function is smallest positive integer $m$ such that: $$a^m \equiv 1 \pmod n.$$

From my knowledge, $λ(n) \mid \phi(n)$ according to Lagrange's theorem (abstract algebra group theory). Thus that seems to be the only reason why Euler's Totient Function was used in the past, making Carmichael's function more appropriate?

The fourth and fifth step is to create public exponent and modular multiplicative inverse of modulus n as decryption key.

The public exponent must be $e$ such that: $$1 < e < λ(n) \quad\text{and}\quad \gcd(e, λ(n)) = 1.$$

Is the "rule" above necessary? I think I've seen different versions of RSA cryptosystem where large exponents are randomly generated (exceeding output of $λ(n)$).

The private key is found by this congruence: $$d ≡ e^{−1} \pmod{λ(n)}.$$

Meaning, utilization of Extended Euclidean Algorithm is not necessary?

I understand Bézout's identity, Euclid's lemma, Euler's totient function, and multiplicative group of integers modulo $n$ (a little). But what is the easiest explanation for the purpose of Carmichael's function in RSA algorithm?

Thank you!


texts: How did "Secure Voice" work on the old Air Force One's?

texts:
I recently visited the "Museum of Flight" where they have an old SAM 970, previously known as "Air Force One".

Inside there is a comm station with many buttons designated "Secure Voice", as can be seen on the lower row of controls in the attached picture. The plaque says "During the Johnson and Nixon eras, "Air Force One" was equipped with a radiophone on which secret voice messages could be scrambled and sent. It rarely functioned properly and was removed to save weight." Therefore I suspect that the buttons and controls in question is not related to this radiophone.

Does anybody know what kind of Secure Voice communications they used these controls for, and how these works?

As a bonus, if the radiophone that rarely worked could be explained as well, I'd really appreciate it :)


texts:
How can you encrypt $n$ messages with the same key, and have the same theoretical security you'd have encrypting a single message with a one time pad? For example, how can you encrypt two messages with the same key, and have that same theoretical security?

I think for $n=2$, something like $E(M) = (K_1M + K_0) \mod p$ should work, for prime p, $0 \leq M \leq p-1$, and each part of the key $K_i$ randomly chosen so $0 \leq K_0 \leq p-1$ and $1 \leq K_1 \leq p-1$.

This seems like the sort of thing that may have already been worked out or proved impossible, but I couldn't find it.


texts: The collision rate probability decreases when using compression?

texts:
Some standard compression procedures, like the  IANA's gzip
provided by HTTP protocol, will consume CPU-time anyway...
So we can reuse compressed file, $Z(x)$, in the checksum procedure.
That is, we can use $H(Z(x))$ instead $H(x)$.

Let $H$ be a collision resistant hash function and $P_c[H](S)$
the collision rate probability
about a sample set $S$ of input elements (eg. random numbers).
It decreases when using $Z(x)$? $P_c[H\circ Z](S) \le  P_c[H](S)$   ?

Intuitivally we can imagine some decrease in collision-rate because hashing a file is similar to an aleatory sampling procedure:
if we reduce the redundance in the sample set, we reduce collision probability.
HTML, XML, and many other file formats have a lot of redundancy.

If the intuition is correct, the questions is also about "how mutch better is it"?

NOTICE: I am using the strange term collision rate probability (with a link to this other question) to avoid confusion with the "general collision probability". Please take care to not mix the concepts in the answer.


texts: disadvantages of combination stream and block ciphers

texts:
I've encountered some papers online describing ciphers made through a combination of stream and block ciphers. (See this 2008 paper by Sandy Harris: https://eprint.iacr.org/2008/473.pdf)  In a nutshell, the concept is to use the output of a stream cipher to add whitening and/or update the round keys of a block cipher.  The paper referenced above describes a combination of AES and RC4.  Other examples of this concept I've seen are a cipher called Eris, combining HC128 and Serpent, and a cipher called Enchilada, combining ChaCha and Rijndael. Enchilada was an entry in the Caesar authenticated cipher contest but was withdrawn in the initial rounds.

The security claims for these combination ciphers are impressive.  Standard attacks against the stream cipher portion should be thwarted by the block cipher, and attacks against the block cipher should be complicated by the use of unique round keys for each block of cipher text.  The speed of these combination ciphers can be comparable to (or even better than) the block cipher by itself, because the number of rounds in the underlying ciphers can be reduced.  (For example, Enchilada runs 12 rounds of ChaCha versus the standard 20, and Eris uses 24 round Serpent, versus the standard 32 rounds).

What I have not been able to find is any cryptanalysis or research on these types of combination ciphers.  On the surface, and with my limited knowledge, there appear to be more advantages than disadvantages to this approach.  At the very least, it looks like a promising topic for research.  Yet the fact that there is so little information in the literature suggests these combination ciphers have flaws I am unaware of.  Which brings me to my question:  what are the disadvantages or weaknesses of this combined approach?


texts:
We already know that every authenticated encryption scheme is CCA secure, I was wondering about the converse.
I believe it is not true, and I am finding trouble to construct a scheme which is only CCA secure but is not an authenticated encryption.
How to show the existence of an encryption scheme which is only CCA secure but is not an authenticated encryption?


texts:
Is Computational Indistinguishability quantifiable?
I know that the success probability should be negligible, which however seems to be somewhat ambiguous.
Is it possible (and usual) to say that given encryption scheme is said to be something like it is computationally secure with some probability?
I've been using an IND-CPA secure public key crypto so far.


texts: Dieharder input data format. Do I need new line at the end?

texts:
I am testing my sequence for randomness using Dieharder with a command like dieharder -a -g 202 -f in.txt >>result.txt

my in.txt looks like

#==================================================================
# generator mt19937  seed = 316179543
#==================================================================
type: d
count: 40000004
numbit: 32
1635395663
 509326050
4144493458
...  // 40M more lines of numbers
3557717321
//Does Dieharder need this empty line before the end of file?

If 3557717321 is the last number in tested sequence, does Dieharder expect an empty line after it? Shoud the file end with 3557717321 or 3557717321\n?


texts: Outsourced Multiparty computation proof in Ideal world

texts:
I need to know in an outsourced two party computation where honst $A$ and $B$ outsource their private and secure data to a malicious server, why we need to design a simulator that interacts with an adversary who exists in real model?

See the paper cited below as an example:

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


texts:
I have a question about Modular Arithmetic Cryptography.

How do I calculate $(-5)^{-3}$ or $(-5)^{-4}$ (even or uneven exponent)?

What do I have to do first here ? I can’t ignore the minus?!?


texts: Using PBKDF2 twice with different argument order

texts:
I'm pretty sure this is a really bad approach (in theory), but one of my clients is doing this and I was wondering… How bad it is to perform pbkdf-2 in this way (with 2000 iterations)?

a = PBKDF2(x, y)
b = PBKDF2(y, x)

x is the username (password in pbkdf2)
y is the password (salt in pbkdf2)
2000 iterations

a is then used for some authentication in the system and "b" is used for encryption.
a and x are also stored and therefore known.

Is it subject to some class of attacks or is it just a really bad crypto nightmare which is only subject to brute-force attacks?

EDIT 1:

More specifically: a is used as key to retrieve user data from the DB (thus, a is sent to server), data is returned and partially encrypted. You need b to decrypt what you get.

EDIT 2:

Let's say that an attacker gets access to the database where these hashes are stored. What kind of attacks could he perpetrate?