texts: Average number of multiplications in left-to-right k-ary exponentiation

texts:
On page 617 in chapter 14 of  The Handbook of Applied Cryptography, the average number of multiplications in left-to-right k-ary exponentiation is $ l\times (2^k-1)/2^k$, where $l=\lfloor t/k\rfloor $, i.e. the number of k words in the $t+1$ bits exponent after excluding the leading 1. My question is, do the residual $t\;mod\; k$ bits require one extra multiplication when it is even, because we only precompute the odd number < $2^k$ ? If this argument is true, how should I calculate the correct average number of multiplications?

Thank @galvatron, especially for CPython implementation.  May I use an example to make my question clear.Let's say I want to calculate $x^{364086}$ with $k=4$. Because $364086=1011|0001|1100|0110|110_{2}$,$t+1=19$, $t=18$ and $l=\lfloor18/4\rfloor$=4. We will precompute $x^3$, $x^5$, $x^7$, $x^9$, $x^{11}$,$x^{13}$,$x^{15}$. Then calculate steps are

$x^{11}$ (from precomputation, no multiplication)
Square $x^{11}$ for 4 times we have $x^{176}$. Multiply it by $x$, we have $x^{177}$
Square $x^{177}$ for 2 times, we have $x^{708}$.  Multiply it by $x^3$, we have $x^{711}$. Sqaure $x^{711}$ for 2 times, we have $x^{2844}$
Square $x^{2844}$ for 3 times,we have $x^{22752}$.Multiply it by $x^3$, we have $x^{22755}$. Square $x^{22627}$ for 1 times, we have $x^{45510}$
Sqaure $x^{45510}$ for 2 times, we have $x^{182040}$. Multiply it by $x^3$, we have $x^{182043}$.Square it for one time, we have $x^{364086}$ (This is the residual bits which require one multiplication, but the chance this residual bits require multiplication is not precisely $(2^{4}-1)/2^{4}$, instead it is $(2^{3}-1)/2^{3}$)

I make a serious error that first k-bits word need one time of multiplication, and I apologize for it. However I still had some questions about this algorithm in the book.
The handbook also says the worst scenario require $l-1$ multiplication, but in this case we have to perform $4>l-1$ times of multiplication.


texts: Why XOR and NOT is free in garbled circuit

texts:
I am having trouble understanding the term "free" in V.Kolesnikov et al's paper.

1. Why NOT is free

In page 4, section 3.1, they said that NOT gate is free

  by simply eliminating them and inverting the correspondence of the wires’ values and garbling

I came up with the following example, which confused me

Let's say that $a,b$ are two single digit inputs from Alice and Bob, respectively.
Suppose Alice is the garbler, she garbles the above circuit and sends to Bob, along with her garbled input $GI(a)$. She then sends Bob's garbled input $GI(b)$ to Bob through obvlivious transfer.  In this example, without trying to implement NOT "for free", Alice only has to send

garbled circuit $\hat{C}$, which contains 7 wires (in different colors above), each with two labels
.$GI(a)$
$GI(b)$, and Bob can figure out the result.

Following the first step "simply eliminating them", I remove all the NOT gates and get the following circuit

Now, AND1 and OR1 shares the same input from $b$. No matter how I invert the wire's value, the circuit will not represent the same function as before.

It seems now I have to separate the inputs for AND1 and OR1, and then give them different labels, although they came from a single source in the original circuit. Then the circuit would still have 6 wires, which isn't quite "free". If it was free, shouldn't we be able only to use 5 wires to construct the ciruit?

2. Why XOR is free
In the same page, they showed their XOR gate $G$.

I see that by doing this the garbler won't have to generate random labels for $w_i^1$ and $w_c^0$. But why is it called free?

In addition, what's the computational saving between generating random labels for all wires and generating only $w_a^0,w_b^0,R$ then computing other labels from the three?


texts: Can RSA with padding detect all errors in ciphertext?

texts:
I'm new in cryptography and there are a couple of things that i'm not sure if i understand correctly.

First, when using padding (PKCS or OAEP), if the chiphertext has errors in transmission we'll we always get an error at the decyption process? Will it detect all errors, or is there a possibility that a certain combination of errors will result in a decryption but with a false result in plaintext?

Second, if no padding is used, (i believe it is called vanilla rsa?) and there are errors on the ciphertext, then the decryption will work any time but will give wrong results instead of the original encrypted plaintext?

Finally with padding or not, with no errors on ciphertext and by using a wrong private key will we get an error in decryption or just a false decrypted plaintext?


texts: Is there any general description language for block ciphers?

texts:
In page 9 (16 in the PDF) of Final report of European project IST-1999-12324 (NESSIE), it is mentioned that:

  The NESSIE project is also developing a new generic tool to analyze block
  ciphers with differential [78] and linear cryptanalysis [422]. This tool is based on
  a general description language for block ciphers.

Is this "description language" publicly available?
Is there any other general description language for block ciphers or stream ciphers?
Is This tool publicly available?


texts: perfectly secret with key chosen uniformly

texts:
Prove or refute: Every encryption scheme for which the size of the keyspace equals the size of the message space, and for which the key is chosen uniformly from the keyspace, is perfectly secret.
My attempt:
I think the statement is false because I made a counterexample:
$M = \{a, b\}, K = \{k_1, k_2\}, C = \{0, 1\}$. Let $\operatorname{Enc} (k, a) = 0$ and $\operatorname{Enc}(k, b) = 1$ for $k\in\{k_1, k_2\}$. The algorithm will return $a$ in the input ciphertext $0$ and $b$ in the input ciphertext $1$. Clearly, the schema is correct. But if we compare with the rule: $$\Pr [C = c | M = m_0] = \Pr [C = c | M = m_1]$$ We have to : $$\Pr [C = 1∣M = a] = 1 \neq 0 = \Pr [C = 1∣M = b]$$


texts: Can I switch out a private RSA Key, so that when decrypting a message, it is decrypted to a different message?

texts:
Here's a task I've been struggling with:
Say I have an encrypted message $c$, and a desired plaintext $m$. How can I define a valid private RSA Key $(d,N)$, so that $c^d \bmod N = m$

Note that the key needs to be valid!
My approach was to write the modulo equation as
$y \times N + m = x \times N + c^d$ so I get $c^d-m'=(y-x) \times N$. So I can simply set some value for $d$ and try to factorize the result to get $N$, but this factorization can be extremely hard because numbers are huge. Is there a better way to approach this?


texts:
I am reading through an information security book right now, and a confusing question poses itself to me:

"Could you use a MAC as a HMAC? That is, does a MAC satisfy the same properties that a HMAC satisfies?"

The book then goes on to give a hint about how MACs are computed by CBC mode of a given symmetric block cipher that involves K the key, and to consider when K is known to an attacker for both HMAC and MAC.

Here's the confusing part: Isn't a MAC just a code created from a MAC algorithm, while a HMAC is a type of MAC algorithm? I do not see how any of these hints could be applicable to the question when a MAC and a HMAC are so clearly similar (to a novice).

Am I right in this thinking?


texts: I try to generate other S_BOX for AES but I don't realize how to choose additive constants for S_BOX from decryption if for encryption it is 0x63 why is 0X05 used for decryption?


texts:
I'm working on a C implementation of the FF1 and FF3-1 format-preserving encryption algorithms, here.
For FF1, NIST provides test vectors, here; however, none of the test vectors is crafted such that d is ever greater than 8, such that Step 6iii is never executed in the code. Does anyone know of any test vectors that exercise that part of the algorithm?
For FF3-1, I have not found any "official" test vectors. Is anyone aware of any that have been published?


texts: Can I store the initialisation vector (IV) in the filename?

texts: I'm encrypting a file and I'm using an initialisation vector. Given that the IV doesn't need to be a secret, is it secure if I add it to the encrypted file's name?


texts:
I am trying to import RSA and AES-GCM keys in jwk format using Web Crypto API on Internet Explorer 11. Can anyone give me examples of how to do it?

The reason why I am asking is according to this msdn page, the keyData parameter must be an ArrayBufferView. However, if the format parameter is jwk, the function should accept a Dictionary containing the key in jwk format, which is how Chrome and Firefox work. I have no idea about how to convert a Dictionary to an ArrayBufferView.

The examples I found here do not work for IE.


texts: If the distinguishing advantage of A wrt distribution D_n, E_n is 1/poly(n) with probability .1, then are they not computationally indistinguishable?

texts:
As in the title, but to make more clear:
If, with probability 0.1, an algorithm A can distinguish between two ensembles D_n, E_n (indexed by sec. paramater n), then are D_n, E_n not computationally indistinguishable?
More generally, is it true that, $$\Pr_A\Big[\big|\Pr_{x\sim D_n}[A(x) = 1] - \Pr_{x\sim E_n}[A(x) = 1]\big|>\epsilon\Big] = 0.1 \implies \big|\Pr_{x\sim D_n}[A(x) = 1] - \Pr_{x\sim E_n}[A(x) = 1]\big|>\epsilon/10$$


texts:
If symmetric cryptosystems have $C^2_n$ keys, and asymmetric systems have $2n$ keys, how many does a hybrid system have?  This was in an online quiz from school

  Company A is considering to adopt a cryptosystem for secure communications among its employees. Currently it has $5$ employees. Assume that every employee has used the adopted cryptosystem to communicate with all other employees once.

3) c. If the company adopts hybrid cryptosystem, how many keys would be used in this case? Show your working.

My answer was

  $C_n^2$ symmetric session key + $2n$ asymmetric keys

  $= C_5^2  + 2 \times 5$

  $= 20$ keys

This was marked wrong. Where did i go wrong here? As far as i understand, in a hybrid system they make use of asymmetric keys to encrypt the symmetric session key, which is used to encrypt/decrypt the document.


texts: hash functions preimage and second collision resistance

texts: A hash function H is secure in terms of pre-image resis-tance. Does this imply that H has second pre-image (aka weak collision) resistance?


texts:
A sponge function is supposed to be able to generate an arbitrary length of output. Yet, SHA3 (Bouncycastle) constrains me to choose an output length between 224, 256, 384, and 512. Evidently, these are not arbitrary lengths. How then is SHA3 a sponge function?

Is there a specific way to generate "arbitrary length" using bouncy castle implementation?

Here is my code:

     SHA3.DigestSHA3 digestSHA3 = new SHA3.DigestSHA3(320);
     byte[] digest = digestSHA3.digest(bip39Seed);

What am I missing?

My uneducated guess is that the standardized version of Keccak is different from the original one that was submitted to NIST. If this is the case, how can I get to the version that allows me to specify arbitrary lengths?


texts: Near in place encryption with BouncyCastle CCM, How large must IV and MAC be?

texts:
I need to encrypt 20 bytes of data and the encrypted nonce + data + mac cannot exceed 30 bytes in size. I have an implementation but i'm not sure if i'm cutting too many corners and compromising encryption.

Using the bouncy castle library i was able to write this.

    static (byte[],byte[]) encrypt(byte[] data, byte[] key, byte[] nonce)
    {
        var engine = new AesEngine();
        var parm = new AeadParameters(new KeyParameter(key), 16, nonce);
        var chipher = new CcmBlockCipher(engine);
        chipher.Init(true, parm);

        var output = new byte[chipher.GetOutputSize(data.Length)];
        var outputLength = chipher.ProcessBytes(data, 0, data.Length, output, 0);
        chipher.DoFinal(output, outputLength);

        return (output, chipher.GetMac());
    }

Here is my thinking. For the data encrypted i have the following pieces of information known:

Metadata about the origination of the data
The approximate date the data was encrypted (down to the day)

With that information i formulated a nonce that contains:

2 bytes meta + 8 bytes Unix ms timestamp

With that i'm able to chop off all but the last 4 bytes of the nonce as those are the least significant bytes that indicate a timestamp for the day in question.

With that in mind i can have the final full encoded data as:

4 byte nonce + 20 byte encrypted + 2 byte MAC

This makes it fit under the 30 byte limit.

So here are my questions:

Is a 16 bit MAC effective at all in this scenario?
Is it kosher to create a nonce from partially known data?
How can i verify that my nonce is being incremented properly inside the code? I just appear to pass a static nonce even though its supposed to increment according to CTR... right?


texts: Proving multiple products "in the exponent"

texts:
I'm trying to come up with a small-sized (non-interactive) proof for a Diffie-Hellman-like statement.
I'll start by giving an example.

The prover has $g^a, g^b, g^c, g^{ac}, g^{ab}, g^{bc}, g^{abc}$.
The verifier only has $g^a, g^b$ and $g^c$.
Nobody (not even the prover) knows the exponents $a,b,c, ab, ac, bc, abc$.
The prover gives $g^{abc}$ to the verifier and wants to convince him it has done so.

To convince the verifier, the prover can give him a proof consisting of $g^{ab}$.
The verifier can check with a bilinear map that $e(g^a, g^b) = e(g^{ab},g)$ and $e(g^{ab}, g^c) = e(g^{abc}, g)$.
(I believe we also need to make all group elements "extractable" for this to be secure, but I'm ignoring this for now.)

Assuming this approach for proving $n=3$ "products in the exponent" is sound, the first challenge is it doesn't scale to large $n$: the proof size is linear in $n$.

To see this, let's extend the above example to arbitrary $n$.
Specifically, suppose the prover and verifier have $g^{a_i}$'s for all $i\in [1,n]$.
In addition, the prover has $g^{\prod_{i\in S} a_i}$ for all subsets $S$ of $[1,n]$.
The prover gives $c$ to the verifier and wants to convince him that $c = g^{\prod_{i=1}^n {a_i}}$.
Then, the proof will be a tree whose root is $c$, its leaves are the $g^{a_i}$'s, and its internal nodes with their children are DDH tuples (i.e., parent is $g^{\alpha \beta}$ with children $g^{\alpha}$ and $g^{\beta}$).
The proof consists of all the internal nodes in this tree, of which there are $O(n)$.
Unfortunately, this is too large.

The second challenge is we want the prover to pick a subset of indices $S \subseteq [1,n]$, compute $c = g^{\prod_{i\in S} a_i}$, give $c$ to the verifier and convince him that there exists some subset $S$ of $[1,n]$ such that $c = g^{\prod_{i\in S} a_i}$, without actually having to reveal $S$ itself, which is too large.

Questions:

Can Groth-Sahai NIZKs [1] be used to efficiently prove such a statement in bandwidth $o(n)$? (Maybe $O(\sqrt{n})$?)
Can you think of other cryptographic techniques that can be applied here?


texts: Proof that the cardinality of the cipher text set is greater than or equal to the cardinality of the plaintext set for a symmetric cryptosystem

texts:
I have been working on this problem and would appreciate some help
Consider a symmetric cryptosystem with non-empty finite sets $P, C, K$ of plaintexts, ciphertexts, and keys, respectively and with encryption functions $e_k : P \rightarrow C$ and decryption functions $d_k : C \rightarrow P$ indexed by keys $k \in  K$.
Show that $|C| \geqq |P|$

Here is my attempt:
Since $d_k$ is the left inverse of $e_k$ by definition of a cipher
Suppose $e_k(x) = e_k(y)$ then $x = d_k(e_k(x)) = d_k(e_k(y)) = y$ for $x \in P$ and $y \in C$
meaning $e_k$ is injective $\forall k \in K$
Also, $e_k(p) = c \in C, \forall p \in P$
Suppose, for finite sets $P$ and $C$, $|P| \gt |C|$
And, since both $P$ and $C$ are non-empty, then $|C|$ is at least 1 and $|P|$ is at least 2.
Then $\exists a,b \in P$ s.t $a \neq b$ and $e_k(x) = e_k(y)$ which raises a contradiction (as it would mean $e_k$ isnt injective)
Thus, $P \not\gt C$ i.e $|P| \leqq |C|$ or $|C| \geqq |P|$


texts:
Confused with color abstraction in this video.

Bob has:

public color;
mixture from Alice;
can produce random color;

Eve has:

public color;
mixture from Alice;
can produce random color (why not?);

Bob can produce same shared color as Alice did, Eve cannot. Does it make sense?


texts: How modern messengers encryption keys can't be hacked

texts:
I dont know is this question more like reverse-engineering or cryptographic.
Why governments are hunting for encryptions keys? Aren't they delievering by the network the same as the encypted messages? What doing it end-to-end encrypted?


texts: Is inverse of a combination function negligible?

texts: Can anyone help me in determining whether $1/{n\choose a}$ negligible function for sufficiently large value of $n$, say for example $n=p^2$ and $a=p$, for an integer $p$?


texts: Optimizing the AES key schedule when round keys cannot be cached

texts:
I have an implementation of AES which can cache at most a 256-bit value between encryptions. Currently, the master key is cached and the key schedule is re-computed for each and every block. Is there any intermediate ≤ 256-bit value which can be derived from the master key which I can cache and use to compute each round key faster than re-running the entire key schedule?

The implementation is in x86 assembly in 64-bit mode and uses the AES-NI extensions. This means I have the AESKEYGENASSIST instruction, which performs the following in 10-12 cycles:

X3[31:0] ← SRC [127: 96];
X2[31:0] ← SRC [95: 64];
X1[31:0] ← SRC [63: 32];
X0[31:0] ← SRC [31: 0];
RCON[31:0] ← ZeroExtend(Imm8[7:0]);
DEST[31:0] ← SubWord(X1);
DEST[63:32 ] ← RotWord( SubWord(X1) ) XOR RCON;
DEST[95:64] ← SubWord(X3);
DEST[127:96] ← RotWord( SubWord(X3) ) XOR RCON;
DEST[MAXVL-1:128] (Unmodified)


texts: X9.62 Multiplying an elliptic curve point by a number

texts:
I'm currently trying to implement ecdsa and the first problem i met --  multiply an elliptic curve point by a number.

As far as i understand X9.62 gives some recommendation for doing it but i haven't managed to find anything.
It would be great to see some program like algorithm.

P.S.
Any help is appreciated. Sorry for my English and thanks.


texts: $\alpha^{2^{m} + 1}$ is a generator of $\operatorname{GF}(2^m)$?

texts:
This is from a paper (Partitions in the S-Box of Streebog and
Kuznyechik) about S-Boxes:

Let $\operatorname{GF}(2^{2m}) = \mathbb{F}_2[X]/p(X)$ be a finite field of even degree defined by a primitive polynomial $p$. The multiplicative subgroup $\operatorname{GF}(2^{2m})^*$ is cyclic and generated by $\alpha$ which is such that $p(\alpha) = 0$.
In this context, $\alpha^{2^{m} + 1}$ is a generator of the multiplicative subgroup of the subfield $\operatorname{GF}(2^m)$

I don't understand why it holds that $\alpha^{2^{m} + 1}$ is a generator of the subfield?


texts: Malicious Model and Arbitrary selecting inputs on MPC and PSI

texts:
Imagine the following setting: a party considers a secret sharing or multiparty protocol that is secure against semi-honest adversaries. The adversary selectively chooses the inputs such that it could learn the inputs of its counterparts from what is derived from the output.

A simple example could be taken from any Linear Secret Sharing Scheme Alice secret shares $x$ and Bob $y$ and want to compute $x+y$. Under this scenario, Alice could choose $x=0$, so that she learns Bob's input.

A more complex scenario is what sometimes is described as the full universe attack on Private Set Intersection (the problem of 2 parties computing the intersection of their sets). The attack in this case is as follows: Alice holds a vector $X$ and Bob a vector $Y$, and want to compute the intersection $X ∩ Y$. In this case the attack consists on Alice replacing its set $X$ by a set $X'$ containing all possible inputs on the universe.

From my understanding of what the security definition of MPC is (and the use of an ideal functionality) this attack would be possible under a semi-honest model. My question is the following: Is such attack possible when a malicious adversary is considered? And more importantly, can I consider such adversarial behavior as malicious, or is it indifferent from the MPC security model?

From my understanding of the implications of a malicious adversary and the capabilities of protocols that are secure against malicious adversaries, such as BGW, SPDZ or MASCOT, such an attack would still be possible. However I have recently come across this work on PSI https://eprint.iacr.org/2013/515.pdf, where they classify such attack as a malicious attack, given that the adversary is manipulating its input to learn other parties inputs.


texts: What is the history of recommended RSA key sizes?

texts:
One can find up to date recommended key sizes for RSA at NIST sp800-131A for example. In short, it suggests a key size of at least 2048 bits.
Is it possible to find a history of recommended key sizes for RSA, going back to the invention of RSA?


texts: Do Carmichael's and Euler's totient functions in RSA generate the same keys?

texts:
Starting with the same primes $p$ and $q$ to generate $n=pq$, will Carmichael's totient function and Euler's totient function give the same public key ($e,n$) and private key ($d,n$) in RSA encryption?

If not, are there specific types or range of primes $p$ and $q$ that result in the difference?

THANK YOU!


texts: Derive a public EC key from two public EC keys

texts:
Alice has two EC key pairs: $a_1$, $a_2$ are private keys (integers), $A_1$, $A_2$ are the corresponding public keys (points). Alice and Bob want to create a new public key $C$. Alice must prove that this key $C$ was created from exactly $A_1$ and $A_2$, i.e. Alice did not use other key pairs for $C$. The new public key $C$ would be used for ECDSA. The private key $c$ is created from $a_1$ and $a_2$ and is usable for ECDSA with $C$. The private key $c$ must not be able to be created from only $a_1$ or only $a_2$.

The algorithm will be generalized to $n$ key pairs. My thoughts for case of 2 keys are below.

Which algorithm can be used for that? I have two ideas:

Addition of $A_1$ and $A_2$: $C = A_1 + A_2$. Bob can verify this, since he knows $A_1$ and $A_2$. The private key would be $c = a_1 + a_2$. This works because $(a_1+a_2) \cdot G = a_1 \cdot G + a_2 \cdot G = A_1 + A_2$. Clear. But how secure is it? Can an ECDSA signature of the public key $C$ be created without both $a_1$ and $a_2$? Maybe $a_1$ or $a_2$ only is enough for this? I don't know.
Multiplication. $C = a_1 \cdot a_2 \cdot G$. Verification is complicated if it is even possible. If Bob knows $A_1$, $A_2$ and $C$, how can he verify that $C$ was composed exactly from private keys corresponding to $A_1$ and $A_2$ (maybe with Alice's help, but without possessing ability to sign with $C$)?

Example of vulnerable verification (for proposal 2): Bob generates a random number $r$ (not available to Alice), computes $r \cdot A_1$ and asks Alice to multiply this by $a_2$. Alice sends $a_2 \cdot (r \cdot A_1)$ to Bob. $a_2 \cdot r \cdot A_1 = r \cdot a_1 \cdot a_2 \cdot G = r \cdot C$. Bob compares $a_2 \cdot (r \cdot A_1)$ sent by Alice with $C$. Then he does the same with $A_2$.

This is vulnerable: Alice computes $C = a_1' \cdot a_2' \cdot G$. Bob generates $r \cdot A_1$ and asks Alice to multiply it with $a_2$, Alice multiplies it with $a_2' \cdot (a_1'/a_1)$. So the result of the multiplication is $a_2' \cdot (a_1' / a_1) \cdot (r \cdot A_1) = a_2' \cdot (a_1' / a_1) \cdot (r \cdot a_1 \cdot G) = r \cdot a_2' \cdot a_1' \cdot G = r \cdot C$. So Bob mistakenly believes that $C$ is derived from $A_1$ and $A_2$. Division by $a_1$ is multiplication by $a_1^{-1}$, which can be calculated from $a_1$ using a multiplicative inverse.

Please, prove that algorithm proposed in item 1 (addition) is correct or provide correct verification for algorithm 2 (multiplication) or provide your own or existing algorithm which is appropriate for the task.


texts: Can you help me understand indistinguishably as described in the CPA security definition?

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

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


texts: Can a public key be same as private key?

texts:
As I understand, we choose the public and private keys to be mutual inverses. However, it is possible that, in a group, there can be numbers which are their own inverses.
E.g. Consider p = 7, q = 3. n = 21, phi(n) = 12.
For the group G = {s | gcd(s,21) = 1} there are four numbers 1, 8, 13 and 20 which are their own inverses.

In such a case, it is possible to choose these numbers as both private and public keys. Isn't it?

Let me know if I have understood this correctly.


texts: Is a keyed MAC sufficient for integrity protection?

texts:
I'm working with the above figure which shows a challenge-response protocol.

Kc - shared key between the host and the client
B' - is a biometric captured by device
BT' - biometric template computed from B'
D' - device authenticator.

Match(BT', BT) returns yes if the user computed biometric matches with the template, no otherwise.

Verify(D', D) checks the validity of the authenticator. If all succeed at the host, host returns yes.

My question is, does message 3 from client > host need to be encrypted for integrity protection?

My instinct is no it doesn't, and using a keyed MAC is sufficient, because encryption does not guarantee integrity protection.


texts: Why is this homomorphic encryption correct?

texts:
In LTV-FHE, section 3.3.2 Formal description, a ciphertext looks like this $c=hs+2e+b = (2g/f)s+2e+b$, where $h = 2g/f$ is the public key, $f$ is the secret key, $g, s$ and $e$ are chosen randomly, and $b$ is the bit to be encrypted.

Following the equation $c = (2g/f)s+2e+b$, the bit $b$ can be obtained easily performing a modulo 2 operation for a ciphertext.

What is the hardness that protects against this simple modulo reduction ?


texts: How to forge signatures in the Schnorr scheme if $r=g^k$ is eliminated?

texts:
I need some help to demonstrate how to forge signatures in the Schnorr scheme if I eliminate the random string $r=g^k$ used in the hash – using $H(M)$ instead of $H(M||r)$.

How would one be able to forge signatures in the Schnorr scheme if $r=g^k$ is eliminated?


texts: What is the difference between signatures and VRF?

texts: For example we have asymmetric signature scheme(RSA or ECC based) and VRF(also can be RSA/ECC based), both of them can be verified using public key of the signer/hasher and also are unique for each message. So what is the difference?


texts: SPDZ protocol: how expensive is it to generate the multiplicative triples?

texts:
I am currently reading the full version of the SPDZ protocol. I understand that the online phase does multiplication with computational and communication complexity $O(n)$ by using Beaver's multiplicative triples as explained $\Pi_{Online}$ (Fig 1, page 5). These triples are numbers $a$,$b$ and $c$ such that $ab=c$, where $a$ and $b$ are random. These triples are generated in the preprocessing phase, as explained in protocol $\Pi_{Prep}$ (Fig 7, page 13) which depends on protocol $\Pi_{Reshare}$ (Fig 4, page 12), to decrypt the value of $c$ and distribute its shares among the players.

$\Pi_{Reshare}$ uses $F_{KeyGenDec}$ to decrypt $e_{m+f}$ to obtain $m+f$. $F_x$ in the paper represents some ideal functionality $x$, and typically there is a protocol, $\Pi_x$ that implements that functionality. In Definition 1, on page 10, they mention that such an implementation $\Pi_{KeyGenDec}$ is required for the cryptosystem. However, I was not able to find the implementation of this KeyGenDec functionality in the paper (including appendices).

Where could I find an implementation of KeyGenDec? How long does this protocol take to run? Is this the bottleneck in the time required to generate the triples?


texts: Is Diffie-Hellman key exchange for multiple parties used in practice?

texts:
After reading this question about the possibility of using DH key exchange for multiple parties I went looking for a (C) library able to do this and found none.

(I find it hard to believe there is no library for this, and my assumption is I'm looking in the wrong place.)

Are there libraries able to reach DH key agreement from three or more parties (ideally, with ECDSA); or is this theoretical and not used in practice?


texts: Hash function with values in a multiplicative group of prime order

texts:
I have to implement a cryptographic protocol which involves a cryptographic hash function $H: \{0,1\}^* \to G$. It is viewed as random oracle. $G$ is a multiplicative group of prime order.

I want to know the steps to implement this function. Are there standard functions to do this?

The protocols also have pairing operations. It would be helpful if you could shed some light on their implementation too.


texts:
I have been looking at an embedded microcontroller which has a cryptographic hardware engine (in particular the PIC32MZ family). These devices have what they advertise as a cryptographically secure PRNG, as well as a true random number generator.

The features of the random number generators are,

  TRNG:

  List item
  Up to 25 Mbps of random bits
  Multi-Ring Oscillator based design
  Built in Bias Corrector

  PRNG:

  LSFR-based
  Up to 64-bit polynomial length
  Programmable polynomial
  TRNG can be seed value

From what I've read about LFSR PRNG (in particular this answer) my understanding is that you only require 2*n bits to be able to determine the polynomial of the LFSR and hence all the random numbers that it generates.

If my understanding is correct, then only 128 bits (16 bytes) of random data are required before the random data is compromised - that is just enough for a single AES IV.

One way that I can imagine making the PRNG cryptographically secure is to reseed it after every 16 bytes using the TRNG - would this be secure?

Is it even possible to make a LFSR cryptographically secure?


texts: Simulatability of Diffie-Hellman Key Exchange

texts:
While reading through Shoup's paper on provably secure Diffie-Hellman key exchange (DHKE), I do not understand something rather simple.

There are two parties $A$ and $B$. $A$ starts by sending $g^a$, and then $B$ sends $g^b$. Both compute $g^{ab}$. For an adversary, $g^{ab}$ should be indistinguishable from a randomly chosen $g^c$. How would one simulate this without commitments?

This is like coin toss: in the ideal world, parties do not have an input, and the TTP just sends a random $g^c$ to each party. Honest parties output $g^c$ (and use it as a session key), and the adversary outputs anything they like.

Let me try to build a simulator. Specifically, in the ideal world, assume $B$ is the adversary. The simulator $S$ would receive $g^c$ from the TTP. What would $S$ forward to $A$? Without, e.g., commitment and ZK proof or random oracles how can $S$ know/extract $B$'s input $b$. $S$ has to send some $g^{a'}$ to $B$ such that $B$ can output $g^c=(g^{a'})^b$. That seems difficult.

If parties would first commit to their shares, things would be easy...


texts: What are the properties of error vector used in symmetric McEliece cryptosystem?

texts: In the symmetric version of McEliece cryptosystem, we are adding intentional error vector during encryption. During decryption, first, we cancel the effect of error vector and then multiply the obtained term with the inverse of G matrix to retrieve the plaintext. In some papers, it is mentioned that weight of error vector has to be half of codeword length. So in this case, what is the relation between the error correcting capability of code used and weight of intentional error vector?


texts: Does key renewal increase complexity of MAC forgery?

texts:
Suppose I have encrypted messages sent to a device authenticated with a MAC keyed with a strong shared cryptographic key. This device can only process so many messages per unit of time. This cryptographic key is renewed every few seconds: a new key is independently created and the previously one is destroyed.

Does this actually have any effect on the difficulty of an attacker to forge a message with a valid MAC? I originally thought it did since any computational effort spent for a key would be wasted once the key is renewed, but it occurred to me that it's not really possible to attack a MAC in a structured way (otherwise it would be broken); tags are just tried at random until a valid one is found, independently of the key.

Am I right in saying that constantly changing the key does not help with increasing the strength of a MAC? If not, can I shorten the MAC for these messages and achieve equivalent security against forgery to a larger MAC length due to the use of short-lived keys?


texts:
"Create a random key for CCPA2 scheme, encrypt m, send it along with a
  PK encryption of the symmetric key. "

Say in the process, the KDF is HMAC, then:

get a random key (128-bit)
C1 = encrypt the message "Hello World" using AES
C2 = is a tuple of E_pk(random_key), and HMAC(random_key, random_key2)

then send C1 || C2?

I have a feeling this is the wrong interpretation. Somewhere doesn't smell right. Or is this good enough?


texts: Why is a CSR signed and which key is used for signing?

texts:
I know that a CSR includes a public key from which a signed certificate shall be generated.

But why is the CSR istself signed and which key is typically used?
For signing I need a private key, so the user of the CSR's signature must have the associated public key. But what key/pair is taken?


texts: What is the best encryption protocol to encrypt streaming video?

texts:
I am building a SoC to capture and encrypt video at once. I would like to understand what encryption protocols are available to encrypt the video stream.

The video stream will be coming from a camera sensor, like a CCD. If necessary it can be pre-processed on the SoC into a particular format (for example to compress it) before being encrypted. It can also be encrypted from its RAW format if possible. The encryption protocol should have an efficient hardware implementation that can be implemented on SoC.

The goal of this embedded system is to achieve the highest possible security by reducing potential hardware or software attacks on the Soc that might expose the clear video stream to the attacker.

Note that this is a self contained chip, and the video data will not be sent over WiFi or network. It stays inside the chip.


texts: Necessity of Randomness when Privately Computing a Sum

texts:
I want to show that no 1-private deterministic protocol exists for calculating a sum of $n \geq 3$ parties (within the realms of Perfect rather than Computational Security). I'm having trouble showing that as I have to show that for any protocol, meaning I've no idea what messages are being sent.

I thought about showing privacy violation by showing that knowing the sum, a party may gain information about others, but obviously a Simulator could do that as well.


texts:
My question is regarding the coupling of the Thorp-Shuffle, as described in Morris/Rogaway/Stegers, Thorp-Shuffle Encryption. On pages 7 to 9, they describe and implement a coupling. It's all fairly elementary up until equation (5), where they show that the coupling time $T$ satisfies $P(T > 2n-1) \le p$, where $p = nl2^{2-n}$ (top of page 9). To do this, they say the following.

  Let $A$ be the event that at some time in $\{n-1,n,...,2n-2\}$ the card $z_{l+1}$ is adjacent* to some card of smaller index in the $Y$ or $Z$ process**. Unless $A$ occurs, coupling occurs by time $2n-1$.

*By "adjacent", they mean that, as bit strings, all but their first (leftmost) bit agree, ie $x$ is adjacent to $x + N/2 \text{ mod } N$, where $N = 2^n$. (See 2/3rds of the way down page 7.) **When they say $Y$ or $Z$, $Y$ hasn't been defined; I assume they mean $X$ and $U$? However, by definition of the coupling, the positions of cards $z_1, ..., z_l$ are the same in $X$ and $U$.

Now, my question is this: how can we deduce if coupling has not occurred by time $2n-1$ then $A$ has occurred, ie unless $A$ occurs then coupling occurs by time $2n-1$? I don't see why coupling means that the cards can't be adjacent.

If anyone has any better tags, please do add away! I wanted to tag thorp, mixing, total variation or coupling, but none of these exist -- even Markov chain doesn't!


texts:
NSA's Suite B Cryptography suggests some cryptographic algorithms for encryption, digital signatures, message digests and key agreements. The selected algorithms and their key size are suggested by the security level needed.

But is there any reason to think that the NSA suggests those algorithms because they know backdoors or something like that? Is it really secure to rely on those algorithms? Or should one assume that the NSA just suggests these algorithms in order to make people use algorithms with backdoors?


texts: Malicious party security model: When one party is corrupted at a time

texts:
Consider we have three parties,namely client $A$, client $B$ and a server. Client $B$ and the server can be malicious, but we do not allow the adversary to simultaneously corrupt the server and  client $B$ (similar to [1]).
The scenario is that both clients outsource their private data to the server. Then they ask the server to do computation and send back the result and a proof of computation correctness to client B.  I have designed a protocol that satisfy the above properties but the malicious server may send an incomplete result. This can be detected by client B but after that if client $B$ proceeds it can learn client $A$'s data (and this is not desirable).

Question: Based on the above security model, is client $B$ allowed to take further action to figure out the other client's data, after it detects the server's malicious behavior?

Edit: TBN: The outsourced data is not leaked to the malicious server.

[1]. http://research.microsoft.com/pubs/194141/sapsi2.pdf


texts: What is the new attack on OCB2 and how does it work?

texts:
OCB2 is proposed by Rogaway, Efficient Instantiations of Tweakable Blockciphers and Refinements to Modes OCB and PMAC
, and it is standardized in ISO/IEC 19772:2009. The author also provided a proof by security reductions, that is, a break of OCB2 implies the break of the underlying block cipher.

However, Akiko Inoue and Kazuhiko Minematsu describe practical forgery attacks against OCB2.

How does the attack work (on a high level)?
Why did the proof by security reduction fail?
What are the implications?


texts: How hard is it to find plaintexts whose hashes satisfy $h(a)\oplus h(b)=h(c)$?

texts:
Given a cryptographic hash function $h$, for example SHA256, how hard is it to find plaintexts $a,b,c$ such that
$$h(a)\oplus h(b)=h(c) \text?$$


texts:
I'm pretty familiar with using ssh-keygen to create groups that go in the /etc/ssh/moduli file for the Diffie-Hellman Group Exchange in openssh.  Reading over the man page, it says "By default, each candidate will be subjected to 100 primality tests. This may be overridden using the -a option."  I'm making an educated guess that the tests being performed are some non-deterministic test for primality (Miller–Rabin?), although the man page doesn't seem to say.  Experimenting with that -a option shows that 4 is the lowest that ssh-keygen will accept as an argument for -a.

what I'm wondering what the chances are of getting a composite number (or a non-safe prime number, or some other problematic situation) with values like 4 or 100 for -a?  Is this on the order of a 1 in 100 risk, or 1 in a million risk?

Thank you.


texts: What happens when i sign a public key with its private key pair?

texts:
I am not a cryptologist, just a cryptography user, so not sure if this is safe.

I want to sign a public key with its private key pair. Is it dangerous to share this signature result along with public key? (For example can this be used to reverse engineer the private key) Or are there anything I should be concerned about?


texts:
I am writing my Bachelor thesis on topic "Current state of stream ciphers". So my questions is: Which stream ciphers are used the most. So far I have A5 family, RC4, E0 (Bluetooth), Snow 3G and ZUC (5G), Salsa20 family (Chacha20) and block ciphers in some operation modes (OFB, CTR).
I am missing whole lightweight cryptography - Ciphers like Grain, Mickey, Trivium (eSTREAM project), but are those really currently used anywhere? What about IP telephony? I read some articles about RC4 used in VoIP but are there any new ciphers?
The best thing for my thesis would be to find some new stream ciphers (let's say >2015) which are used in the real environment.


texts: How can we determine if two discrete logarithms are equal?

texts: Let $p$ be a prime number, and let $g_{1},g_{2},...,g_{n}$ be $n$ generator of $Z^{*}_{p}$. We have a list $y_{1},y_{2},\dotsc,y_{n}$ of elements in $Z^{*}_{p}$  such that for every $i\in \lbrace1,2,\dotsc,n \rbrace$ we have $y_{i}=g_{i}^{x_{i}} \bmod p$ for some number $x_{i}$ (but we don't know $x_{i}$). I am trying to find an algorithm to determine all pairs $(y_{i},y_{j})$, $i\neq j$ such that $x_{i}=x_{j}$.


texts:
I'm trying to find a collision for the following (modified) Merkle–Damgård hash function.

  Suppose we already have a hash function $h : \mathbb{Z}_2^{2·n} \to \mathbb{Z}_2^n$ for fixed length bit strings, with $h(0\ldots 0)= 0\ldots 0$.

  The input $x$ (bit string, variable size) is divided into blocks $x_j$ of $n$ bit each, padding the last block with zeroes if necessary:
  $$
\overbrace{x_0}^{n \text{ bit}}|| \overbrace{x_1}^{n \text{ bit}}|| \ldots|| \overbrace{x_{i-2}}^{n \text{ bit}}||\overbrace{x_{i-1}|| 0\ldots 0}^{n \text{ bit}}
$$

  We add another block $x_{i}$ of $n$ bit, containing the binary representation of $|x|$ (length of x), resulting in:

  $$
\overbrace{x_0}^{n \text{ bit}}||\overbrace{x_1}^{n \text{ bit}}||\ldots||\overbrace{x_{i-2}}^{n \text{ bit}}||\overbrace{x_{i-1} 0\ldots 0}^{n \text{ bit}}||\overbrace{|x|}^{n \text{ bit}}
$$

  Therefore we have $i+1$ blocks of $n$ bit each. For $0\leq j\leq i$, refer to the $j$th block as $b_j$.
  Define $y_0 := 0\ldots 0||b_0$ and $y_j := h(y_{j-1})||b_j$ for $1\leq j\leq i$
  ($0\ldots 0||b_0$ and respectively $h(y_{j-1})||b_j$ means concatenating everything together).

  The hash function $h^*$ is then defined as
  $$h^*(x) := h(y_i)$$

How can one find a collision for $h^*$ without having one for $h$?


texts:
Can I encrypt data with multiple keys and decrypt with one? To be clear, I am not saying encrypt a file, decrypt it, then encrypt it again with a different key. I want to encrypt it, then encrypt it again, then again, maybe even again. I want to know whether I can use only one key to decrypt. The key can change though, it doesn't have to be the same key (in fact it shouldn't be).

I need a smart way to update the key to the new key, depending on how many times the data was encrypted. Also, the only way to get the new key is to have the old key... Is this possible? Is there an encryption algorithm that can be stacked multiple times and be decrypted by one key (and can I create that key)? Either this can already be done, or I am crazy--remember, I'm new to this...

Previously handled comments on StackOverflow:

  "What's the point of encrypting multiple times? Properly encrypted data is indistinguishable from random noise."

I'm not trying to make it more secure by doing this...

  "Do you want to perform E(k_n, msg) once with one of many possible keys then E(k_d,ciphertext) to get the ciphertext? Or do you want to perform E(k_1, E(k2, ... E(k_n,msg) ... ) ) as the encryption?

The latter, except I don't want to do encrypt with all keys all at once. I want E(k_1, msg) ... some time ... E(k_2, encrypted_msg) ... and so on, but I want to know if I can decrypt with one key after however many encryptions (and how to get that key).

  "Consider: 'I really want a smart way to update the key to the new key'."

Yes. And, of course, the encrypted file will change during the process.


texts: RSA Encryption Time with Different Block Sizes

texts:
I was working on encrypting a few files on my computer and I was using OAEP for padding with RSA. I noticed that it was taking a long time to encrypt some of my files with a small block size, so I tried to encrypt the same files with a much larger block size and it finished encrypting incredibly fast. I was thinking that the number of encryption cycles since there were so many blocks and/or the amount of padding used could be the reasons why it was so much lower when I tried to encrypt the files with small block sizes. Does the number of encryption cycles and/or amount of padding used from smaller block sizes compared to large block sizes impact the time. If so, why is this? If there are other reasons too as to why RSA with OAEP encrypts files much faster with larger block sizes compared to smaller block sizes, I would love to learn more about that!

Disclaimer: I completely understand that RSA is NOT meant for file encryption, I am just trying stuff.

Thank you in advance for any logic behind this that you can provide.


texts: Key exchange and authentication using libhydrogen

texts:
I have been able to exchange session keys on two devices using Libhydrogen's Key exchange using the N variant method. I also want to authenticate both devices to have some protection against the Man in the middle attack. Can I use libhydrogen's Public key signatures method for that? If yes, how to use it with key exchange?

Q 1: This method generates a key pair for signing. Should I first transfer the public key of the server to the client? The client can then sign the session key and send it back to the server for verification? Would this work?

Q 2: Should the I use libhydrogen's signature method for authentication before the key exchange or after?

Any help would be appreciated.


texts:
Recent news articles have suggested that the NSA may be involved in trying to influence the cryptography in public standards or commercially deployed software, to enable the NSA to decrypt the encrypted traffic.  For example, see this article in the New York Times.

The New York Times article specifically mentions a 2006 NIST standard, where two Microsoft engineers later discovered a serious problem in the scheme.  The New York Times article explains how the standard was written by the NSA, who pushed the scheme hard:

  Simultaneously, the N.S.A. has been deliberately weakening the international encryption standards adopted by developers. One goal in the agency’s 2013 budget request was to “influence policies, standards and specifications for commercial public key technologies,” the most common encryption method.

  Cryptographers have long suspected that the agency planted vulnerabilities in a standard adopted in 2006 by the National Institute of Standards and Technology, the United States’ encryption standards body, and later by the International Organization for Standardization, which has 163 countries as members.

  Classified N.S.A. memos appear to confirm that the fatal weakness, discovered by two Microsoft cryptographers in 2007, was engineered by the agency. The N.S.A. wrote the standard and aggressively pushed it on the international group, privately calling the effort “a challenge in finesse.”

After some sleuthing, I'm pretty certain this is a reference to the Dual_EC_DRBG pseudorandom number generator scheme described in NIST SP 800-90.  The weakness is that Dual_EC_DRBG appears to contain a backdoor, and anyone who knows the backdoor can totally break the PRNG.  The weakness was first described in a rump session talk at CRYPTO 2007 and was subsequently discussed by Bruce Schneier in Wired.

As a consequence, there are now good reasons to suspect that Dual_EC_DRBG contains a NSA backdoor, and the NSA might be able to spy on anyone who is using Dual_EC_DRBG.

My questions:

Who uses Dual_EC_DRBG?
Do any commercial products use Dual_EC_DRBG?
Does anyone use it?


texts: Implementation of MiMC over Edward curve

texts:
I'm trying to use MiMC-hash function [1] over Edwards curve, in order acheive an hash function that output a point on Edwards curve.

However, in Section 5.1 ([1]), they state that $gcd(3,p-1)=1$, which is not valid the value $l$ (the order of the base point).

Is there any trick that I can use to achieve that?
(I was thinking about working on smaller field, but I struggle to put the result on the correct point on the elliptic curve).

Thanks.

[1] - https://eprint.iacr.org/2016/492.pdf


texts: Using multiple cryptographic keys for encryption?

texts:
I am setting up an encryption methodology for items in a database. To decrease the likelihood of data being compromised due to the keys being compromised I would like to use an application level key (stored outside the database on a different server), a database level key (stored in a table away from data), and a data level key (stored inline with the data).

All of the keys are all AES256, encrypted at rest, and generated in a cryptographically sound way; they require a key management service to generate them and decrypt them. I have two methodologies in mind.

Gather and decrypt the keys at the same time, and immediately hash them together with some data context that describes the data to make a new single 256bit encryption key specific to that data. Then immediately delete them from memory; the hash remains in memory long enough to perform a single encryption/decryption, but is eventually deleted and never stored to disk. If it is compromised in memory, only the data it matches could be compromised.
Keep all the keys in memory long enough to successively encrypt/decrypt with each key. This runs the higher risk of the decrypted keys being individually compromised since they are in memory longer, but it seems like since entropy is added on each encryption step, it’s probably a stronger encryption in the end. Certainly the number of stored bytes increases (partially because of storing initialization vectors).

Is one method more secure/standard? Is there a more standard way of achieving what I’m trying to do? References would be great.


texts: Selection of parameters for Massey-Omura Cryptosystem

texts:
I have 4 questions about Massey-Omura Cryptosystem.

Are there standards that define these parameters?
How to choose a group order?
What is better to take the function f?
What is the recommended key length?


texts: From the product of two permutation matrices raised to the same power, is it easy to find the power?

texts:
Let $A$ and $B$ be two public permutation matrices.
If $r$ is a secret power of large number, can we easily find $r$ from $A^rB^r$?


texts: Signing files with some kind of "inheritance"

texts:
I'd like to design a system where the following situation happens:

I (person 1) have some secret key
I hand out another secret key to a developer (person 2)
Person 2 signs several files with his secret key
Person 2 can now distribute his software among with mine to the users.
In my software I'd like to be able to check if the digital signature is valid.

I'd like to check if the digital signature with the code person 2 made is valid.

Person 2 could distribute the public key among with his files, so I could check it, but that would be way too prone to attacks which could replace the public key and resign the file.

Also, there would be multiple developers with their own different secret keys. I wouldn't like to embed every single public key into my software, the best would be if I could create some kind of "SUPER KEY", or I don't know how to describe.

Obviously I'm willing to make compromises if the given solution doesn't match my previously described workflow, but achieves the same thing.

I'm curious if there's some already existing cryptographic algorithm which would suit my needs.
I was thinking of some RSA-related things, but according to my very limited knowledge, it's not really possible without embedding all the keys.


texts:
Say I want to encrypt short messages via radio to a friend. Would a series of key streams based on 36 characters (alphanumerics) generated by a CSPRNG like CryptGenRand and applied to the plain text provide adequate unpredictability? As with a OTP, each message would use a different stream.
My (limited) understanding here is that because the computer that generates the key stream is independent of the transmission method (radio) that attackers would either 1) have additional problems of identifying who I am, what computer I used, when I used it and gain access to this computer to get my key stream, or 2) have to crack the CSPRNG (possible, considering: http://eprint.iacr.org/2007/419.pdf).

Amplification: to answer some questions. Yes, it'd be Windows' CryptGenRandom (sorry, was a little off on the class name), probably by using SecureRandom class in Java. The output key streams would be generated on one pc, then shared via removable media. The actual encryption/decryption would be simple transposition using the key stream, and would be automated with a small app.


texts: Is there a simplified article, video, or blog about bulletproofs?

texts:
I'm trying to learn about bulletproofs for my master "Enhancing Privacy in E-voting Systems", but the original paper was too hard for me. I also tried to look at this, but it was also too difficult. So, is there and article or a video or blog that explains bulletproofs on a beginner's level?

edit: i found this it is easy relatively and start from the basics


texts: Risks using .NET RijndaelManaged with static Key and IV

texts:
A company I'm consulting for has a (quite old) home grown web SSO solution based on an encrypted cookie. The auth flow looks more or less like this:

User hits protected page on integrated site
Site redirects to central logon site
User authenticates and gets sent back to originating site with an encrypted cookie containing username and various other bits regarding their authorizations
Integrated site then makes authentication/authorization decisions based on the cookie data

Apps that are integrating with this SSO system are given a "special" decryption library for their platform that knows how to decrypt the SSO cookie. Special in this case simply means they don't make it publicly available, but it's the same library for everyone (per platform).

Out of curiosity, I decided to look into the implementation details of the decryption library. At the core, it's using RijndaelManaged from .NET. However, it has hard coded values for things that seem like they shouldn't be hard coded from my admittedly limited understanding. I'm wondering if they ultimately have an exploitable vulnerability such that knowing the decryption details could hypothetically allow an attacker to craft a valid cookie to impersonate someone else.

The parameters they're using to initialize the RijndaelManaged class are:

Hard coded 128 bit Key
Hard coded 128 bit IV set to all 0's
PKCS7 padding
CBC cipher mode

The library also includes an RSA public key used to verify an MD5 signature appended to the encrypted cookie.

EDIT: After further thinking, I believe my initial fear about how Rijndael was used is only a problem without the appended signature. While (I think) you can generate modified and valid cipher text using the Rijndael details, you won't be able to create a valid signature without the private key associated with that RSA public key. Is that right?


texts: Compact ROM with space only for EdDSA. How to fit a key exchange algorithm inside?

texts:
I have implemented Ed25519 for a constrained-memory system, and I want to provide a Shared Secret functionality. The recommended method is to use X25519 for this; but then I would have to implement point multiplication over the Montgomery curve Curve25519, which I don't really have room for.
Would there be any downside to using Ed25519 directly for this? In other words, if PrK is my private key and PuK is your public key, our shared secret is [PrK]PuK computed over the curve Ed25519, and not the curve Curve25519. Perhaps then I could hash the result, as Bernstein recommends for X25519.
I am aware of two possible issues: firstly, Curve25519 is slightly faster here; but this is not a serious problem in my application. Secondly, such a custom algorithm is not recommended by any standard; this is a more serious problem, but I can live with it. Does anybody know of any more potential problems with this approach?


texts: How to collect, process, and transmit data securely?

texts:
In my question "Authenticating data generated by a particular build of an open source program", Dave Cary requested that I post a question stating my real problem on a high level rather than the partial solution and abstract approach I took. So here goes:

Need to develop a program that collects raw scores at a competition, compute the winning scores for that competition, and save that results so that it can be transmitted to a server for display and validation. The results must be in some human readable form (preferably XML). There must be some way to trace what version of a program generated a set of results. There must be complete transparency in the program in terms of how the winning scores are processed and computed. The server will only accept correctly computed results.. The server should be able to distinguish between results computed by an official build of the program versus a wildcat build. The machines running the program are essentially offline. Not all machines will be updated with new versions at the same time.


texts: Why didn't people redesign the key scheduling algorithm of DES to use longer keys instead of using 3-DES?

texts: To overcome short key length of DES, Triple DES was devised. What would go wrong or why didn't people redesign the key scheduling algorithm to use longer keys?


texts: Why are the first 4-6 characters from ssh-keygen (RSA) the same everytime?

texts:
New to StackExchange, so please bear with the newbie.

At my current job we are often creating many ssh keys with ssh-keygen (RSA). One thing I have noticed is that the first few characters (say the first 5 or so) of the private key are consistently the same. These are all created on the same computer. Is this to be expected? I am just curious why this would be the case.


texts: Can I use Salsa20 as a good non-cryptographic PRNG with different streams if I reduce the number of rounds to 8 and omit the addition step at the end? I want to omit the final step because I don't want to get all zero outputs.


texts: Finding a hash function that calculates average of an item in a stream of tuples

texts:
So, I have a stream of tuples coming in for example [country, state, person], where state and person are unique items.
Now I have to find :
1. for  each country, I have to estimate average number of persons in a state.
How do I design a sketch that uses a hash function that does this with a minimum memory storage.


texts: Is it possible to weaken a bitcoin private key by “using” it elsewhere?

texts:
What are the increased possibilities (if any) of being able to crack a private key given the following:

The associated bitcoin (ECDSA Secp256k1-based) public key is known.
The private key has been used to generate a public key from a different ECDSA curve and that public key is also known.
It is known that the two public keys are derived from the same private key.
It is known which ECDSA curves were used to generate the public keys.
It is known which ECDSA curve was used to generate which public key.

Does it make any more difference if there is data that is known to have been signed by the private key and the signature(s) are known and the raw data is known?

EDIT: I should have pointed out that the conditions are ANDed, I.e. All conditions are known. Sorry, I should have been clearer the first time.


texts:
Assumptions

Let's theoretically assume that a browser skips the check that a certificate it receives belongs to the stated CA (that's an exercise).

How could I exploit this in order to impersonate to a server?
In other words, if some client requests site A, and I have MitM capabilities, can I redirect the user to my evil site?

My idea

I thought about forging a certificate for my evil site, and then sign the forged certificate with another forged one of a CA that I also forge, which signs the initial certificate for me (in other words: I sign for myself).

In the forged cert, I'd state that I am site A, attach my public key and in then (hash and) sign the cert with my own made up sign key $K_s$ (let's say RSA but it doesnt actually matter).

Now I'd put $K_v$ which is the public validation key as the public key of the CA cert I forge, and attach this CA cert to the server cert.

Now, when the user requests site A, I return him my evil site with the two certs I fogred.

The browser then skips the CA check and just validates the signature with the previous CA cert public key (extracting the hash and then comparing the hashes), and it's OK.
I also assume here that the Trust Anchor check is also skipped, thanks to the base assumption.

Is my idea correct?


texts: Can I measure entropy through compression only?

texts: Say I have a file containing words from the English language.  Not meaningful text, just a repetition of a few words.  The original size is 1559454 bytes and it is compressed by a certain program to 75742 bytes.  (A very good compressor, it seems.)  Can I estimate the entropy of the source producing such file using essentially the byte reduction?


texts: How to provide secure password based encryption with password reset option

texts:
I am trying to build website that will encrypt some data for the user using his/her the output of scrypt on it, now the idea is that this schema is not flexible because if the user loose their password then all of their data is lost, instead came to following options:
Option 1 :

Generate random 128 bit key $k_1$

Generate random 128 bit recovery key $k_2$

Run scrypt on user password to get $k_3$

Give $k_2$ to user to save it in secure place and not save it in database

Encrypt $k_1$ once with $k_2$ and once with $k_3$ and once with $k_2$ and store them in database

When user forget their password he/she uses $k_2$ to decrypt the encryption key $k_1$ and then go to step 2.

Option 2:

Generate random 128 bit key $k_1$

Generate random 128 bit recovery key $k_2$

Use scrypt on user password to derive $k_3$

$k_4 = k_1 \oplus k_2$

$k_5 = k_1 \oplus k_3$

To encrypt we use the $k_1 = k_4 \oplus k_5$

Give $k_2$ to user to save it in secure place and not store it in database

When a user forgets their password he/she provides the system with $k_2$, then $k_1 = k_3 \oplus k_2$, go to step 2

Option 3:

Use scrypt on user given password, this will be $k_1$

Generate random 128 bit key for encryption $k_2$

Encrypt $k_2$ with $k_1$

Use Shamir shared secret with number of shares is $2$ and threshold is $2$ and the secret is $k_1$

Store share in database $s_1$, and give the other $s_2$ to the user to save it in secure place.

When a user forgets their password she/he will provide the system with his/her sahmir shared $s_2$, and using shamir secret sharing algorithm and the $s_1$ we obtain $k_1$ and then go to step 1.

Now my exact question is: What is the pro and cons for option 1, option 2 and option 3? Which one will be the most secure one? And which one will be the best from a performance perspective?


texts: Strictly, is length(key) >= length(message) wrong for one time pads?

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

entropy(key) >= entropy(message)?

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

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

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

Am I wrong/confused/hungry?


texts:
hashing some data and encrypting data share some similar attributes. Surely this is why "Difference between encrypting something and hashing something" has been asked.
The point of this question is hence not repeating the different purposes. Instead I would like to ask.
Since hashing does not, by intention provide a way back I was wondering if there would be a possibility enhance a hashing scheme as to allow a way to revert the data.
To keep this a concrete and less abstract question assume this case.

Let there be data and a key provided initially (which I agree is already some derivation to hashing in which there is only data)
Then let the key serve as the initial input to a perform a hashing operation. For instance this could be a SHA256(key)
Let step 2 be continuously repeated using the result of the previous step as new input. (So essentially this would be a SHA256(SHA256(key)) as the result of the second round). The results of each round are collected until it reaches the length of data.
Finally let the data be XOR'ed with this "hash-generated one-time-pad"

Now to reverse the steps 1 to 3 can also be used to reverse again from the ciphertext to the plaintext data.
In this concrete example it seems that somehow hashing has essentially become encryption. The question therefore is this: Can this be?, is the scheme presented above an encryption scheme mainly consisting of a hashing function?
Addition
would the hash be a cryptographic safe pseudo-random-number-generator (CSPRNG) and hence this hash be part of a stream cipher setup?
Or:
Can a hash become a CSPRNG (and this would be then a stream cipher)?
Update
With happiness I have read all and even accepted one answer with thanks. Yet I want to stress that the questions focus was less
"Is this suggested algorithm a safe encryption scheme" (it is not in particular the question of safety), Instead it was about logical connectedness/links between what can be understood as encryption and which is understood as hashing
Given that for instance both hashing and encryption often attempt to produce a pseudo-random deterministic outcome. I think the question hence "can hashing become encryption?" is answered well, as it seems in some respects there is chance to use mainly a hash and end up at least with a weak encryption. Maybe the only think yet still missing (because much of some answer's efforts focus on the safety of the example algorithm) is maybe.
(1) If all encryption can be seen as hashing?
and be
(2) all encryption bases on hashing? (which I do not think)
Yet the question is already answered very nicely so any addition focusing on that aspects (instead of the safety of the algorithm - which was simple to be more concrete) would be nice.


texts: Scrypt cipher - known vulnerabilities and cryptanalysis?

texts:
there is a Scrypt cipher which is used for exmaple by some cryptos like LItecoin for their mining algorithm.

I never heared of scrypt. I know eg SHA256 which is well analyzed and considered as secure until now.

1) ANy known crypatanalysis for scrypt / vulnerabilities?

2) is scrypt considered in the community as a secure (comparable to sha256) cipher?

3) How collision-resistant is it?

4) Is it easily breakable by quantum computing attacks?

Thanks


texts: Concatenation of multiple shorter hashes vs a single long hash

texts:
I permanently need to hash lots of data quickly, but the result only needs to be collision resistant.

Is there any negative side-effect of using multiple (say 2) algorithms providing a shorter digest (e.g. RIPE-MD-128 and Tiger128) versus using an algorithm providing a digest of the added length (e.g. SHA256).

I want to explicitly highlight that I only need high performance and collision resistance. Other properties (avalanching, etc.) are irrelevant, I do not even care if it is possible to go back from digest to input. So I do not even need to really use "cryptographic" hashing algorithms (CRC32 is perfectly fine here I guess).

More specifically my idea is to use multiple REALLY FAST algorithms (clhash performing at over 4 gigabyte per second on my testsetup, xxhash performing at over 6GB/s, ...) and simply concatenate them to improve collision resistance:
$$
Digest(Input) = XXH64(input)\ |\ CLhash(input)\ |\ CRC32(input)\ |\ Farsh(input)
$$

This results in a digest with $64+64+32+32=192$ bits length, but is faster than an algorithms providing a digest with 192 bits. The important question for me is: is the collision resistance comparable to an algorithm providing 192 bits?

I benchmarked a lot of different hashing algorithms and the fastest performing hash, that is also reviewed and provides a long digest (which can be an indicator of better collision resistance), is Blake2b performing slightly above 1500 megabytes per second and provides a 512 bit digest. A combination of different algorithms would be even faster, and for my use case performance is key.


texts: Hash function and Digital Encryption Algorithm

texts:
I am familiar with the fundamentals of cryptography as well as Digital Signatures. I understand how DSA like RSA works and the fundamentals of mathematics behind digital signing and verification. I also have a reasonable understanding of how bitcoin works. However I can not understand the role of hash function (SHA-256) in bitcoin blockchain.

The role of a private key and its corresponding public key seems clear to me.

A public key can be used by the sender of a message to encrypt the message than can only be decrypted with the private key of the recipient.
A private key can be use to sign a message, so when the message is encrypted with the private key the recipient can verify, by using the public key, that the message must have been signed by the owner of the private key.

The questions rises is bitcoin protocol.
I understand that the public key is use to derive the bitcoin address. Therefore, having the private key associated to that address allows you to prove that you are the owner of that address.

The hash function (SHA-256) is used to make the digest of the of the transaction and block in the block chain. Somewhere I read that “To save time, digital signature protocols are often implemented with one-way hash functions (...). Instead of signing a document, Alice signs the hash of the document.”

I've got three related questions:

Is that the only role of the hash function in the bitcoin protocol?
What is the role of the hash function in the verification of the ownership of the address?
Couldn’t we get the same result of proving ownership without the hash function?


texts:
If I XOR the output from 2 CSPRNG will the result be better (more random) than the output from either one?
Assume one of the PRNG is biased.


texts:
Design of efficient of block ciphers needs consideration of many factors such as register size. i found that some ciphers can be SIMD implemented such as TWINE , SM4 , chacha20 ,SPIX ,and others.

What components in block (Feistel and SPN) and stream ciphers are tricky to be implemented in vectorizations?
Does the Sbox size (4 bit or 8 bit) or the F-function structure (such as simon-like Sbox in SPIX or SP/SPS such as in Clefia or piccolo) matter ?
Does  the  branch number in Feistel Type (2,4,6,8 ..) have related in number of blocks to be packed for vectorization?


texts:
Wikipedia claims that the best attack on the surprisingly simple TEA block cipher, that isn't a related-key attack, has a time complexity of $2^{121.5}$.

So despite how unsophisticated the cipher looks, if I use a KDF properly and don't use related keys, TEA is secure?


texts: What do you mean by Ciphertext indistinguishability

texts:
Wiki definition :

  A cryptosystem is considered secure in terms of indistinguishability
  if no adversary, given an encryption of a message randomly chosen from
  a two-element message space determined by the adversary, can identify
  the message choice with probability significantly better than that of
  random guessing (1⁄2). If any adversary can succeed in distinguishing
  the chosen ciphertext with a probability significantly greater than
  1⁄2, then this adversary is considered to have an "advantage" in
  distinguishing the ciphertext, and the scheme is not considered secure
  in terms of indistinguishability. This definition encompasses the
  notion that in a secure scheme, the adversary should learn no
  information from seeing a ciphertext. Therefore, the adversary should
  be able to do no better than if it guessed randomly.

I understood the meaning of this but what do you mean by Indistinguishability under chosen-plaintext attack and Indistinguishability under chosen ciphertext attack ? Could anyone give me an example, and answer in easy understanding language.


texts: Why in RSA do we use mod n rather than mod phi(p⋅q)?

texts:
When we pick $e$: $$e \in \{1,2,3,4,...,\phi(p\cdot q)-1\}$$
where $\gcd(e,\phi(p\cdot q))=1$. Similarly when computing $d$ which is the modular inverse of $e$ (the private key) we use the extended Euclidean algorithm as
$$\operatorname{EA}(e, \phi(p\cdot q))$$
so that $$e\cdot d \ \equiv \ 1\pmod{\phi(p\cdot q)}$$
So having a message $X$ why does simultaneously encrypting and decrypting message as
$$ {(X^e)}^d \equiv  X \pmod{\phi(p\cdot q)}$$
not work, as it should be equivalent to $X^{e\cdot d}$ and $e\cdot d$ are the inverse of each other in the set of  $\{1,2,3,4,...,\phi(p\cdot q)-1\}$ so they are supposed to cancel each other which is supposed to be the idea of RSA.
I know that $e\cdot d$ result in plaintext to be decrypted to 0.00 if I follow the normal encryption/decryption process (since I tried it)
Can anyone explain why it does not work as described?


texts:
Leonid Levin constructed a universal one-way function, i.e. a function $f$ such that if any one-way functions exist, then $f$ is a one-way function.  My question is, what universal pseudorandom generators or pseudorandom functions have been constructed?  That is, a function $G$ such that if any pseudorandom generators exist, then $G$ is a pseudorandom generator.  Or a function $F$ such that if any pseudorandom functions exist, then $F$ is a pseudorandom function.
Now one method would be to start with Levin’s construction of a universal one-way function and then build a PRG/PRF out of that.  But the construction of PRG’s and PRF’s from one-way functions is fairly complex.  Is direct construction of a universal PRG or universal PRF?


texts: How does tls 1.3 cope with man in the middle (in key exchange)

texts:
in case i cannot do PSK (give the same key to both sides via physical means).
i saw tls1.3 still support DH (doesnt matter that it is DHE or ECDH).
isnt that makes it a weak key exchange?
do they rely on seperate key exchange algo.? (like PAK - x.1035)


texts: Is there any Information on the "Modular Approximate Greatest Divisor" problem?

texts:
The Approximate Greatest Common Divisor (AGCD) problem is the difficulty of obtaining the value $\ p\ $ when given samples of $\ pq_i + e_i$ for secret values $p, q_i, e_i$.

I would like to know how the difficulty of the problem changes when modular reduction is incorporated.

Specifically: is the problem of obtaining $\ p\ $ from samples of $\ pq_i + e_i \bmod x$ with secret $\ p, q_i, e_i$ and public $x$ equivalent in hardness to the previously mentioned variant of the problem that operates over integers?

I could not find information on this version of the problem when searching for the term "Modular AGCD", but I am not sure what to refer to it as. It may a negligible difference between the two that does not warrant classification as a separate problem, but I am not sure. Intuitively, it seems that the variant with the modulus would be more difficult to solve. But I would like quantitative details on any differences, if there are any.

Edit

Poncho's answer highlights the fact that the sizes of the parameters are important when discussing the hardness of the problem. I am interested in the problem with the following parameter sizes:

$x$ is a 1792-bit prime
$p$ is a uniformly random 1792-bit integer
Each $q_i$ is a 1536-bit integer with the 1280 most significant bits uniformly random

The next lower 255 bits are set to 0, and the least significant bit is set to 1

Each $e_i$ is a 1024-bit random integer


texts:
I asked this question recently but I was told it is not save to simply send over the identifier for your crypto method you want to use. for example, say the server has crypto method 3 5 and 6, the client had 2, 3, and 6.

The clients sends the methods it can do and the server checks the highest possible version. A man in the middle could intercept the message from the client and only send 3, so the server would use the weakest common method. Obviously you don't want this, we want them to use 6 (the highest is the strongest in this case).

I have tried to figure out why TLS does not have this weakness (other than the FREAK bug) but somehow I can't find out why TLS does this better. So my question: How does TLS ensure the use of the best crypto method both the server and client share?

Background info

I curently have a piece of code which has a crypto layer (very old) it currently sends 00 which indicates it needs to use our old crypto method but 01 will be TLS (which I'm going to implement) However having TLS and an insecure exchange to determine the crypto method is obviously as strong as our insecure exchange. But to keep it backwards compatible we can't simply switch our old crypto method for TLS so we need to do this exchange. which is why i need to know how to do this properly.


texts:
I saw this recently published riddle and its solution in
this link.
My mathematical background is not so strong. Is it possible that someone here to solve the riddle? My background in math is not strong.
I understand that there is some problem in that they repeatedly XOR each (file_name + '\0' + file_content) with the prev. (file_name + '\0' + file_content), and only then use it for authentication against the asymmetric signature.
I understand that our goal is somehow to zeroed our added files hash by XOR with some calculated unique file names, but I do not know how to do it without weakness in the hash algorithm itself.
Please explain the solution in simplest possible way (but at the same time I want to understand exactly what the weakness here is and what exactly is the solution).


texts: Many single-time use keys encryption scheme (not Shamir's Shared Secret)

texts:
I'm looking for encryption scheme with the following properties:

There's a sequence of keys that can be used to decrypt the message
Strictly only one key from the sequence is required to decrypt the message
Keys need to be used in the order that is defined by keys sequence
Once used, the key can't be used again to decrypt the message (this implies some kind of transformation of encrypted message as part of the decription process)
It is not possible to derive keys from the sequence based on knowing any number of the keys from the sequence
The encrypted message is kept by third party (e.g. on a server), that
decrypts it for the receiver of the message on request, but only the receiver of the message keeps the sequence of the keys. In case of security breach, if the encrypted messages leak from the storage they're kept on, they're worthless for the attacker, because the third party doesn't keep the sequence of the keys. I know that it would be still possible to steal the message from primary memory when the receiver decrypts it, but the focus is on making the permanent storage of the message safe.


texts:
I have to hash a message with MD5, digitally sign it, and then verify.

I have looked around, but I can't find a step-by-step example. I understand how RSA works when a message is given as number (not hashed).
But I am confused when I have to sign a hash.

For example: $n=33, d=7, e=3$.

I have a message: Hi
I compute the MD5 hash, $H(m)$, which is c1a5298f939e87e8f962a5edfc206918.
Now I have to sign it with $S = H(m)^d \bmod n.$

I get confused here: How can I perform this $H(m)^d$?  What will the result be after that?


texts: Is it possible to construct a multiplicative group from $\mathbb{Z}_n$ if $n$ is not a prime number?

texts: With $n$ being a prime number I know we can generate groups over multiplication. Is it possible the other way around ($n$ not being a prime)?


texts: Merkle trees instead of the Sponge or the Merkle-Damgård constructions for the design of cryptorgraphic hash functions

texts:
Most modern cryptographic hash functions use some form of compression function combined with a construction such as the Merkle-Damgård (MD5, SHA1, SHA2, etc), the Sponge construction (with Keccak as a notable example) and variants of these constructions in order to allow messages of indefinite length to be processed.
It also happens that in order to exploit parallelism some hash functions have modes which make use of Merkle trees, such as the tree-hashing mode of BLAKE2 and ParallelHash (not a Merkle tree per-se but still).

To my knowledge there are multiple Merkle tree-like structures that provably reduce the security of the whole construction to the one of the underlying primitive (for example the one described in the Sakura paper and the one described in the Certificate Transparency RFC).

If I am not mistaken MD6 tried to use Merkle trees directly, however I am not aware of any other cryptographic hash function trying such a thing. Is there any reason why more cryptographic hash functions don't use a Merkle tree-like construction directly instead of just adding them as a way to allow parallelism to existing hash functions on top of the Merkle-Damgård or the Sponge construction?


texts: How many bits are needed to commit one bit non-interactively in the standard model?

texts:
I'm wondering the state-of-art result about how many bits are needed to commit a single-bit non-interactively? I noticed in the paper of Naor's bit commitment: http://www.wisdom.weizmann.ac.il/~naor/PAPERS/bit.pdf
this paper says assured amortized O(1) bits of communication per bit commitment. However, it seems Naor's bit commitment has interactive commitment phase. Thus I'm wondering the state-of-art result about this research direction. How many bits of communication per bit commitment should be sent non-interactively in the standard model?

I'm only interested in non-interactive bit commitment assuming one-way function not assuming DDH like Pedersen commitment.


texts: Why is does the protocol of Ding et al. produce biased bits and does it relate to passive security?

texts:
I am not understanding the following from "Lattice Cryptography for the Internet" by C. Peikert (pages 9):

  We remark that a work of Ding et al. DXL14 proposes a different
  reconciliation method for lower bandwidth "approximate agreement," in
  the context of a key exchange against a passive adversary. However, we
  observe that the agreed-upon bit produced by their protocol is
  necessarily biased, not uniform, so it should not be used directly as
  a secret key (and the protocol as described does not satisfy the
  standard definition of passive security for key exchange).

I don't understand the biased part and how it is related to passive security for key exchange. Maybe I just don't understand the definition of passive security for key exchange. I don't know. Any help would be appreciated.


texts: How to find $d$ with large $e$ ? If $(3\cdot d)^4 \le n$ : Wiener attacks, so what if $(3\cdot d)^4 > n$ ?


texts: Why is Ring-LWE based homomorphic encryption secure with one sample?

texts:
Suppose $R=\mathbb{Z}[X]/f(X)$ is a polynomial ring.

Decisional Ring-LWE is hard if one cannot distinguish the following samples:

$(a_i, b_i) \in R^2$ for $i\in [0,k-1]$ (completely random)
$(a_i, b_i=a_is+e_i) \in R^2$ for $i\in [0,k-1]$ ($b_i$ is obtained by multiplication of $a_i$ and secret $s$ masked by some noise)

This requires $k$ samples.
However in homomorphic encryption scheme, key generation of public key requires just one Ring-LWE sample.

Why is this secure?


texts: Is there any tool which can be used to test that implementations follow  FIPS 140-2 Compliance ?


texts: Homomorphic Encryption and the Approximate GCD Problem Confusion

texts:
Note: I asked this question on Math.StackExchange yesterday and it wasn't answered, so I thought I would repost it here, in hope of getting an answer

I am reading Homomorphic Encryption and the Approximate GCD Problem, specifically Section 3.2 on page 23, which outlines a basic encryption scheme:

  The user chooses a large odd integer $p$ to be the secret key for the system.

  A plaintext is a single bit $m$.  To encrypt a message $m\in\{0,1\}$ and obtain a ciphertext $c$, the user chooses $q,e \in\mathbb{Z}$ independently and randomly from some distribution for each encryption and computes $$E(m,p) =qp+ 2e+m$$

  The binary size of $q$ is generally chosen to be greater than the binary size of $p$. The binary size of $e$, which is referred to as the error, is much smaller than the binary size of $p$. We will discuss the exact sizes for these parameters later on.

  The decryption function for this system is given by
  $$D(c,p) = (c\mod p)\mod 2$$

  To see that the decryption function is correct for a ciphertext $c=qp+ 2e+m$, observe that
  \begin{align}D(c,p) &= (qp+ 2e+m\mod p)\mod 2
\\&= (2e+m)\mod 2\\
&=m \end{align}

  Note that for this to work we need \begin{align}2|e|+ 1&<\frac p2\\|e|&<\frac p4−\frac 12\end{align} so that $(2e+m\mod p) = 2e+m$.

However, what I am struggling with is, if we choose $e<0$ then \begin{align}2e+m\mod p &= (p-2|e|)+m\\&\neq2e+m\end{align} by the definition of modulo (at least as seen by most common programming languages):

  $a\mod b=r$ where $a=qb+r$ and $0\leq r<b$

Since $p$ is specified to be odd, then we have
\begin{align}&((p-2|e|)+m)\mod 2 \\
&=((p\mod2)-((2|e|)\mod 2))+(m\mod 2)\mod 2\\
&= ((1-0)+m)\mod2\tag{as $p$ is odd}\\
&= (1+m)\mod 2\tag{as $m$ is either $1$ or $0$}\\
&\neq m\end{align}

I'm just trying to understand why we specify $$|e|<\frac p4 - \frac 12$$ and not $$0<e<\frac p4 - \frac 12$$

as, as far as I understand, the decryption doesn't work when \begin{align}0<-e&<\frac p4 - \frac 12\\
\frac 12 - \frac p4 < e &< 0
\end{align}

  Example

  Choose $p=1583$, $q=52498$, then $|e|<\frac{1583}{4}-\frac 12 = 395.25$ so choose $e=-241$

  For $m=1$, we have \begin{align}c&=52498\times 1583+2\times (-241)+1\\
&= 83104334-482+1\\
&= 83103853\end{align}

  We decrypt this as follows \begin{align}D(c,p)&=(c\mod p)\mod 2\\
&= (83103853\mod 1583) \mod 2\\
&= 1102 \mod 2\\
&= 0\\
&\neq m=1\end{align}

  We can see that \begin{align}(c\mod p) &= 1102\\
&= (2\times 550.5) + 1\end{align} and $550.5 > 395.25$ which doesn't satisfy the constraint on $|e|$

Can someone either confirm that my logic is correct, or explain to me where it is falling apart please.


texts: Discrete logarithm hash function Exercises

texts:
I have a problem with this exercise:

Let $G$ be a group of order a prime $q$ and let $g, h$, be two randomly selected elements of $G$, with $g,h\ne 1$. Consider the following hash function on integers $x_1$ and $x_2$:
$H(x_1,x_2)=g^{x_1}h^{x_2} $
Show that the problem of finding a collision pair $(x_1',x_2')$ such that $H(x_1, x_2) =H(x_1',x_2')$ is equivalent to finding the discrete logarithm of $h$ with respect to the base $g$ (or viceversa, of $g$ w.r.t. the base $h$).

I thought I could do this to solve the problem:
$log_g(h)=x$ then $h=g^x$
If $H(x_1,x_2)=g^{x_1}h^{x_2} $ then I can write:
$H(x_1,x_2)=g^{x_1}{(g^{x})}^{x_2}=g^{x_1}g^{xx_2}=g^{x_1+xx_2}$
With $x$ fixed, it is simple to find a pair of $(x_1',x'_2)$ such that $x_1'+xx_2'=x_1+xx_2$ and then a collision.
Can you tell me whether this logic works? Do you know if there are easier ways to solve it?


texts: Why does Apple create a certificate for my push notification key

texts:
Brief rundown of how Apple Push Notifications (APN) work:

Generate a keypair, generate a CSR for it
Upload the latter to your Apple Developer account and associate it with your mobile app
In the process, your CSR is signed and you get to download the certificate
Connect to the APN server using the key + certificate, send your notifications

Note that this is a separate key/certificate just for push notifications. It is distinct from the code signing key, and not used anywhere else. And, TTBOMK, the mobile phones never see that key, they verify that push notifications are genuine based on the fact that they receive them via a secure channel from the Apple HQ.

Here is my alternative, simpler idea: create a keypair and upload the public half to Apple. You can then send messages by authenticating with the private key.

So, why does Apple sign my key? What do I actually use the certificate for, while connecting? Is that signing dance done because SSL supports client certs but does not support bare private keys?

I'm not a cryptography expert, so please correct any wrong assumptions I've made!


texts: AES or One-time-pad for encrypting a single 128bit block?

texts:
I just started my network security course and came across the below question. Could some one help me here.
User A wish to send a 128-bit secret message, S, to user B. As the preliminary step, both A and B agree to use a 128-bit secret key, K, selected uniformly at random. At the time of transmission, A considers two different ways to secure the secret message, S. The first way is to encrypt S using the key, K, as one-time pad and send S ⊕ K to B. Alternatively, the second method is to directly use AES algorithm to encrypt S. In this case, the secret message, S, needs to be encrypted as a single 128-bit block. Despite of using either one-time pad or AES, suppose that an adversary, C, knows some initial portion of the original secret message, S, and can see the entire encrypted message during transmission. The primary intention of the adversary, C, is to recover full secret message from the encrypted message by trying every possible key. In this situation, which method among the one-time pad and AES would be more secure?
Select one:

Both methods are equal. The adversary can decrypt the ciphertext in
both the methods
One-time pad
AES
Both methods are equal. The adversary cannot decrypt the ciphertext in both the methods

My understanding:
In case of one time pad, as the attacker already knows the initial portion of plaintext and complete cipher text, attacker can just XOR them to get the initial portion of key. Attacker has to use  brute force for the remaining key bits.
But in the case of AES, the attacker has to try 2^128 combinations to get the complete plain text.
So, AES is more secure than one-time-pad in this case.
In course content, answer is given as :

Both methods are equal. The adversary cannot decrypt the ciphertext in both the methods


texts: Discrete Logarithm within DH exchange - finding out A and B secret number

texts:
How would i find out Alices or Bobs private number from the details exchanged in public.

prime - g = 7

primitive root - n = 3

Alice - A = 3

Bob - B = 4

The details visible in public exchange are:

g = 7

n = 3

Ya == 27 mod 7

Yb == 81 mod 7

How would one go about finding Alices secret number A or Bobs secret number B from the exchange usings only the visible details exchanged in public space. Please provide an explanation to notation as well as a practice solution to the scenario I've provided.


texts: Improving efficiency of an "encryption" algorithm based on a chaotic map

texts:
I've implemented an "encryption" algorithm that uses the deterministic chaos of an extended logistic map:

$x_{n+1}= r_n \cdot x_n \cdot (1-x_n)$

$y_{n+1} =
     \begin{cases}
       \text{$x_n+y_n$} &\text{if $x_n+y_n<1$}\\
       \text{$x_n+y_n-1$} &\text{if $x_n+y_n\ge 1$}\\
     \end{cases}$

$r_{n+1} = 3.57 + \left(0.23\cdot\sqrt{x^2+y^2}\right)$

The data is first chunked into $256\cdot64$ bits which I visualise as "squares". The initial values of $x,y,r$ are determined per-chunk by sampling bytes in a SHA-256 hashed key-data pair mixed with a hash of the index of the data chunk. I then map $x,y$ values from the range of the unit square to specific bits in the chunk and flip those bits iteratively, $(256\cdot64)^2$ times per chunk.

I am now looking to increase the performance of this algorithm, and I had an idea to apply some kind of chaotic "surface" to each chunk, sensitive to initial values. I would then only need to compute the value of this surface once per bit with a single function to spread the chaos over each chunk.

Having browsed Wikipedia's list of chaotic maps, I couldn't really seem to find anything that fit what I had in mind. Are there any known functions that might yield a good result?

Edit: After suggestions that chaos theory isn't possible to make secure, I wanted to find out whether other algorithms exist that use chaos theory. Apparently there is a large quantity of literature on this topic, especially focused on image encryption. Could someone explain the main sources of insecurity in a chaos theory based encryption algorithm?


texts: How can I get select messages ciphers for salsa20poly1305 for unit tests?

texts:
In order to avoid memory errors, I always write safe C++ wrappers with strong type-safety for any C encryption library I use.

To test my wrapper of crypto_secretbox_xsalsa20poly1305 of libsodium and make sure I'm using it correctly, I need a set of messages, nonces and keys that someone used and encrypted and the outcome of that. This is necessary for unit tests.

In OpenSSL, when I do that, I usually use the terminal, and pipe from the terminal to my unit tests and compare the output of my result.

There doesn't seem to be a terminal tool for libsodium. So I'm hoping there's either an online service that does this (take msg + nonce + key and produce cipher + mac), or someone here could provide a few test
messages and their expected mac + cipher in hex.


texts: Why does PBKDF2 xor the iterations of the hash function together?

texts:
The definition of PBKDF2 states that I obtain a derived key (1) by calling a pseudorandom function a bunch of times recursively:

  $U_1 = PRF(password, salt)$
  $U_2 = PRF(password, U_1)$
  …
  $U_n = PRF(password, U_n-1)$

The standard then defines the actual key material K as

  $K = F(password, salt, n)$

where F is $U_1 \oplus U_2 \oplus \cdots U_n$

I don't understand what the purpose of XORing the blocks together is. Assuming that PRF is a cryptographically strong function, how does XORing the blocks help? Why is $U_n$ not strong enough key material by itself?

The standard mentions that the blocks are XORd together “to reduce concerns about the recursion degenerating into a small set of values” but I guess I don't understand how that can happen since the password is being fed back into the function at each iteration.

If the recursion can degenerate into a small set of values, doesn't that mean there is a short cycle in the hash function? Isn't that a bad thing for cryptographic hash functions?

(1) Assume for simplicity that the key is the same length as the hash function output.


texts: what are the NTRU keysize and application in industry?

texts:
I'm a student currently working on a research project on the NTRU cryptosystem, I've read some papers about this cryptosystem, and in those papers they are talking about keysize, is it the size of the public key or private key ?

is there any other indusctrial application of NTRU apart from CyaSSL ?


texts: Paillier equality test under the same key

texts:
I have a similar question to this one:
Is an equality test possible when using paillier crypto?

However I want to do the following:

Given the Paillier Cryptosystem.
Given the function $f(input)$, which both Alice and Bob have.
$f()$ is a deterministic function.
Both Alice and Bob have the input of this function.

Alice encrypts a message $m=f(input)$ with Alice's public key and publishes $enc(m)$.

Is it know possible for Bob to verify, knowing $m=f(input)$, if $dec(enc(m))=m$, but without knowing Alice's private key?


texts: What systems of robust steganography are out there?

texts:
By robust, I mean resistant to common image transforms (reversal, crop a non-multiple of 8 pixels off and recompress, blur, solarize to 64 levels, then interpolate, and sharpen, change compression levels, optimize for download, scale...

Suppose you are trying to embed ownership/copyright info in an image.  How do you do so in a way that survives all of the above singly or in combination? And has sufficient parameters that it is non-obvious that it has been done.

You need to build in a lot of redundancy, and error correction systems.  But that is short of workable system.

Ideally such a system is somewhat holographic in that other systems could also put data into an image, without compromising the original data.

Edit:  While the use mention is one similar to watermarking, I normally consider a watermark to be visible in the image.  Digital rights management has the addition of having various hidden attributes/data.

This came up in a discussion about Facebook putting tracking codes in images. In their case using an uncommonly used metadata field.  So take it a step further:  Can you put data into an image that is not readily recoverable without knowing a bunch of specific additional information, and that is proof against normal image operations.

Keeping the data secret is easy.  Encrypt before encoding the ciphertext into the image.  Keeping the data recoverable is harder.  I'm inquiring about the latter.