texts: How does this POLYVAL modular reduction algorithm work?

texts:
I recently found the GitHub repository used to make the measurements in the AES-GCM-SIV paper where they implement polynomial hashing using POLYVAL.

This means in this context to compute the usual $\tau=\sum_{i=0}^nm_iH^{n-i}$ for 16-byte message blocks $m_i$ and a 128-bit key $H$ in the usual way as $H_{i+1}=(m_i+H_i)\cdot H$ with messages and $H$ being interpreted as polynomials over $\mathbb F_2[x]/(x^{128}+x^{127}+x^{126}+x^{121}+1)$.

Now the actual computation uses x86 hardware intrinsics (which can be looked up here).
The code in question is Polyval_Horner (polyval.c, line 137) in particular the following extract (adopted and commented from the repo):

__m128i TMP0, TMP1, TMP2, TMP3, TMP4, T, POLY, H;
H = _mm_loadu_si128(((__m128i*)pH));
T = _mm_loadu_si128(((__m128i*)TAG));
// ordering of the inputs is reversed, last is most significant
// 0xc2000000 corresponds to the top 3 POLYVAL coefficients
POLY = _mm_setr_epi32(0x1,0,0,0xc2000000);

T = _mm_xor_si128(T, _mm_loadu_si128((__m128i*)inp));
// This instruction takes two 64-bit halves and carrylessly multiplies them
// If the lower nibble is 0, take the lower half of the first input, else the upper half
// likewise with the upper nibble for the second input
TMP1 = _mm_clmulepi64_si128(T, H, 0x00);
TMP4 = _mm_clmulepi64_si128(T, H, 0x11);
TMP2 = _mm_clmulepi64_si128(T, H, 0x10);
TMP3 = _mm_clmulepi64_si128(T, H, 0x01);
// TMP2 and 3 contain the range of coefficients from 64 to 191, add them
TMP2 = _mm_xor_si128(TMP2, TMP3);
// now extract the upper and lower halves of these coefficients and add them
// into either TMP1 or 4 depending on whether they are the lower or the upper coefficients
TMP3 = _mm_slli_si128(TMP2, 8);
TMP2 = _mm_srli_si128(TMP2, 8);
TMP1 = _mm_xor_si128(TMP3, TMP1);
TMP4 = _mm_xor_si128(TMP4, TMP2);
// reduction starts here
// multiply the lower half of TMP1 with the upper half of POLY
TMP2 = _mm_clmulepi64_si128(TMP1, POLY, 0x10);
// This re-orders the 32-bit subwords
// 78 should exactly swap the 64-bit halves
TMP3 = _mm_shuffle_epi32(TMP1, 78);
TMP1 = _mm_xor_si128(TMP3, TMP2);
TMP2 = _mm_clmulepi64_si128(TMP1, POLY, 0x10);
TMP3 = _mm_shuffle_epi32(TMP1, 78);
TMP1 = _mm_xor_si128(TMP3, TMP2);
T = _mm_xor_si128(TMP4, TMP1);

(I have not converted to pseudo-code as to preserve any specific instruction behavior I may get wrong).
This code loads a key pH and a previous iteration TAG adds it with some 16-byte input inpand multiplies it with pH in a carryless way and then reduces it modulo the Polyval polynomial into the new value of T.

My reading of the above code is that

Before the reduction TMP4 holds the 128 most-significant polynomial coefficients of the multiplication result
Before the reduction TMP1 holds the 128 least-significant polynomial coefficient of the multiplication result

Now my question is:

How does this reduction algorithm work?

Because for me, if I try it on paper with $x^{127}$ and $x$ I should get back $x^{127}+x^{126}+x^{121}+1$ but instead I think the algorithm returns me $1$.

Here's my interpretation of how to read the reduction intrinsics:

Take the lower 64-bit of the lower 128-bit of the multiplication result, multiply them with the upper 64-bit of the polynomial (in my example that's $0$ times the upper bits), call it TMP2
Swap the 64-bit halves of the original 128-bit result, call it TMP3 ($0$ in my example because TMP1 would be 0)
Add TMP2 and TMP3, call the result TMP1 ($0+0$)
Repeat the previous three steps once
Return the addition of the current TMP1 and TMP4 (the upper 128-bit) which in my case would be $0+1=1$


texts: Can BPS be used to encrypt a single integer, and restrict the output to a certain range?

texts:
As per specifications document,

"We have the natural restriction that at least two characters must be ciphered, i.e. $b \geq 2$"

where each character is represented by an integer of certain cardinality.  So basically a $2$ integer array is the minimum.

However say I want to encrypt a single input integer but restrict it to a certain range.  For example say the cardinality of the integer was $2000$ (so the range of possible values from $0 - 1999$).

Can this be done using BPS?  (i.e. Would it be acceptable to simply input an integer array of size one to the algorithm with the cardinality as the range I want?)

I am trying to encrypt a year, but in a way that does not result in a year greater than current year.


texts: Ciphertext and tag size and IV transmission with AES in GCM mode

texts:
I am completely new to using AES in GCM mode of operation, and I have not a very large background in cryptography as well. I have been playing with OpenSSL trying to encrypt and decrypt some messages. From my simple experiments rise the following questions:

First of all, I noticed that the size of the output is exactly the same as the input. I am confused. As far as I knew, AES works in blocks of 16 bytes. I am used to CBC mode, where the message needed padding. Does this mean that GCM can work with any size of the input, without having to pad and unpad things?
I read that the IV can be of any size, and that it is sufficient for it to be non-repeating. Does this mean, for example, that I can use a 4 bytes iv with a progressive counter? Is that just as easy as that or are there security issues with short and predictable IVs?
Since I need to generate a new IV for every message, how am I supposed to transfer it? As far as my understanding goes, the secrecy of IVs is not fundamental... does this mean that I can just send each IV in plaintext along with its message? If not, what should I do to let the other endpoint know about my iv?
Are MAC tags always 16 bytes long?

I hope these questions are not exceedingly dumb. They should definitely be simple and quick to answer.


texts: Differences between industrial and military cryptography

texts:
Industrial and military cryptography should follow the same basic rules, but what does make them different is:

Higher key length, protocols unknown to the civilian world, and perhaps unique methods of transferring media

Are there other fundamental differences that make military encryption safer?


texts: Mathematical Proof for Key independence in Differential Cryptanalysis

texts:
How would you construct a proof that XOR difference of two cipher texts cancels the influence of the key?

I started out with a simple cipher defined as follows:

$C = \Phi( S(P\oplus K_{0}) \oplus K_{1})$

Where

$\Phi$ is a permutation box
$S$ is a substitution box
$K_{0}$,$K_{1}$ are the first and second round keys respectively
$P$ is the plaintext
$C$ is the cipher-text

In an effort to prove that the XOR difference is independent of the influence of the round keys, I start by constructing an expression for the XOR difference of two cipher-texts :

$C_{0} \oplus C_{1} =  \Phi( S(P_{0}\oplus K_{0}) \oplus K_{1}) \oplus  \Phi( S(P_{1}\oplus K_{0}) \oplus K_{1})$

Which I've simplified to the following algebraic form:

$\Phi^{-1}( C_{0} \oplus C_{1}) = S(P_{0}\oplus K_{0}) \oplus  S(P_{1}\oplus K_{0})$

I'm too paranoid about the non-linearity of the SBOXs to apply straight forward algebraic law to this form.

How do I get rid of the SBOXs and am I even going about this proof the correct way?


texts: What is the most popular cipher suite used in TLS 1.2 for HTTPS?

texts: I'm trying to do some performance (time) calculations over TLS. I have the data I need for a variety of cipher suites but in order for the calculations to generalize well, I need to know if there is a clear most popular choice for TLS 1.2 cipher suite. Data to back up any answers would be appreciated.


texts:
I am in high school and I am writing a paper on RSA. I want to show that low values of the public key exponent can make it easy to 'invert' the function so that the encrypted message can be recovered.
How is this done? I have tried to read the Handbook of Applied Cryptography but it's not making sense...

Would this be inversion:
Taking cipher text, and continuously adding the modulus, then taking the eth root of the sum. If the result is an integer, then it is the plaintext message.


texts: How to combine pepper in random string generation

texts:
I am writing a key generator program.

Indeed it generates a key in the form of a random text string (not binary), with its characters chosen randomly from a set of defined characters, with a specified length.

You can see an example of my program's config.ini file for clarification:

[general]
key_chars = abcdefghijklmnopqrstuvwxyz
            ABCDEFGHIJKLMNOPQRSTUVWXYZ
            0123456789
key_len = 22
pepper = G89ne_^DFIM"]12@\z2's#GBA

Ignoring the pepper part, we can generate the desired key with a code like this (code is in Python language):

Warning: The following code is not secure! *

def generate(self, keyLen, keyChars):
    key=''
    for i in range(keyLen):
        randIndex=randint(0, len(keyChars))
        key+=keyChars[randIndex]
    return key

But I don't want my keys' security rely solely on the OS/Language (presumably) secure random generator (In this case, pycrypto module's CSPRNG that probably itself uses OS' CSPRNG under the hood), so I want to engage the pepper in the procedure too, but I am not sure about the proper way to do that securely. Please tell me how to combine the pepper in the above code (Or maybe you suggest a different method for doing that which is better suited to such purpose).

*: I used randint in my example code because I thought it is part of pycrypto module, then I realized that is not the case!


texts: Do I need to provide entropy to secp256k1_ecdsa_sign() ?

texts:
using secp256k1_ecdsa_sign()  I noticed the same data signed multiple times, coming back with the same signature. I always thought that signatures are different because random data is somehow involved.

looking at my  (production) code, this is my call:

    secp256k1_ecdsa_signature sign(const pb::sha256 &in) {
        secp256k1_ecdsa_signature sig;
        if ( 1 != secp256k1_ecdsa_sign(pb::TheCTX::instance()->CTX(),
                                       &sig, in.data, key_data, NULL, NULL) ) {
            qDebug() << " error sig";
        }
        return sig;
    }

This is the function signature:

int secp256k1_ecdsa_sign(const secp256k1_context* ctx,
                         secp256k1_ecdsa_signature *signature,
                         const unsigned char *msg32, const unsigned char *seckey,
                         secp256k1_nonce_function noncefp, const void* noncedata)

Question1: Where is randomness coming from? The default secp256k1_nonce_function, when i pass in NULL is nonce_function_rfc6979.

Question2: Did I do something wrong? Can my private-keys be derived from my signed messages?

Please help... kinda freaking out.. ty


texts: Security proof for CBC as a prefix-free PRF

texts:
I am currently trying to fully understand Dan Boneh's/ Victor Shoup's proof in their excellent crypto book draft, that the raw CBC construction is a secure pseudo random function family for prefix-free adversaries (see Section 6.4.1).

The methodology of the proof is to replace the PRF $E_K: \mathcal{X} \rightarrow \mathcal{X}$ with a function $f:\mathcal{X} \rightarrow \mathcal{X} $, that is chosen uniformly from random from set of all functions $f \stackrel{\$}{\leftarrow} \text{Funs}_{x,x}$:

The crux is then to calculate an adversary's ability to distinguish this $\text{CBC-}f$ construction from a random choice out of $\text{Funs}_{mx,x}$ (the set of all functions $\mathcal{X}^{\leq m_\text{max}}\rightarrow \mathcal{X}$ with $1\leq m \leq m_\text{max} $). For this, a rooted tree is used, where each query represents a path in this tree. The goal is to find the probability, that two inputs for $f$ collide (CBC chain value $\oplus$ some $X_i$ collides with some other CBC chain value $\oplus$ some $X_j$). This is where the prefix-freeness comes into play, because it ensures, that the message blocks are statistically independent from the CBC chain values and hence two inputs for $f$ collide with probability $1/|\mathcal{X}|$.

Last but not least my question: Why do we have to consider internal collisions too? Why is it not sufficient to only consider collisions on the last $f$ invocation for every query? How can a prefix-free adversary know, if there was an internal collision, when he only sees $Y$?


texts: SHA-3 was released by NIST just over 4 years ago this week. In my experience it does not seem to be as widely used as I might have expected. I see SHA-2 and even SHA-1 more often. What are your opinions on why this is the case?:


texts:
I read about how is an input message prepared to be hashed by MD4,MD5 or SHA-1:

  Step1 Append padding bits

  The input message is "padded" (extended) so that its length (in bits)
  equals to 448 mod 512. Padding is always performed, even if the length
  of the message is already 448 mod 512. Padding is performed as
  follows: a single "1" bit is appended to the message, and then "0"
  bits are appended so that the length in bits of the padded message
  becomes congruent to 448 mod 512. At least one bit and at most 512
  bits are appended.

  Step2. Append length

  A 64-bit representation of the length of the message is appended to
  the result of step1. If the length of the message is greater than
  2^64, only the low-order 64 bits will be used.  The resulting message
  (after padding with bits and with b) has a length that is an exact
  multiple of 512 bits. The input message will have a length that is an
  exact multiple of 16 (32-bit) words.

  ... algorithms steps

I read that hose 2 steps are always the same for input messages for MD4, MD4 and SHA-1. How about  SHA-224 / SHA-256 / SHA-384 / SHA-512? How do they 'prepare' input to compute a hash? The same way maybe?


texts: Validating that a hash is over a specific value for two hashes with additional (known but different) input

texts:
$M$ (not public) is hashed with a hash function $\text{H}$ that includes a variable $T_1$ (public), giving $C_1$ (public). The same $M$ (not public) is hashed with the same hash function with another variable $T_2$ (public), giving $C_2$ (public).

Knowing the variables, $C_2$ can be verified to be from the same data as $C_1$.

Is there a hash function $\text{H}(M + T_1) = C_1$ that relates to $\text{H}(M + T_2) = C_2$ in such a way that, knowing $T_1, T_2, C_1, C_2$, and with no knowledge of $M$, it can be verified whether both use the same $M$?


texts: ElGamal signature without calculating the inverse

texts:
I stumbled upon this question in some textbook.

  Propose a variant of ElGamal signature scheme  such that there is no need to calculate the inverse $k^{-1}$ as it is usually done using the EEA.

Recalling what ElGamal signature is about: we fix a prime number $p$ and a generator $\alpha$ of $Z_p^*$. User $A$ then chooses a number $a \in \{0, \ldots, p-1\}$ as its private key and sets $ \beta = \alpha^a \pmod{p}$ as its public key. To sign a message $x$, $A$ chooses a random $k \in Z_{p-1}^*$. The signed message is then  $(\gamma, \delta)$  where $$\gamma \equiv \alpha^k \pmod{p} \quad{} \hbox{and} \quad{} \delta \equiv (x-a\gamma)k^{-1} \pmod{(p-1)}$$

To verify the validity of the signature, $B$ verifies that $$ \beta^\gamma \gamma^\delta \equiv \alpha^x \pmod{p}$$

I have no idea how to solve this problem without breaking the security of the system. Browsing the internet, I've found some papers related to this problem, but the proposed solutions seemed too complicated for a question posed at the undergrad level. Does anyone know a clever solution?


texts:
Alice uses an ElGamal signature with base the group $Z^*_{107}$ and parameter $g=3$ of order $q=53$.The private key of Alice is some $x \in \{0,1,.....,52\}$ and the public key of her is $y=10$. To sign the message m, she calculates $r=g^k \bmod107$ for $k \in \{0,1,......,52\}$ and $s=(k \cdot h(m)+r\cdot x) \bmod 53$. For signing the first message, Alice chooses a random $k_1 \in \{0,1,......,52\}$. To sign  the second message she uses $k_2=(2 \cdot k_1 +1) \bmod 53$ and generally if for the signature of $i$-th message she has used the $k_i$ for the $(i+1)$-th message she uses the $k_{i+1}=(2\cdot k_i +1)\bmod 53$. You know two successive signatures of Alice: $(r,s)=(79,7)$ of message $m$ with $h(m)=2$ and the signature $(r',s')=(105,41)$ of message $m'$ with $h(m')=3$. Find the private key of Alice (of course withουt calculating directly any discrete logarithm in group $Z^*_{107}$)

I am trying to solve this. I tried to apply the ElGamal Algorithm but I do not know how to use the $h(m)$ hash function. Can anyone help to solve it and help me how to use correct the ElGamal signature?
(source: mathematical competition 2008,France)


texts: Distinguishing Original VS Fake Products

texts:
Let's assume that we want to distinguish original vs fake products when a customer receives them. I was thinking about using a protocol similar to digital signature.

My question is can this problem be mapped to digital signature?
If not, what other security protocol can we use?

More details:
I was thinking about using the digital signature. Let's assume the original company writes a pair of digital signature and plain text on the product. Then, when customer receives it, (s)he can verifies it using the protocol (you may refer to here (3' 56'') for the protocol), and understands if the item is coming from the original sender or not.
However, the attacker can come in the middle, make a product, and copy the digital signature and the plaintext from original one!


texts: What is sent on the initial communication with Kerberos?

texts:
When a user wants to communicate with another user (let's say Alice and Bob), what is sent over the network during the initial communication?

Alice uses her Kerberos client and enters her password and username.

Something which is not clear to me:

Will she send a message containing

time
username
hash of password

generated with the session key of the kerberos client and authentication server?

Or will she send a message to the AS containing

time
username

encrypted with Alice's password and this again encrypted with a session key?


texts: On countermeasures for replay attacks. Does this one require plaint text password storage?

texts:
I was reading this wiki section on the countermeasures against replay attacks and it basically suggests that:

If Bob wants to confirm Alice's identity he can send a one-time token (I think it should be called a 'salt') to Alice which she appends to her password and hashes it before sending it back to Bob, who in turn also does the same operation and compares the results.

But if Bob must perform the same operation i.e. append that token to Alice's password and hash it, then he must also have the original password stored, right?  Isn't this a security risk?

So the question is:  Does Bob have to have a plain text version of Alice's password and if not, how does he avoid this requirement?


texts: openssl logs showing keyblock length of only 88 bytes instead of 136 bytes

texts: I was decrypting TLS encrypted data from wireshark using the openssl(TLS1.0 version) TLS logs which provides the complete key block which of size 136 bytes.Now i moved to TLS(1.2 version) in that Key block size is of 88 bytes only.Anybody please help me in this... Thanks in Advance


texts: Recommended skills for a job in cryptology

texts:
First let me apologize if this is an ill posed question. Let me also note that I do not in any way seek a comprehensive answer, simply your thoughts on what makes for a valuable asset to a company like the NSA. I am a Maths student in the US, and I realize that a problem-solving mind is at minimum required for said question.

Some other responses I would find helpful include coursework, relevant programming languages, as well as helpful books. I am currently reading Schneier's (sic?) Applied Cryptography.


texts: Can you recognize a low private exponent from a public key?

texts: In the RSA cryptosystem, Wiener, Boneh and Durfee showed that low private exponents can be efficiently recovered. Is it possible to see from a public key alone whether the private exponent (d) is small? Is the public exponent (e) then necessarily large? Is it possible to have a small private exponent when e=65537?


texts:
I have been hearing about Salsa20 from quite some time. It is even the favorite cipher in the ransomware world. Some ransomware used this cipher, probably because of speed.

I want to know how secure  this cipher is when compared to AES. How much has it has been reviewed by cryptanalysts?


texts: Why do 5G, 4G, etc., use non-conventional algorithms?

texts: Looking up information about 5G and the previous 3GPP standards, why have they been incorporating non-conventional algorithms into the standards? For example, AES has been considered secure for ages and there is lots of support for hardware acceleration, but what was the rationale behind, for example, adding ZUC and SNOW 3G too? Does adding more algorithms make it easier for network operators in any way?


texts: Setting protocol parameters to achieve concrete security

texts:
Background

One issue with modern security proofs is that they are usually asymptotic. In other words, such proofs are usually formulated as follows: For any polynomial-time adversary $\mathcal A$, we can select a large enough security parameter $n$, such that the probability that $\mathcal A$ breaks the system is a negligible function of $n$.

Unfortunately, concrete values for parameters of the protocol cannot be readily deduced from such asymptotic proofs. For instance, the size of RSA modulus for a secure signature scheme may not be obtained from an asymptotic proof of security for the given scheme.

This issue was first formalized by Bellare and Rogaway, in their famous paper "The exact security of digital signatures: How to sign with RSA and Rabin." They provided a new type of analyzing and proving the security of some scheme, which they termed exact security. Soon after, numerous papers considered this notion, and gave various results on the exact security of signature schemes.

Assumptions

This question considers "exact security" for identification protocols. Since we're going to give concrete parameters, we have to make some explicit assumptions:

The time-complexity of entities is limited to $2^{80}$ operations.
Entities can perform up to $2^{30}$ operations per second.
The best algorithm for factoring an integer is GNFS. Given this assumption, factoring a carefully chosen $1024$-bit integer requires about $2^{86}$ operations, which is infeasible according to assumption 1.
In the identification protocol, there is a $30$-second time-out. The adversary can take its time to perform any preprocessing, but when engaged in protocol execution, he must reply within $30$ seconds, or time-out occurs and he fails. (This is in contrast to signature schemes, where the adversary is not faced with such restriction.)
During the lifetime of the system, the adversary may engage in at most $10^8$ identification sessions. He is successful if he can impersonate in at least one session, and he fails otherwise. In other words, a successful adversary is one whose success probability is at least $10^{-8}$.

Protocol and Proof

The honest prover has the factorization of an integer $n$, and the verifier is going to verify this. Let $L = \Theta(1)$ and $m = \Theta(|n|)$.

The identification protocol is the $m$-time repetition of a $\Sigma$ protocol. The challenge of the $\Sigma$ protocol is chosen randomly from the set $\{0,\ldots,L-1\}$.

Now, we are given the following "tight" security proof (the details of how this proof is obtained is unimportant):

For any adversary $\mathcal A$ whose time-complexity is $T$, and who breaks the identification protocol with probability at least $\epsilon$, there exists another adversary $\mathcal B$, whose (expected) time-complexity is $\frac{TLm}{\epsilon} + \Theta(|n|^2)$, and can factor $n$ with probability 1.

Question

  How can we use these assumptions and facts, to suggest concrete values for $|n|$, $L$, and $m$, such that the system is both efficient and secure? (The efficiency condition is included because the choice of extremely large parameters will obviously make the system secure.)


texts: Is it possible to determine the number of characters used for a password used to encrypt a file with AES 128?

texts:
I lost a password for an ethereum wallet at the end of 2016. Computer immediately shutdown and password was not recoverable.

I know there are many potential avenues for narrowing my search for what my password could have been, but I am wondering if the number of characters can be determined from the encrypted file?

I dont know if this would make a difference but it was an ethereum wallet, using Geth


texts: Is it safe to assume Salsa20 to be a PRP?

texts:
Often in security proofs a certain block cipher is assumed to be a pseudorandom permutation or PRP. I wonder if this goes for stream ciphers as well, and specifically for Salsa20.
If we limit ourselves to the scope of one Salsa20 block (64 bytes), being fed 64 bytes of plaintext data, is it safe to assume $Salsa20_{key,nonce}$ to be a (strong) PRP family?
I'd very much be interested in the reasoning why or why not, and whether this extends to other stream ciphers.


texts: What is the difference between order of base point and curve order in EC?

texts:
When I was read about the elliptic curve cryptography I found some definition about domain parameter of  elliptic curve like the follow. But I did not understand something
$p$: prime number.
$a, b$: field elements, they specify the equation of the elliptic curve $ E$ over $F_P$,
$y^2  ≡ x^3+a • x+b  $
$G$: A base point represented by $G= (xg, yg)$ on $E (F_P)$
$n$: Order of point $G$ , that is $n$ is the smallest positive integer such that $nG = O$.
$h$: cofactor, and is equal to the ratio #E($F_P$)/$n$, where #E($F_P$) is the curve order.
My question
What's diffrence between  $n$ & #E($F_P$)? also
I think two are same value.
because #E($F_P$) is Curve Order where The number of points on the elliptic curve is called its curve order. and when we do #E * $G$ = $O$.
Is this right or not right?


texts: Pohlig-Hellman: While solving in a subgrp, why is multiplication done mod the parent group's $p$ while the exponent is expanded as per $p_i$ of subgrp

texts:
In the Pohlig-Hellman algorithm, we take a Discrete Log Problem (DLP) in a group & solve it in subgroups $p_1^{n_1}$, $p_2^{n_2}$, $p_3^{n_3}$ etc & then combine it with the Chinese Remainder Theorem (CRT).
The original DLP is $\bmod p$ & the order $p -1 = n = p_1^{n_1} * p_2^{n_2} * p_3^{n_3} .... $
When we are solving for a subgroup $p_1^{n_1}$, we frame number of coefficients of $x$ based on the max value $x$ can take i.e. $p_1^{n_1} - 1$
For example, if we are solving for $3^4$, then we frame $x$ as
$x = c_0 + 3c_1 + 3^2c_2 + 3^3c_3$
$x$ has 4 coefficients here ($c_0$, $c_1$, $c_2$ & $c_3$) because the max value of x is [$p_1^{n_1} - 1$] (because it's $\bmod p_1^{n_1}$)
However, when we actually solve for finding the coeffs of $x$ for subgroup $p_1^{n_1}$, we do the calculations with $\bmod q$, instead of $\bmod p_1^{n_1}$. Why is that?
For e.g. if we take the example here: When they calculate $8006^{2025} = 1$ for subgroup $2^2$, this is actually calculated as $8006^{2025} \bmod p$ rather than $\bmod p_1^{n_1}$. It's the same in all the calculations. Why is this? Shouldn't it be done $\bmod p_1^{n_1}$
When we are finding $x = x_1 \bmod {p_i}^{n_i}$, we are doing calculations $\bmod q$ instead of doing them $\bmod {p_i}^{n_i}$.
EDIT: Or an alternate question could be this - the operations of the subgroup is always going to be $\bmod p$ rather than $\bmod {p_i}^{n_i}$.  Considering that, then why are the 3 congruence equations we get for the 3 subgroups also not $\bmod p$. Why are they $\bmod 4$, $\bmod 81$ & $\bmod 25$?
EDIT2: Based on various answers, I have boiled down my question to one line
While multiplication in the subgroup is being done modulo p, why are exponents in the subgroup expanded modulo $p_i$?
Is there any theory explaining this?


texts:
This question is about the approximate GCD problem which is defined as follows: Given any number of the approximate multiples $a_i = p \cdot q_i + r_i$ of $p$, where $p$, $q_i$ and $r_i$ are integers, the problem is to find the hidden common divisor $p$. Note that $q_i$ and $r_i$ change in each $a_i$.

I've recently read “Practical Fully Homomorphic Encryption without Noise Reduction” by Liu, about a fast symmetric FHE scheme, which is based on the approximate GCD problem. Now the paper claims that it reaches 128-bit security by increasing the linear search space's size to $>2^{128}$.

Is there any attack on the approximate GCD problem, that is faster than brute-force (trying out all possible approximate GCDs)?

As an example set of (brute-force secure?) parameters, I'd say that $\log_2q_i\approx64\approx\log_2r_i$ and $\log_2p\approx 128$ should be secure against brute force as one would need $2^{128}$ tries for retrieving $p$ or would have to try more than $2^{64}*2^{64}=2^{128}$ values for $q_i$ and $r_i$.


texts: How does the sender obtain the receiver's public key?

texts:
Cryptography process includes encryption and decryption process. In public key cryptography public key of receiver is being used for encryption.

I want to know how public key of receiver is sent to sender?


texts:
Just for the sake of learning, I'm attempting to write an ECDSA implementation in Java.

I have what I believe is a correct implementation for point addition and doubling, but I'm not sure how to implement point multiplication - Every online description I've found says to use an algorithm like this:

public static Point pointMultiply(BigInteger kin, Point a, Curve curve) {
        Point r = new Point(BigInteger.ZERO, BigInteger.ONE);

        BigInteger k = kin.mod(curve.getN());
        int length = k.bitLength();

        byte[] binarray = new byte[length];

        for(int i = 0; i < length; i++) {
            binarray[i] = k.mod(BigInteger.TWO).byteValue();
            k = k.divide(BigInteger.TWO);
        }

        for(int i = length - 1; i >= 0; i--) {
            r = pointAdd(r, r, curve);

            if(binarray[i] == 1) {
                r = pointAdd(r, a, curve);
            }
        }

        return r;
    }

Except all of those descriptions define r as the point at infinity. That's great, except my point doubling/adding code requires actual values in order to operate on the point. How do I find an actual value for that point so I can manipulate it, and if there is no defined value, how would I implement point multiplication?

Most of the descriptions of the point at infinity I've found say that it either isn't a real point and is some sort of abstract thing (in which case I don't understand how one can manipulate it) or that it has coordinates of (0,1), which does not give me a correct pubkey when I test it against BouncyCastle.


texts:
We've been asked to generate a certificate signing request using elliptic curve and we can't use any third-party library as it's an embedded application with very limited resources).

We are used to generating CSR using RSA, but we can't find any documentation on how to do that with an elliptic curve; specifically, which data to use for the signing part. Studying OpenSSL-generated CSR it looks like there are multiple signatures generated, or a hash of some kind, but we don't know. And OpenSSL source code is quite difficult to read when you're not used to it.

Can anyone point us in the right direction?


texts: FHE over the integers - Is that paper's scheme known to be insecure against quantum adversaries?

texts:
I was reading the paper Fully Homomorphic Encryption over the Integers, and started

wondering if there is a known quantum attack on their main scheme, because

There is an efficient quantum attack on their "even slightly simpler scheme", as follows:
completely factor $x_{\hspace{.025 in}0}$,

for each [product of a very small number of $\hspace{.03 in}x_{\hspace{.025 in}0}\hspace{-0.04 in}$'s prime factors] with the right number of bits,

see if using that as a private key correctly decrypts a moderate

number of "test ciphertexts" generated for that purpose

if one does, then use it to decrypt the challenge ciphertext and output that decryption result

otherwise output failure

That attack works because $p$, as a random odd integer of a given bit length, has a noticeable

probability of being prime, so in particular of having a very small number of prime factors.

and

The section that describes their "even slightly simpler scheme" also says they

"do not know of ant attack that works for this 'easier case' but not for the general case.".

(The "ant" typo is in the paper that I linked to.)

On the other hand, the version on Springer does not include that section.

  Is there a known efficient quantum attack on the main scheme of those two papers?

(I say "those two papers" because I'm not aware of any difference between their schemes,

and if there is one then I don't know which of them I mean.)


texts: For TLS AES_CCM mode how does CBC_MAC work when the message length is not aligned to block size?

texts: Even after goign through lot of specs I failed to understand how CBC-MAC works, specifically in case we have message not aligned to 16 bytes. Are there any padding bytes?


texts:
I happened to watch Mr. Bill Buchanan lecture that explains Winternitz one time signature scheme (https://www.youtube.com/watch?v=eqMMlcN4zSc). The scheme shown in the lecture is susceptible to universal forgery, as if an Opponent query for OTS on a message composed of 32 0xFF octets, he gets back Hash(prive[i]) for i=1..32, and with this, he can sign any desired message. I understand that there should be added a checksum to prevent this attack, and my question is ;

whether the checksum: 0xFFFF-SUM(N[i]) i=1...32 will solve the problem?

The idea is that any octet in the message that is modified to be lower than 0xFF, will cause at least one byte in the checksum to increment, and thus will require the Opponent to inverse a one way hash function.


texts:
Is it possible for one party to encrypt some data and have another party (unknown to the first party) view that original data if a certain condition is met?
I cannot find any information about this despite numerous searches.  I  might have the terminology wrong, or perhaps... it is impossible!
I read about zk-SNARKS, and as I understand it, this technique is used to prove a computation on an encrypted value or perhaps show the opening of some commitment in a set.
I thought perhaps you could set a condition in a circuit.  Say (for simplicity), using a (public) input integer x less than 100 (or maybe part of a set or something), you could print secret data y. But that would mean the encrypting party would have to produce an unsatisfied partial SNARK somehow. Then the person that wants to attempt decryption would have to input their integer later.
I guess it's not a great example unless the input is provably random, but is there some technique to do this? I only mention SNARKS as it's the only thing I could think of where you can have arbitrary conditions like this. In reality, I was thinking of something where the data revealed could be any size, like a huge text file or something other than an integer y.


texts: Is phi-hiding assumption as hard as integer factorization?

texts:
Phi-hiding assumption can be simply stated as (wrt hardness)

It is difficult to find small factors of $\varphi(m)$ where $m$ is a number whose factorization is unknown and $\varphi$ is Euler's totient function.

Is the hardness due to this assumption comparatively higher than than the hardness of integer factorization?
My intuition says that finding prime factors of $\varphi(m)$ is simpler than finding the prime factors of $m$. So I believe that the hardness of the phi-hiding assumption is at most equal to the hardness of integer factorization.


texts: What is the limit of plaintext required to break the Vigenère encryption?

texts:
A theoretical question about the Vigenère cipher:

Without any knowledge about the key (not even it's length) can we tell how much known or chosen plaintext is needed for the adversary to completely recover the key?
What about if we know the key length? (I assume that we'll need plaintext with the same length of the key).


texts:
Since AES CTR mode uses a unique IV and counter to produce the key to XOR  with the plain text to get the ciphertext, the question is so as to how decryption is done. Since AES CTR produces a different cipher each time for the same password and plain text due to the unique key, how is it possible for the decryption function to produce the same key for a given password to get back the plain text?

Can anyone please explain me on how this is happening?


texts: How to check the integrity of a key received through mail using symmetric encryption?

texts:
I would like to provide access to encrypted data through a cloud service provider, using a pay-as-you-go model. This means that we will sometimes need to revoke a user's access to the data. To restrict a revoked user's access, the CSP will re-encrypt the data and send the new key to valid users only through their mail.

Before using the new key they received by mail, however, the users will presumably need some way to verify its integrity and authenticity. If possible, I would like to implement this using only symmetric encryption (like AES) instead of asymmetric encryption like RSA. Is this possible, and if so, how?


texts: Extract private RSA key from USB cryptographic token using Bardou et al. attack (variant of "million message attack")

texts:
There is a side channel attack on tamper-resistant USB cryptographic tokens using padding-oracle, described by Bardou, Focardi, Kawamoto, Simionato, Steel and Tsay, titled "Efficient padding oracle attacks on cryptographic hardware" (INRIA; CRYPTO 2012, LNCS Volume 7417, 2012, pp 608-625), full paper, brief description. This attack uses vulnerabilities in implementation of PKCS#1v1.5 padding and is an evolution of "million message attack", discovered by Bleichenbacher. Bardou was able to cut cost of attack from 1 million decryption requests down to several tens of thousands requests.
My question is: If somebody owns an vulnerable USB token (listed in the paper), and there is a single RSA key recorded inside this token, can he setup this attack to extract stored private key from this token?
Update: there is FAQ on Bardou web-site: http://www.lsv.ens-cachan.fr/~steel/efficient-padding-oracle-attacks/faq.html

What are the prerequisites for these attacks?
You need access to the UnwrapKey function. This could be achieved, for example, directly by putting malware on the host machine, or indirectly if the unwrap key functionality is exposed via a network protocol.
What are the consequences of these attacks?
The modified version of the Bleichenbacher attack reveals a plaintext encrypted under an RSA key. That plaintext, in the context of the PKCS#11 UnwrapKey command, is a symmetric key. The same attack can also be used to forge a signature, though this takes longer. Our paper gives full details.
The Vaudenay CBC attack may reveal either a symmetric key or a private RSA key if it has been exported from a device under a symmetric cipher like AES using CBC_PAD.
Do the attacks in the paper reveal the private half of RSA keypairs?
Like the original algroithm, our version of the Bleichenbacher attack does not reveal the private half of the RSA key used for encryption.

Riccardo Focardi has online paper Practical Padding Oracle Attacks on RSA with nice description of padding attacks, including Bleichenbacher and Bardou. He also gives a link to Nate Lawson's repsonse to RSA claims (a-la Our tokens are not vulnerable). And after this paper RSA again says: "No smartcard cloning"


texts: Use Initializaiton Vector as Additional Authenticated Data

texts: Cipher is GCM-AES.  Is it acceptable/recommended to store the IV as AAD?  Any popular examples?


texts: Security equivalent to Diffie–Hellman problem?

texts:
I've been doing the security proof for one of my Theorem. Basically, given
$g^a$, $g^b$, $g^{cb}$, $g$ and $c$ as known values. Is the problem of computing $g^{acb^{-1}}$ equivalent to the Diffie Hellman-problem? In other words, is this easy to compute that?

My feeling is that its similar to the harder problem of the original Diffie-Hellman, which is given $g^a$, $g^b$, $g^c$ and to compute $g^{abc}$. But I couldn't come up with a reasonable proof. Could you please help?

Thanks,


texts: Does a cofactor of an elliptic curve have to be an integer?

texts: What are the implications of a curve having a non-integer co-factor for its generator point? Is that even possible?


texts: Is it possible to combine cryptography with steganography

texts:
Definitions:
M - original message,
Me - encrypted message M,
S - watermark message,
Ms - message M with steganography watermark S,
e - encryption private key,
d - decryption key (it is private too),
s - key for signing message with watermark,
ds - decryption public key, inseparable combined with watermark key s,
v - key for verify watermark S in message Ms.

Here is the task:

Alice generates two keys e and d, so:
(M, e) = Me and (Me, d) = M

Then Alice generates keys s and v for watermarking message with S and verifying it:
(M, s) = Ms and (Ms, v) = S

After that Alice takes decryption key d and combines it with s, so:
(d, s) = ds and there is no F that could F(ds) = d

Then Alice sends Me to Bob by unsecured public channels.
And Alice gives ds to Bob by secured private channel.

Bob can read Me by applying key ds, so:
(Me, ds) = Ms
Bob cannot do and there is no F to:
F(Me) = M or F(Ms) = M

And Bob shares message Ms to public channels.

Now Alice have found message Ms and can verify that message has been shared by Bob, like this:
(Ms, v) = S

Is someone here knows is it able and exists some algorithms to do that,
may be some implementation of it, and how to combine existing encryption and watermarking libraries?


texts: Are cryptographic hash functions quantum secure?

texts:
I was reading a paper related to post quantum cryptography. It says that RSA, ECC and ElGamal encryption schemes would be obsolete with the advent of quantum computers. But the hash functions can still be secure. I don't understand how one can unilaterally claim this security when hash functions themselves are not based on any hard problems. (I do have the knowledge of Merkel-Damgård and Keccak construction).

Are there hash functions considered secure just because nobody has come up with a quantum algorithm to solve it? Or are there any reduction to any well known hard problem? It there is please explain the reduction.


texts: I've seen the word 'cost' being used several times in describing algorithms e.g. algorithm A costs more to compute than algorithm B. What does 'cost' mean in this sense?


texts:
If verifiers are public blockchain nodes, which might leak information. Does this imply that range proofs such as Boudot's and Lipmma's (squaring based) approach could not be applied, unless a trusted set-up is used?
In this case, if we need a range proof without trusted set-up, what are the choices out there? Bullet range proof? any other altnernatives?


texts: Combine two sha512 hashes to a single hash

texts:
Assume I have two data fragments: $Frag_1$ and $Frag_2$.

I can build sha512 hashes the usual way with $SHA512(Frag_1)$ and $SHA512(Frag_2)$ and then hash the two fragments appended to each other:

$$SHA512(Frag_1 | Frag_2)$$

My question is, is there any way to combine the hashes of those two fragments so that it would be possible to compute the hash of their appended version?

More precise: Is there an operation (denoted here with a red question mark “$\color{red} ?$”), so that

$$SHA512(Frag_1)\ \color{red} ?\ SHA512(Frag_2) == SHA512(Frag_1 | Frag_2)$$

It is possible to create the data fragments with a length of a multiple of the block size of sha512?


texts: Isn't the deterministic property of (EC)DSA a security problem?

texts:
From what I read in Wikipedia's article "Elliptic Curve DSA ~ Security", the "deterministic" generation of $k$ can help prevent certain type of attacks (such as the one happened to Sony).

However, wouldn't the deterministic property be predictable as compared with "probabilistic encryption"? To me, it seems like RSA does use padding to make it non-deterministic. From a security point of view of, wouldn't that be undesirable?


texts: What is the meaning of weight in cryptography and how is it related to branch number?

texts: I am trying to understand the mixcolumn design of AES. I read that the branch number is 5 and there was a definition that referred to weight of vectors. What is weight of a vector?


texts: efficient authentication with broadcast encryption?

texts:
(I am not a crypto expert, so I apologize if the terminology I use is incorrect.)

Suppose I have the following simple broadcast encryption scheme for securely sending content to $n$ authorized recipients using only symmetric-key algorithms:

each authorized recipient is given a recipient key (known only to the sender and recipient)
the sender generates a random key to encrypt a message (content key)
for each receipient, the sender broadcasts the content key encrypted with the recipient key
each recipient uses its recipient key to decrypt the content key
the sender broadcasts the message encrypted with the content key
each recipient uses the content key to decrypt the message

With the above scheme, there is no authentication.  A man-in-the-middle attack would allow one recipient to undetectably alter the original message on its way to another recipient.  Some additional steps could fix this:

the sender calculates a cryptographic hash of the content
for each recipient, the sender broadcasts the hash encrypted with the recipient key
each recipient decrypts the hash and uses it to authenticate the message

My question:  Is there a scheme that allows recipients to authenticate the message without the $\operatorname{O}\left(n\right)$ overhead of sending the encrypted hash and without using asymmetric cryptography?  If not, can the overhead be reduced?


texts: Low level explanation of how a message is sent via RSA

texts:
I understand that RSA encryption uses this formula:

C = M^e (mod N)

public key is e and N

N is pq - p and q are private key.

mod N makes above function one-way - ie cannot be reversed.  Hence given C, e and N, it is not possible (easily) to find M.

Basic idea is that modulo arithmetic on an exponent is a one way function.

The practical bit I am struggling on now is that M (the message) must be a number.  How is the text eg "I love you" converted to a number.  I am looking to understand the basic concepts but also in reality what scheme is used to create a number from the text.  What are the options and what is generally used in practice?  Please explain the mathematics as required.

You could take the byte stream of the text message above:

01001001001000000110110001101111011101100110010100100000011110010110111101110101

and treat as a LARGE binary number.  I guess the numbers would get pretty large like this so probably not the way its done.


texts: Does ElGamal Encryption create a different key for each block sent?

texts: I ask about ElGamal algorithm. Is ElGamal algorithm used new key for each encryption process. in other word it should we use new key for each chunk? For example, if we have message that has four block each block less than $P$. Where $P$ is the prime number used in ElGamal. How many keys should be used to encrypt this message?


texts: Is there a 1:1 mapping between private and public EC keys?

texts:
After asking: Are all possible EC private keys valid? I learned that all 32 byte (256 bit) values greater than 0 and less than n are all valid private keys.  This means that 99% of all 256 bit values are valid private keys.  (This was a revelation to me.)

The public key space is 257 bits, as it includes X and the sign bit of Y.

Is there an exact 1:1 mapping between private and public keys?

Is there a way of telling whether a 257 bit value is a valid public key? (i.e. that a private key maps to it, as slightly more than half of all 257 bit values must not be valid public keys, if there is a 1:1 mapping.)

(I'm using secp256k1.)

Thanks for your answers.

My mental model, for an imaginary curve with n = 5, a 3 bit private key and 4 bit public key now looks like this:

private              public
0x0    +-----------> 0x0
0x1 ---+             0x1
0x2 -----------+     0x2
0x3 ---------+ |     0x3
0x4 ---+     +-|---> 0x4
0x5    |       |     0x5
0x6    |       |     0x6
0x7    |       |     0x7
       |       |     0x8
       |       +---> 0x9
       |             0xa
       |             0xb
       |             0xc
       |             0xd
       |             0xe
       +-----------> 0xf


texts: Why should the RSA private exponent have the same size as the modulus?

texts:
Consider the generation of an RSA key pair with a given modulus size $n$ and a known, small public exponent $e$ (typically $e = 3$ or $e = 65537$). A common method is to generate two random primes numbers of size $n/2$ (or very close), and check at least that they are probable primes and that $\mathrm{gcd}(e, (p-1)(q-1)) = 1$. Once $p$ and $q$ have been vetted, from what I've seen, the other parameters (the private exponent $d$, or the CRT parameters if desired) are computed but not subject to any extra check.

I have met an extra requirement whose purpose I don't understand. In the Référentiel Général de Sécurité (something like the French equivalent of FIPS), annex B1 §2.2.1.1, a rule states:

  [RègleFact-3] Private exponents must have the same size as the modulus.

What is the purpose of this rule? I know that small private exponents are bad, but here small means something like $d \lt N^{0.5}$. Even allowing for a security margin, this is a far cry from requiring $d \gt N/2$. What can go wrong if the size of $d$ is not verified (so the probability that $d \lt a N$ is close to $a$)?


texts: Linear congruential generator with non constant increment

texts:
Consider this random generator function.

A simplified version is provided below (this is C++, mind that "seed" is a reference):

uint32_t Rand(uint64_t& seed)
{
    seed = 1683268614LL * (seed & 0xffffffff) + (seed >> 32);
    return seed & 0xffffffff;
}

For those unfamiliar with C++: & denotes bit-wise AND, LL as a suffix denotes signed long long (signed 64-bit usually), >> denotes plain bit-shift, the uint64_t& in the header denotes that the input is a reference to an unsigned 64-bit integer, that is, updates also apply outside the function.

This is almost a linear congruential generator (LCG), the only difference is that the increment is not a constant, but a part of the seed itself.

My question is on the security of this algorithm, since LCGs are very easy to break.

Does using a non constant increment improve or decrease security? How could this be cracked other than by bruteforceing it?


texts:
An administrator is testing the collision resistance of different hashing algorithms.
Which of the following is the strongest collision resistance test?

A. Find two identical messages with different hashes

B. Find two identical messages with the same hash

C. Find a common hash between two specific messages

D. Find a common hash between a specific message and a random message

I am studying for Security+ and I find this question repeated with the same answer: A without explanation which I believe wrong.

I thought pre-image resistance is when given a hash output h, it is difficult to find the input m such that h(m) is irreversible.

While a weak collision test is when given a specific m1, it is difficult to find a random m2 such that h(m1) = h(m2)

And a strong collision test is when given a random m1 and a random m2, it is difficult to output the same hash digest such that h(m1) = h(m2)

So I believe the answer is not even listed. Since that A does not correspond to any of the collision tests definitions and B is typically the characteristic of a hash function, C implies identical messages which also a paraphrase of B and lastly, D closely refers to a weak collision test a specific m1 and random m2.

How could possibly the answer be A? Is this question missing something or am I misguided somehow? Can someone explain to me please.

I believe the answer should be E. Find a common hash between two random messages


texts:
I wasted the last 2 days finding literature and/or some illustrative explanations on how to perform correct multiplications against the MDS-Matrix in Twofish over $\operatorname{GF}(256)$ with $x^8 + x^6 + x^5 + x^3 + 1$.

There seems to be no method - all algorithms I found are using pre-computed MDS tables, which isn't helping me understand it at all.

Could someone provide me with a simple and easy-to-use algorithm for this multiplication?


texts: PRNG that takes input a $n$-bit string and gives output a $2n$-bit string?

texts:
Recently, I'm reading one paper of Boneh and Zhandry. They have mentioned a pseudo random number generator that takes input a $n$-bit string and gives a $2n$-bit string as output. They just used it as a generic construction.
I want to learn specific construction of such kind of PRNG. Please refer me any link or please explain me the construction of such PRG.


texts: I am studying Lamport-Diffie signature scheme. In the lecture present the algorithm  $A'$ for attempting to invert the one way function $f$, where $f$ is used to compute the public key. My question is Why to use this algorithm $A'$ to prove the Theorem 1?, Why I cann't use other any algorithm (for example Grover, or Brute Force)?


texts: How is the 'Algebraic Degree' calculated in the paper about analysing the white-box AES(Chow et al. 2002) by exploiting internal collisions?

texts:
This paper proposed a new attack on the initial white-box AES implementation of Chow et al.

In order to determine the good solution, we use the
particular structure of the function $S_{0}$.
$S^{-1} \circ S_{0} \left( \cdot \right) = P_{0}\left( \cdot \right)\oplus k_{0} $
By definition of $P_{0}$, the above
function has algebraic degree at most 4.

According to this paper, $P_{0}$ denotes bijective mapping on the vector space $\mathbb{F}_{2}^{8}$, which is the combination of two 4-bit input encodings and one 8 $\times $ 8-bit mixing bijection.
Given the next proposed Lemma 2 in this paper, I know the algebraic degree is about boolean function, then I study the boolean function and high-order derivations of Lai 1994.
But I still can't understand why the algebraic degree at most 4 by definition of $P_{0}$?


texts: Distinguish between cipher-texts of text-book RSA and RSA/OAEP

texts: Is there is a possibility to identify from cipher-text that, this is been encrypted using a text-book RSA or RSA with OAEP padding. (By looking at the cipher-text only) ?


texts:
Basic Station-to-Station protocol which authenticates Bob and Alice if they safely shared their long-term asymmetric public keys.

Alice sends Bob her public key $A_K$
Bob receives $A_K$ and computes the shared secret key $K$
Bob signs with his long-term key $S_B(\mathit{B_K, A_K})$ and encrypts $E(S_B(B_K,A_K), K)$ using AES 128 GCM
Bob sends Alice $B_K, E(S_B(B_K,A_K), K)$
Alice computes $K$, decrypts $E(S_B(B_K,A_K), K)$ and verifies the sig. using Bob's long-term public key
Alice signs $S_A(\mathit{A_K, B_K})$, encrypts $E(S_A(A_K,B_K), K)$ and sends the resulted ciphertext
Bob decrypts $E(S_A(A_K,B_K), K)$ and verifies sig. $S_A(\mathit{A_K, B_K})$ using her long-term public key

I have three questions.

Before Bob computes $S_B(\mathit{B_K, A_K})$ does he hash $B_K$ and
$A_K$ using $SHA256$ for example so Alice can hash them herself and compare the hashes?
Does Bob use plain $K$ for encryption or does he use a key
derivation function like $HKDF$?
If Bob uses $HKDF$ can he include the salt at the end of the data he
sends to Alice?


texts: How expensive would running a practical application on full homomorphic encryption be?

texts:
This is a multidisciplinary question, hopefully I can stay on topic.
It has been published that we can now use (try?) fully homomorphic encryption computation on cipher text inputs. But I'd like to ask how practical it is to use this technology.
So here's a specific question.
If Alice has a one megabyte text file (like some novel). And Bob wants to provide the service of scanning the text and producing a list of the unique words in the file (useful for search indexing). And Bob wants to provide this service without any access to the underlying file. And the parties want to use something like PALISADE or the Microsoft Homomorphic Encryption libraries. Then what rough order of magnitude would this cost in terms of computer memory and retail cost of executing this on some commodity cloud provider?
Are we talking pennies, US dollars, or something exceeding the world GDP?


texts: How to generate the Keystream from IV+Key in RC4

texts:
So I understand that a keystream is generating from a key and is the length of the message you want to send, so that you can properly XOR every bit. But I'm having trouble finding and understanding the algorithm for creating the keystream from the IV and key.

One idea I had is if you have a message of length 100 and key of length 10, then your IV is 90 bits to cover the rest of the message, and then the key string is just the concatination of IV + key.


texts:
The doc of pycrypto gives an example of using AES in CTR mode:

>>> from Crypto.Cipher import AES
>>> from Crypto.Util import Counter
>>>
>>> pt = b''*1000000
>>> ctr = Counter.new(128)
>>> cipher = AES.new(b''*16, AES.MODE_CTR, counter=ctr)
>>> ct = cipher.encrypt(pt)

I think this isn't safe for encryption of multiple messages with the same key because the counter value defaults to 1. Would it be safe if I do:

iv = os.urandom(16)
ctr = Counter.new(128, initial_value=int.from_bytes(iv, 'big'))

Some articles recommend a timestamp-based nonce (e.g. 64-bit timestamp + 64-bit random value). I was wondering if it's OK to simply draw a 128-bit random value with urandom, and if this implementation is flawless.


texts: Can I find a number, such that the its SHA-256 hash is all-0

texts:
I want to find a number, such that the result of its SHA-256 hash is all 0.
I don't know if this number exists.


texts: Bit decomposing a polynomial in BGV cryptosystem

texts:
I'm having trouble with the BitDecomp subroutine on page 9 of the BGV cryptosystem. I'm focusing on the RLWE instantiation so $R_q = \mathbb{Z}[x]/(x^d+1,q)$. I can't see how BitDecomp works for a vector of polynomial in $R_q^n$, in particular, how the $u_j$'s are in $R_2^n$.

Does it assume that the polynomial is in coefficient representation? Can someone please give an example for $n=1$, and $n=2$?


texts:
Possible Duplicate:
  Using CBC with fixed IV

I am using AES in CBC mode.

For some reasons I have some issues for transmiting the IV. So I am using a fixed IV.

If the first 128bits of the message, change on every message (like a timestamp).
Does that can moderate the issue of having a fixed IV ?


texts:
I'm trying to decrypt a cipher that I suppose has been encrypted with Vigenére.

However I came about the following thought:
The cipher consists of characters from [cghijklmnopqrsuvwxyzABCDEFGIJKLMNOPQRSTUVWYZ0-6+].
My thought: The characters seen in the cipher need to be in the alphabet used when encrypting via Vigenére. However this does not mean that this is the complete alphabet used - for example, the 7 could be present in the alphabet and just not a given result appearing in the cipher (maybe the match never appeared).

The presence of the 7 would affect the characters afterwards as it shifts the table-entries.

Real question: How do I know if I've gotten the right alphabet to start solving a Vigenére Cipher (without known key) if I can't imagine the alphabet at first?
As I see the alphabet used in my cipher isn't a default a-z Alphabet.

Am I thinking too complicated? I think I have a misunderstanding, but can't get rid of it.

I would really appreciate every explanation to clear up my confusion.


texts: How to attack a classical cipher using known partial plaintext?

texts:
I have a ciphertext generated by a classical cipher. I do not know what was cipher used to generate it. I do however have the beginning of the plaintext.

What are the cryptanalysis approaches for classical ciphers?
How do you suggest trying to recover the plaintext in this instance?
How can I leverage the known plaintext to attack the cipher?

I have this ciphertext:

  NUVRRIEZWBRVRFFAPUUKFVRYNQBCINHZKNETUVDVUMRTEANPAFIELBPOANIXLCMEZQETKDKVWBMNCTRVUMRFNTFDGWRUMCSCTHSGKDULRFCNABNCGSNMMGRFNTLOWQRBETZRMUBQYURFRFASANGPEQRFFAFCZACAZCTUBTHKUNEZHPPWSGPNABHZKZQNREANLCHUCZDLMLPUNTMNETDAUINQADUNSUMGETETHFBNMNNONTFBBPOQEMZPETEQUIDTHKNABKDZWBDBRZUSRASUMNIRARETETHFBZKRHPNQFAKRICMGETMULCTCULSLGBIVWBDBIEMUFCUVNUGPINFBQTMPNUMSRNNANTNANCMNNTFUMUKRILRFFAPUUKFVRYNTCMETNUVFWDABBRFNRIEFRFNTHGPUHPNKCILEGBUTWUSCPQSLMNIBWQINFBQTFAVRLCKRHKLZNFAZLSNTBDBEASTD

It begins with the partial plaintext:

  it turns out that


texts: Understanding the groups used in bilinear Ate-pairing

texts:
The bilinear ate pairing $e:G_1\times G_2 \rightarrow G_T$ is defined over the following groups:

\begin{equation}
\begin{aligned}
& G_1 = E(\mathbb{F}_p)[r] \cap Ker(\pi_p-[1]),  \\
& G_2 = E(\mathbb{F}_{p^k})[r] \cap Ker(\pi_p-[p]),  \\
& G_T = \mathbb{F}_{p^k}^*/(\mathbb{F}_{p^k}^*)^r,
\end{aligned}
\end{equation}

where $E(\mathbb{F}_{p^k})[r]$ is  $r$-torsion points of elliptic curve $E(\mathbb{F}_{p^k})$, $\pi_p$ is the Frobenius endomorphism and $[n]$ is the scalar multiplication of a rational point $n$.

I'm having trouble understanding the structures of the groups. Especially I'm confused with this mapping $\pi_p-[n]$ and the notation $\mathbb{F}_{p^k}^*/(\mathbb{F}_{p^k}^*)^r$ as whole. Further explanation, why the groups are like this and other discussion is also welcome. Thanks in advance.

Source: Implementing Cryptographic Pairings over
Barreto-Naehrig Curves.


texts: Complexity leveraging in case of exponentially many hybrids

texts:
Complexity leveraging is a proof technique in cryptography where the reduction algorithm runs in super-poly time. (see this). Many papers use complexity leveraging when there are exponentially many hybrids. Here is an example.

Suppose, we need to prove that two experiments $Expt \;0$ and $Expt \;1$ are computationally indistinguishable. Then, we come up with a sequence of hybrids $Hybrid \;1, Hybrid \;2, \ldots Hybrid \;N$ and prove

$Expt \;0 \approx_c Hybrid \;1$ assuming, say, one way functions.

$Hybrid \;i \approx_c Hybrid \;i+1$ assuming one way functions.

$Hybrid \;N \approx_c Expt \;1$ assuming one way functions.

If $N = poly(\lambda)$, then $Expt \;0 \approx_c Expt \;1$ assuming one way functions.
How to apply complexity leveraging argument if $N = 2^\lambda$? (Here there are many reduction algorithms each running in poly time).


texts: Questions about Symmetric Encryption part of TLS

texts:
In TLS, we use DHKE for establishing the session key & then encrypt the actual communication with session key using symmetric encryption. While reading about DHKE, I learnt that you could use the key as a AES Key & encrypt the session with AES. Or you could use something like Elgamal encryption.
So in practice, what is used more commonly? Is it something like AES or is it something like Elgamal?
AES seems to be quite complicated as compared to Elgamal - Elgamal is just multiplication with the key modulo. So how come it provides security comparable to AES with all it's s-boxes, p-boxes etc? Is it because for every message a new session key is used with Elgamal?


texts: What operation does $\|$ denote in ANSI X9.63 KDF?

texts:
Can someone tell me in laymens terms what this is?

$$K_i = \mathrm{Hash}(Z \| \mathit{Counter} \| [\mathit{SharedInfo}])$$

What do the double pipes represent?


texts: How do TLS 1.1 and 1.2 generate IVs (initialization vectors) for each record?

texts:
According to RFC 4346

  Explicit IVs

  [CBCATT] describes a chosen plaintext attack on TLS that depends on
     knowing the IV for a record.  Previous versions of TLS [TLS1.0] used
     the CBC residue of the previous record as the IV and therefore
     enabled this attack.  This version uses an explicit IV in order to
     protect against this attack.

How are the IVs generated in concrete implementations? (like openSSL, BouncyCastle)


texts: Scalar multiplication with projective coordinates

texts:
I'm implementing point addition, doubling and scalar multiplication using projective coordinates. I took reference from this link https://www.nsa.gov/ia/_files/nist-routines.pdf

I have implemented

Routine 2.2.6(ec_double)

Routine 2.2.7(ec_add)

Routine 2.2.8(ec_full_add)

Routine 2.2.9(ecc_full_sub)

They all are working and I have verified the results with the example results given at the last for P-256 curve.

I implemented Routine 2.2.10 ec_mult(Scalar multiplication) But I couldnt get the correct output. In line 15 and 16 of this routine they take the binary representation of d(random number) and 3d. And the loop skips both MSB and LSB and performs the operations.

I got doubts like that 3d is modular multiplication or simple multiplication?. The loops runs for d or 3d if its not modular multiplication?

Is there anything else I'm missing out?. If somebody has followed this algorithm and implemented it please help me out here.


texts: I cannot get the meaning of "check s-box"

texts: In second lecture of cryptography, we had a lecture "Block cyphers" and teacher gave me  permuted array of numbers 1...10 and letters "a"..."f" and asked me to find XOR profile. But I do not have any idea what I need to do and do not get what XOR table,s-box is. Could you give me a fundamentals(basics) to understand, what we are doing, I could not get information from google.


texts: How many passwords are possible in this scenario?

texts:
A password string consists of one or more of the 26 characters A..Z and can be of any length from $1$ to $8$ characters. How many password are possible in this scenario?

As my calculation, it should be  $2^{26}\times8!$, is it correct?


texts:
I can't find out how to break 1 round of feistel network (obtaining the key).

I understand why this equation takes place:

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

EDIT: The function f looks like this:

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

I saw it's possible in a few references:

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

Thanks!


texts: How does a dishonest verifier affect plausible deniability of the interactive Schnorr protocol?


texts: Need help understanding this exercise's solution

texts:
We were given this exercise, which asks us to identify the types of keys used on this diagram:

The solution was

Kxa -> A's private key

Kya -> A's public key

KxB -> B's private key

My question is, how is it possible that B knows the contents the first message coming from A since it was encrypted with A's private key ?
Also, B replies back to A encrypting the message with A's public key which is encrypting a message using B's private key.. I thought private keys were meant to be used to decrypt messages ecrypted by public keys.

I dont understand how come they know each other's private keys.


texts:
What is Gimli, and how does XooDoo compare to symmetric ciphers such as AES or ChaCha?

I am looking at this library, called charm.

Interesting paper here.

I also note the paper on XooDoo here.

There were no questions on XooDoo on this site, so I'm really interested to have peoples thoughts.

How do these 'permutation' based ciphers compare with standard symmetric ciphers?


texts: What is significance of recovering the chaining value of a hash compression function?

texts:
What is significance of recovering the chaining value of a compression function, when the message and its output are known? in other words, if a compression function $CF$ takes a chaining value $h_{in}$ and a message $m$ as inputs and outputs $h_{out}$.

$h_{out}=CF(h_{in}, m)$

Is it a bad property if given $m$ and $h_{out}$ to recover $h_{in}$?


texts: Is there a crypto function that would take 1 second to run?

texts:
Short version of the question: what if we encrypt or decrypt by running SHA-256 one million times repeatedly, beginning with the initial "phrase" or "object", so that the operation can take 1 second, won't take prevent hacker's brute-force attempts?

Details:
If the system has an encrypt and decrypt system that would first SHA-256 "abcde" first, and then SHA-256 on that result, for 1 million times, to see if the result matches with the stored encrypted-one-million-time token, then the hacker can try the system beginning with "aaaa" but not practical to try it until "zzzz", even if the password is just 4 characters long (such as a password for the PC or Mac).
I think one way hackers try to hack into a computer or system is that they just try most popular passwords or just passwords starting with a to z, aa to zz, ..., aaaa to zzzz.
So then, if the crypto function is designed to take at least 1 second to finish, won't that stop that brute-force attempt?
Otherwise, the hacker can try 500,000 possibility per second, and it doesn't take much effort.  Some system actually stops for 1 second between attempt (such as Unix login prompt), but it doesn't stop it if it is not through some UI interface for that 1 second delay.


texts: How to generate a random polynomial of degree $m$?

texts:
I am trying to do a homework in which implement a variation of this paper and I don't know how to generate a polynomial of degree $m-1$. This polynomial is used to generate the $y_0$ and $y_1$ values.

I am using JCE for doing the coding. What do I need to do to achieve this?


texts: Is it possible for this tweakable block cipher scheme to be secure for more than $2^\frac{n}{2}$ blocks? $2^{n}$ blocks?

texts: In the title, $n$ is the block size in bits and will not be used to denote it in the body of this question unless otherwise stated. Imagine that we have $\mathbb{K} \in \{0, 1\}^{\ell_{K}}$, $\mathbb{T} \in \{0, 1\}^{\ell_{T}}$, and $\mathbb{X} \in \{0, 1\}^{\ell_{X}}$, $E(K, T, X): \mathbb{K} \times \mathbb{T} \times \mathbb{X} \rightarrow \mathbb{X}$, and $D(K, T, X): \mathbb{K} \times \mathbb{T} \times \mathbb{X} \rightarrow \mathbb{X}$. We have a tweakable block cipher where the encryption of a block of data is returned by $E(K, T, X)$, the decryption of a block of data is returned by $D(K, T, X)$, $K$ is the secret key, $T$ is the tweak, and $X$ is the block of data. Suppose that this tweakable block cipher is meant to be used in such a way that $T$ is equal to the block number. If $\ell_{T}$ is sufficiently large, then will the maximum number of blocks that can be encrypted under this scheme be equal to or possibly even greater than $2^{\frac{\ell_{X}}{2}}$ or even $2^{\ell_{X}}$?


texts: Does the authentification in GCM serve the same purpose as CRC32?

texts:
The purpose of the authentification is to ensure the data integrity. Let's just focus on the authentification part of the GCM which is using the Galois field multiplication to create an authentification tag. Eventually, this tag will be verified on the receiver side.

Say today I already have a CRC32 scheme that used in my system. May I know if they are serving for similar purpose. I do read some article saying, the hacker is able to alter the data which can still result the same CRC computed value in the end.

Does this mean Galois Field multiplication is doing better job for this?


texts: 8th SharifCTF — What is the advisable way to recover the key of single round DES here?

texts:
I am participating in the 8th SharifCTF competition and have a related question:

I have 1000 plaintext and its ciphertext, which has been encrypted with  DES algorithm (only 1 round).

Now, how can I get this 64-bit hexadecimal key?

Can we use a known plaintext attack, or would another attack be more advisable? If, which one?


texts: What's wrong with my security model - or how can it be attacked?

texts:
I'm working on a little personal project where security is very important, and I've thought for a while about the best way to do this. Now I am looking for a little outside help on good practices. The goal is to store personal text data on a server (like wifi passwords, etc) and be obtained through a password. I wanted to make user accounts for a few friends so that we each could securely store text snippets and retrieve them without the others knowing them. Here's my data structures:

// Account
- Username
- Password
- Salt

// StoredData
- Title
- Info
- User

Okay, now the fun part. Here's how I'm obfuscating the data. When a friend creates an account, their username is salted with a salt in the server config files (this is Rails btw, so ENV['SALT']) and then SHA256'd. The password is generated via BCrypt. The only thing I'm not sure about are how many rounds to do for BCrypt so the server stays snappy; right now it's at default for ruby's bcrypt library. A random salt is also saved in the Account for the next step.

Username = SHA256(username + SERVER_SALT)
Password = BCrypt(password)
Salt = BCrypt.generateSalt

When a friend saves their data, it is encrypted using AES-256. So for this, an AES Key is generated using a combination of their plaintext username and password, as well as the salt generated in Account creation. That key is never stored on the server, but created on device at runtime.

         PBKDF2_HMAC_SHA1(secret, salt, rounds)
AESKey = PBKDF2_HMAC_SHA1((usernamepassword), Account.Salt, 20000)
Title = AES-256(AESKey, title)
Info = AES-256(AESKey, info)

Last but not least, every time you login, you are given a SessionKey that enables you to perform any function like editing or creating new data. This SessionKey rolls after every action. So, on login you get S1, then you make a new piece of data and S1 is deleted and S2 is given to you. So on and so forth. Each SessionKey has a one hour time limit as well. Here's my data structure for that:

// SessionKey
- Key (32-bit GUID)
- HashedUser
- ExpirationDate

Also, the whole thing is sent back and forth over SSL, though after the recent revelations I'm not too sure how secure that is anymore. My question to the community is - what am I doing wrong? No crypto implementation is being rolled by me, I'm just using multiple stock implementations. BCrypt is 10 rounds and PBKDF2 is 20,000 right now. Are those high enough for contemporary cryptography and the computer systems I know some people have? Are there any gaping holes? Is the whole thing wishful thinking?


texts: What good is a hash accompanying a program?

texts:
After studying at length about weaknesses in SHA2, length extension attacks, forged signatures, etc. I have to ask why groups like Gnu provide hashes on their program texts?

As long as the public knows how the hashes were generated, a forger could substitute his own malicious code and cook up a totally valid hash for it, so that it would look legitimate.

So it appears that this is "security theater" which looks serious, but has really no way of assuring anything meaningful.


texts: Which element produces randomness in symmetric block ciphers encryption

texts:
Talking about symmetric encryption, I have 3 elements which I keep trying to puzzle together: IV, encryption mode, and padding.

My question really is which of these elements makes the ciphertext be random?

What I believe right now:

Padding:
The padding does not "add" randomness. It only solves the problem of being able to divide the plaintext into the block size defined.

Encryption mode:
Here I have a little bit of confusion. So, lets compare ECB mode with CBC mode.
As far as I know, the problem with ECB is that, for example, if I have two plain text that I want to encrypt:

P1A, P1B
P2A, P2B

where P1A would be the first block of plain text 1.

If P1B and P2B are the same, then C1B and C2B would also be the same, even if P1A and P2A are different. ¿Am I right?
Therefore is easy to "swap" ciphertext blocks of data.

On the opposite side. CBC mode (without details) chains the ciphertext blocks one with another. Therefore, if we apply CBC mode to the last example. C1B and C2B would not be the same.

But.. And here is one of my questions. The mode "by it self", in this case CBC, does not add randomenes right? Because the  ciphertext will always be the same for the same plain text.
Am I wrong? Is there any mode that obtains randomness by itself?

IV:
And at last, the IV, which I think is actually the only element from these 3 which makes the cipher text be random.

How much wrong am I?

Thank you and sorry if I made some mistake with the technical language of crypto.


texts:
I'm quite new to cryptographic systems, and today we discussed entropy at work. Since entropy is used to ensure the difficulty for an attacker to break in, I was wondering if the more time the high entropy value remains the same, the more the system becomes vulnerable.

Is the concept of entropy related with the time (like a logarithm function or else)?


texts: Why is it a bad idea to use a UTF-8 derived symmetric key?

texts:
Given a cryptographically secure series of octets, it is often useful to display this information or store it in a database in a textual format such as hexadecimal.

Why would it be incorrect to take this hexadecimal and encode it with UTF-8 to derive a symmetric key rather than converting from hexadecimal back to the original byte array?

My thought is that it reduces the key space and presents a bias toward where hexadecimal characters fall in the UTF-8 encoding scheme. Perhaps someone can clarify this for me.


texts: Efficiently computing the neutral element in a ring isomorphic to Z/NZ?

texts:
Edited to clarify question

So my question is whether anyone knows of an efficient way to compute the neutral element (I'm gonna call it 1, but the operation doesn't have to be multiplication) in an abstract ring isomorphic to $\mathbb Z/ N\mathbb Z$? More specifically, the scenario is this:

Suppose we have a ring $ R = \mathbb Z/ N\mathbb Z$ (here, the operations are addition and multiplication) and a ring isomorphism $ f: (R,+,\cdot) \rightarrow (S, \triangle, *)$. However, we do not know what this bijection $f$ is. We also assume $N$ is very large, like an RSA-Modulus, and thus factorization is unknown. As has been pointed out, if $N$ is exponentially large, we can't just have a list of the elements, so we will assume that the elements are given through a black box that when invoked outputs an element of $S$, but does not tell us which element of $R$ it corresponds to. The elements of $S$ could, for example, be bitstrings.

D.W. has shown in his answer that if we only have oracle access to $\triangle$ and $*$, the neutral element regarding $*$ cannot be efficiently computed if $N$ can't be factored efficiently. So the question remaining is:

If the operations $\triangle$ and $*$ are explicitly given as a formula, can we always efficiently compute the inverse operation of $*$ and thus the neutral element?

Or are there cases when even having the formula instead of oracle access does not help us?

Here is a short example:

$R$ is $\mathbb Z/ 7\mathbb Z$ with regular modulo-addition and multiplication.
$S$ is $\mathbb Z/ 7\mathbb Z$, $ x \triangle y := x + y - 4 \bmod 7, \ \ \ x * y := (x-4)(y-4) + 4 \bmod 7$.
So in the ring $S, \ e_\triangle = 4$ (we get this through solving $x \triangle e_\triangle = x \forall x \in S \Leftrightarrow x + e_\triangle - 4 = x \forall x \in S \Leftrightarrow e_\triangle - 4 = 0$, or more generally because we know that the order of the group regarding $\triangle$ is 7, i.e. we can take an arbitrary $x$ and compute $ x \triangle x \triangle x \dots \triangle x$ (7 times)).

But what about $e_*$? In this specific example, we can easily solve $x * e_* = x \forall x \in S$ to obtain $e_* = 5$, but we are only able to solve it because this is an easy example.

Thank you for your help :)


texts: How are calculated numbers in AES S-box?

texts:
I have a problem calculating the 0x02 value of the AES S-Box.

I followed the steps descibed in “How are the AES S-Boxes calculated?”, but my answer is not correct.

0x02 is 00000010

Input = 0  0  0  0  0  0  1  0 (LSB First)
Row 0 = 1  0  0  0  1  1  1  1
Bit 0 = 0  0  0  0  0  0  1  0 = 1

Row 1 = 1  1  0  0  0  1  1  1
Bit 1 = 0  0  0  0  0  0  1  0 = 1

Row 2 = 1  1  1  0  0  0  1  1
Bit 2 = 0  0  0  0  0  0  1  0 = 1

Row 3 = 1  1  1  1  0  0  0  1
Bit 3 = 0  0  0  0  0  0  0  0 = 0

Row 4 = 1  1  1  1  1  0  0  0
Bit 4 = 0  0  0  0  0  0  0  0 = 0

Row 5 = 0  1  1  1  1  1  0  0
Bit 5 = 0  0  0  0  0  0  0  0 = 0

Row 6 = 0  0  1  1  1  1  1  0
Bit 6 = 0  0  0  0  0  0  1  0 = 1

Row 7 = 0  0  0  1  1  1  1  1
Bit 7 = 0  0  0  0  0  0  1  0 = 1

LSB is 11100011, MSB = 11000111, than (XOR) to the final vector 0x63,
the result is 0xa4, but it should be 0x77

What am I missing or what might I be doing wrong?


texts: "Security" of SHA functions (Wikipedia), what does it mean?

texts:
Wikepedia's table Comparison of SHA functions mentions "Security(bits)" for some SHA functions. From the ratio (Output size (bits): Security(bits)), I feel it is something like "collision resistance". So,

Should we only consider collision resistance as the Security of a hash function?

what does the Security in the table mean?


texts:
Sigma protocol to prove that the prover knows how open a commitment.

Consider the unconditionally hiding commitment scheme based on discrete log, i.e., the public key $p_k = (p,g,y)$, where $\langle g \rangle = Z_p^*$ is a generator and $y \in Z_p^*$.

To commit to a bit $b$, we proceed as follows: $c = \text{commit}(r,b)_{p_k} = y^bg^r \bmod p$.

Now, I want to design a $\Sigma$-protocol to prove that the prover knows how to open $c$, where the challenge should be a single bit $e$.

Here the witness $w=(b,r)$ is input only to $P$, while $x = (p,g,y,z)$ is input to both $V$ and $P$.

Recall that conversations in a $\Sigma$-protocol are $(a,e,z)$.

My initial attempt is to make $P$ send a random commitment as $a$, and then ,depending on whether $e=0$ (or $e=1$), send some $z$ back to $V$.

However, I've trouble determining the $z$ and prove soundness.


texts:
Any advice would be appreciated:

It seems to me that using an uncomplicated combination of a shamir scheme and schnorr it's fairly trivial to have a threshold signature scheme.

I think it's also easier than other scheme's I've read about, and also probably more secure.

Is there some reason this construction doesn't work?

Summary:

M participants roll a random "share" (private key)
Interpolation in the exponent of public keys to produce combined public key
Signing of a message M is done using Schnorr on each "share"
Signatures are combined using Shamir interpolation
Verification via standard Schnorr

Long winded description:

https://medium.com/@simulx/an-m-of-n-bitcoin-multisig-scheme-e7860ab34e7f


texts: In cryptography, what is "fractionation"?

texts:
I understand how fractionation is used in the straddling keyboard, which is an important feature of the VIC Cipher, and in the Polybius Square of the ADFGVX cipher, but I am not sure how to describe its cryptographic function and benefit.

It helps spread the redundancies of the plaintext over the ciphertext, and that is diffusion. In doing so, it increases a message's uncertainty.

But on the face of it, fractionation also looks like a kind of substitution.

What exactly is fractionation, and what can it achieve in terms of information theory?


texts: Formal Information-Theoretic Key Expansion Definition

texts:
Is there a formal definition for a protocol that expands keys that are pre-shared among 2 or more parties?
How about an informal definition?

Example:

Alice and Bob pre-share a $n$-bit string $k$.  After running algorithm $\Pi$ Alice and Bob have a common ($n$+$q$)-bit string $k'$, where $q>0$.  In addition Eve learns nothing about $k$ or $k'$. Eve is an an eavesdropper on the channel between Alice and Bob with unlimited computational power.  i.e. If $P_x$ are the odds of Eve learning $x$ then $P_k\le \frac{1}{2^n}$ and  $P_{k'}\le \frac{1}{2^{n}}$.


texts: Why is the public/private key length used in libsodium so much shorter than needed for RSA

texts:
Reading the libsodium source I see that is uses a key length of 32 bytes (256 bit) for private/public key encryption.

For RSA private/public key encryption a key length of 2048 (or 4095) bit is suggested.
Why is the key length in libsodium so much shorter? Is the used algorithm so much more "efficient"? Or is there something I am missing?


texts: How much can we compress RSA public keys?

texts:
I am wondering to what degree we can define an RSA variant, with a security argument that it is as safe as regular RSA with a given modulus size $m$ (e.g. $m=2048$), in which the public key has a compact representation of $k \ll m$ bits.

We can fix the public exponent to our favorite customary value, e.g. $e=2^{16}+1$ or $e=3$, thus need to store only the public modulus $n$. We need not store the leftmost bit of $n$, which is always set by definition; nor the rightmost bit, which is always set since $n$ is odd. With a little effort, we could save (very) few more bits noticing $n$ has no small divisors, but that will still be $k \sim m$ bits.

We can do better by forcing the $\left\lfloor m/2-\log_2(m)-2\right\rfloor$ high bits of $n$ to some arbitrary constant such as $\left\lfloor\pi \cdot 2^{\left\lfloor m/2-log_2(m)-4\right\rfloor}\right\rfloor$.
Observe that we can chose the smallest prime factor $p$ of $n$ just as we would do in regular RSA, then find the maximum integer interval $[q_0,q_1]$ such that any $q$ in that interval cause $n=p\cdot q$ to have the right high bits, then pick a random prime $q$ in that interval (most often there will be at least one, if not we try another $p$).
Some of the security argument is that

generating an RSA key $(p,q')$ using a regular method, with random huge primes in some appropriate range and no other criteria beside the number of bits in $n'=p\cdot q'$, and $p<q$;
then deciding the high bits of $n$ from those in $n'$;
then finding $[q_0,q_1]$, generating $q$ as a random prime in that interval, and setting $n=p\cdot q$;

demonstrably gives the same distribution of $(p,q)$ as said regular generation method, hence is as secure; then we remark that the high bits of $n$ are random (with some distribution not too far from uniform), and public, thus fixing it can't much help an attack (I think this can be made rigorous).

This is now $k \sim m/2+\log_2(m)$ bits to express the public key. We can save a few more bits, each one at worse doubles the amount of work to generate the private key (we can repeat the generation process outlined above until we find a key with these bits equal to some public arbitrary constant; or equal to bits from a hash of the other bits if we want a tighter assurance that the scheme is not weakened).

Can we do better, and what's the practical limit?

Update: In RSA Moduli with a Predetermined Portion: Techniques and Applications, Marc Joye discuses this, and reaches $k \sim m/3$ (without claim of optimality). I'm worried that I do not see an argument that the manner in which $(p,q)$ are selected in Algorithm 3 does not weaken $n$ against a dedicated factoring algorithm.


texts:
A few months ago, XKCD posted a challenge to find a plaintext which hashed (using Skein 1024 1024) to a specified value. Inputs were scored based on the hamming distance between the hash of the specified input and the desired hash.

The top scorer, from Carnegie Mellon, found a plaintext whose hash matched all but 384 bits of the desired hash.

I also tried competing in the contest. I used brute force and just hash many sequential values and submitted the best one I could find. I didn't come close at all. As I expected, it was easy to drop the first few bits and get it down to the mid 400s, but each improvement was harder than the one before.

Is there a better way than brute force? When I was competing, I figured that the Skein hash function seemed pretty secure and that I wouldn't be able to find any weakness to speed up the process. Now I'm doubting that the winner could score so well with brute force, even with immense amounts of computing power.


texts: Can the access policies defined using different access structures (Monotone Span Program and Access Trees) be used together in CP-ABE scheme?

texts:
In order to add authentication features to this CP-ABE scheme, I have tried to combine it with the ABS scheme proposed by Maji et. al.

I want to use the sign() and verify() algorithms of ABS scheme. But the problem is that the two scheme support different access policy structures; CP-ABE uses access trees to define access policy whereas the ABS uses monotone span program (MSP).

What changes are necessary for the two access policy structures to work together? For example, can I translate an MSP access policy to an access tree?


texts: Do we always use Sophie-Germain primes $1\bmod 4$?

texts: A prime $p$ is Sophie Germain if $2p+1$ is also prime. Wiki says if $p\equiv3\bmod4$ then $2p+1|2^p-1$. This seems to put a huge restriction on density of Sophie-Germain prime if they are $3\bmod4$. For this reason do all systems use Sophie-Germain primes with $1\bmod 4$ for discrete logarithm?


texts: What does the expression $1^n$ mean as a function argument?

texts:
In a paper about predicate encryption or attribute based encryption, the setup function is mentioned with the $setup(1^n)$ or $setup(1^l)$. I want to know what is meant here.

Is it multiples of ones or representing something else?
Also, why is this used here?


texts: What is wrong with simple concatenation in salted password hashes?

texts:
I once heard that if implementing a password hashing scheme, simply concatenating the password and salt together before hashing could lead to some subtle vulnerabilities, and I'm trying to figure out if this is actually the case.

According to this anecdote, the following should not be used:

hash(salt + password)
hash(password + salt)

And instead, something similar to an HMAC, like the following, should be used:

hash(hash(password) + salt)

Even though simple concatenation is vulnerable to length extension, I can't think of a way that could ever be useful to an attacker.

Is there any merit to this anecdote?


texts:
There are many Fully Homomorphic Encryption over the Integers schemes whose security is based on the intractability of the Approximate GCD (AGCD) problem.

The paper Algorithms for the Approximate Common Divisor Problem surveys several lattice reduction based algorithms for solving AGCD. All of them require $t > \frac{\gamma - \eta} {\eta - \rho}$ samples to solve the $(\gamma, \eta, \rho)$-AGCD problem by reducing a particular $t \times t$ lattice.

In Section 5.2 of Fully Homomorphic Encryption over the Integers, the authors state a "rule of thumb" that lattice reduction algorithms acting on a $t \times t$ lattice take time roughly $2^{t/k}$ to output a $2^k$ approximation of the shortest vector.

However, LLL lattice reduction is known to run in polynomial time with respect to both the dimension of the lattice and the input sizes. Concretely, for the DGHV scheme where $(\gamma, \eta, \rho)$ ~ $ (\lambda^5, \lambda^2, \lambda)$, a quick estimation yields that $L^2$ lattice reduction can break DGHV in time $\lambda^{25}$ with memory $\lambda^{11}$ given $\lambda^{3}$ samples.

So why does the aforementioned paper treat the runtime of lattice attacks on AGCD as exponential?


texts: How to implement homomorphic multiplication for Elgamal?

texts:
I want to add the homomorphic property to Elgamal in libgcrypt.

This is the core code I added to the library.

static void
do_homo_mul (gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t data1_a, gcry_mpi_t data1_b, gcry_mpi_t data2_a, gcry_mpi_t data2_b, ELG_public_key *pkey)
{
  mpi_normalize (data1_a);
  mpi_normalize (data1_b);
  mpi_normalize (data2_a);
  mpi_normalize (data2_b);

  mpi_mulm (a, data1_a, data2_a, pkey->p);
  mpi_mulm (b, data1_b, data2_b, pkey->p);
}

But I cannot get the right result. What is wrong with my code?


texts: What is the principle of linear cryptanalysis, as applied to a block cipher ? For instance, this page gives the rough outline of differential cryptanalysis.


texts: Is it possible to decrypt the 2nd byte of AES-256-CFB-8 ciphertext without decrypting the 1st byte?

texts:
I am stuck with AES-CFB decryption.

Assume I encrypted plaintext helloworld (10 bytes) using AES-CFB.

Now I want to decrypt the second byte e individually, that is I don't want to decrypt the first bytes or any other bytes except the second one.

Is it possible to do that without decrypting the first byte?

I did my fair share of research and even tried several practical approaches to find an answer myself, but somehow I’m stuck.

In case it helps answering my question, here’s what my latest attempt looks like (think of it as “pseudo-code” as I’m definitely not asking an off-topic question related to the code itself):

char *key = "whatever";
char *data = "helloworld";
unsigned char out_cipher[10], out_plain[10];
unsigned char iv_enc[AES_BLOCK_SIZE], iv_dec[AES_BLOCK_SIZE];
RAND_bytes(iv_enc, AES_BLOCK_SIZE);
memcpy(iv_dec, iv_enc, AES_BLOCK_SIZE);
AES_KEY enc_key, dec_key;
AES_set_encrypt_key(key, 256, &enc_key);
AES_set_encrypt_key(key, 256, &dec_key);
AES_cfb8_encrypt(data, out_cipher, 10, &enc_key, iv_enc, &num, AES_ENCRYPT);
AES_cfb8_encrypt(out_cipher + 1, out_plain + 1, 1, &dec_key, &out_cipher[0], &num, AES_DECRYPT);

But even trying to approach this programmatically didn’t help me grasp this. Sure, I managed to retrieve an answer. Yet, it was clearly wrong because the 2nd byte of the decrypted plaintext differs from the original plaintext.

As I’ve now run out of ideas on how to find the answer to my question, I decided to ask here hoping someone can enlighten me if it is possible to decrypt the 2nd byte of an AES-CFB ciphertext without decrypting the 1st byte? Or maybe am I missing something else?


texts: Can Secp 256 K1 curves "map" to a value on FIPS 186-3 or P-256?

texts:
I'm looking at Secp 256K1 vs UProve's FIPS 186-3 or P-256 implementation.  Is there any relationship between the curves such that I can consistently "map" or "project" values from one curve to another?

Is this a good idea?  (What faults could crop up when doing so?)

My goal is to allow for two independent crypto systems based on ECDSA or subgroups to share the same keys via a conversion of some type


texts: How long will brute force of salted SHA-512 hash will take, if salt is known and possible characters in password are known?

texts: Suppose I know that the password is composed of characters [A-Za-z0-9], length is unknown, but maybe less than 8. If I have information about the salt use to perform hashing, and also hashing algorithm(SHA-512) is known, how long will brute-forcing the password will take? what is the mathematical relationship with time for password lengths = 1,2,3,4,5,6,7,8?


texts: Is it possible to decrypt an RSA ciphertext with only $N$ and $e$?

texts:
Is it possible to perform RSA decryption if one only knows $N$ and $e$?

Failing that, what is the maximum key length where brute-force is still practically feasible?


texts:
In this protocol:

A → B : { <[A, {K}pk(B)]> }pk(B)
B → A : { <[B, {K}pk(A)]> }pk(A)

I'd like to determine why this is insecure.  How can the attacker learn the key K if A and B are both honest agents?

This is what I have started with:

A → B : { <[A, {K}pk(B)]> }pk(B)

An attacker M can intercept this, however M cannot decrypt this.  M sends it to B so B thinks the message is coming from M:

M → B : { <[A, {K}pk(B)]> }pk(B)

Then I run into the problem that A's identity is still in the message.  When B decrypts, he will realize that D and A do not match, and end the session.

Any help, hints, or advice would be appreciated! Thanks!


texts: How to forge Schnorr signatures if you can guess the challenge

texts:
Underlying the Schnorr signature is an identification protocol:  let $G$ be a cyclic group where discrete log is "hard" and choose $g$ as a generator of $G$.  Now have Alice pick a random (secret) exponent $s$ and publish $v=g^s$.

To identify herself to Bob, it goes like this:

Alice chooses a random exponent $r$ and sends $g^r$ (commits $r$)
Bob sends random exponent $e$ (challenge $e$)
Alice sends $r + se$
Bob makes sure $g^r = g^{r + se}v^{-e}$

That's all well and good, but what if a cheating prover can guess $e$?  Then how does he fool Bob?


texts:
This is from Dan Boneh's book
4.5 Constructing block ciphers from PRFs
Let F be a PRF, defined over $(K, X, X)$, where $X = \{0, 1\}^n$. We describe a block cipher $\varepsilon = (E, D)$ whose key space is $K^3$, and whose data block space is $X^2$.
Given a key $(k1, k2, k3) \in K^3$ and a data block $(u, v) \in X^2$, the encryption algorithm E runs as follows:
(snipped)

What exactly is  $K^3$ & $X^2$ here? Why has the KeySpace been cubed & the datablock space been squared?


texts:
How can i generate ec curve25519 keys using openSSL?
When I run

openssl ecparam -name curve25519 -genkey -noout -out private.ec.key

I have this message

unknown curve name (curve25519)


texts: MAC providing sender authentication (follow up question)

texts:
I was looking at the responses posted on the following question: How is digital signature different from a message authentication code (MAC)?

I read the following comment to the first answer:

  So simply speaking, MAC cannot be used to verify sender authentication because it only protects the message integrity. Alright, thank you so much

This triggered a question, what if the key used for the MAC came from an authenticated key agreement?

Both parties would have been able to verify the public keys of each other during the key exchange. So this means that all derived keys from that key agreement are implicitly also authenticated. Meaning that the calculated MAC tags using that key provide message authentication and also provide sender authenticity. And can't seem to find something wrong with this logic.

A second question, is there a security reason why then not
to use the public and private key pair to calculate digital signatures on the messages? Instead of using the MAC?