texts: Finding subgroup in elliptic curve over finite field $ \mathbb{F}_{11}$

texts:
For elliptic curve $ y^2 = x^3 +3x+7$ I found the finite group $ E(\mathbb{F}_{11})= \left\{ \mathcal{O}, (1,0),(5,2),(5,9),(8,2),(8,9),(9,2),(9,9),(10,5),(10,6) \right\}$.

I have to find a generator of a subgroup of $ E(\mathbb{F}_{11})$, but for every point $P$ in $ E(\mathbb{F}_{11})$ when I try to calculate $[2]P$ I get a rational number. Am I doing something wrong?

For example if $P=(5,2)$ then by the formula $x([2]P)={(\frac{3x_1^2+a}{2y_1})}^2-2x_1$, where $a$ is the coefficient next to $x$ in the elliptic curve, and $x_1$ is the first coordinate of $P$ and $y_1$ is the second. But here I get $x([2]P) = (\frac{3*25+3}{2*2})^2-2*5 =(\frac{39}{2})^2-10 $. Should I just ignore the denominator and use $(\frac{39}{2})^2-10 =\frac{1521-10*16}{16}=\frac{1361}{16}$ and the answer for $x$ would be $1361$ mod 11$= 8$?


texts: BLS signatures in the G-valued Random Oracle Model

texts:
This paper on semi-generic algorithms considers

"non-standard properties of the employed hash function".

For BLS signatures whose main group is $G$, I'm curious what can

be shown when the hash function is a $G$-valued random oracle.

Is there a known semi-generic attack that is faster than just
ignoring the signing oracle and solving for the private key?

Is there a known lower bound for generic attacks that is better than the

bound that follows from the reduction to computational Diffie-Hellman?


texts: Can perfect forward secrecy introduce vulnerabilities?

texts: Is it always a win or could PFS algorithms introduce new attack vectors or weaken the level of secrecy vs not being used?


texts: Cryptographic properties of field multiplication

texts:
While reading about AES-GCM, I discovered there is a multiplication over $\operatorname{GF}(2^{128}$). My question is about its cryptographic properties, such as:

Take a random element $X$ from $\operatorname{GF}(2^{128}$) (which is not $0$ or $1$). Multiply it with a constant $Y$ (say, the plaintext, which is defined over the same field, $Y\neq 0$). Given the product $XY$, is it possible to recover $Y$ (or some non-trivial information about $Y$)?
If the product $XY$ satifies some regularity condition (such as $XY=1$), is it possible to gain information on $Y$?
If multiple conditions like this are given, is it possible to gain information on $Y$? I mean, say for randomly chosen $X_i$'s, the product $X_iY$'s are given.

If the above problems are hard to solve, probably finite field multiplication can be used as a method for masking countermeasure for side channel (at least theoretically).


texts: Seeking clarification of OTP & MAC discussion

texts:
I refer to the question for-a-one-time-pad-which-mac-method-is-information-theoretically-secure, and specifically the exchange between lightspeeder & kasperd.

I've found the discussion a little advanced, but can I infer that:-

Any hash can be used for message authentication, including MD5?
The MAC tag must be encrypted with the OTP?
The size of the hash only affects the probability of a successful forgery?
The inherent security proof of a OTP is maintained even by appending a MAC to the plain text, then encrypting?

Can anyone confirm (hopefully) my interpretation?


texts:
I would ask you some questions about users' password storage in a login system.

What algorithm do you suggest me to use? bcrypt or PBKDF2?

I was looking for a way to implement them client-side and i thought this way:

The client computes 10.000 iteractions of user's password with PBKDF2 and username (or email) as SALT and the server will store in the DB the salted SHA-512 digest of the PBKDF2 result.

Is it a good way?
Is client-side key stretching good in general? Does it have some disadvantages compared to the server-side implementation?
Is there a better way to implement PBKDF2 client-side?
And what about bcrypt?
If I use bcrypt server-side, what's the best way to add a pepper?
Adding pepper has some disadvantage?


texts:
I'm reading the paper “Collision-Resistant Hashing? Towards Making UOWHFs Practical” which states:

  While it might be easy to find a collision $M,M'$ in $F_K$ by making both
  $M,M'$ depend on $K$ (Any Collision Resistance), the adversary may be unable to find collisions if she
  is forced to commit to one point of the collision before seeing $K$.
  We call this weakened notion of security target collision resistance
  TCR

nb: $K$ is a key used to a hash function $F$.

My question is: Why then TCR is a weakened notion if the article says that it is easier to find a collision $M,M'$ than TCR?

My other questions related to the same paper:
Dependence on Keyed Hash Function • No Birthday Attack to TCR • Weaker Notion of Target Collision Resistance


texts: Can Grover's Algorithm be combined with a meet-in-the-middle attack?

texts:
We all know and love the meet-in-the-middle attack, which basically makes double encryption pointless using a time-memory trade-off. Now, the NSA recently recommended to use double encryption to adequately protect sensitive data from quantum attackers.

This made me ask myself:

Can one combine Grover's algorithm with the MITM attack to make double encryption "pointless" in the quantum setting?

Example:
The classical strength of double AES-256 encryption is 257-bits and $2^{256}$ storage. Using Grover's algorithm to attack the full cipher would take $2^{256}$ time. Can this time be reduced using a MITM trade-off and a quantum computer?


texts: Recovering key in AES - Infinitely many known plaintext ciphertext pairs

texts: Is it possible to recover key/algorithm in AES encryption more efficiently than via brute force given attacker has access to arbitrarily many plaintext ciphertext pairs. If so, are there other known techniques which are secure even in the scenario of arbitrarily many known ciphertext plain text pairs?


texts:
Can an SHA-256 plaintext be malleable? For example:

Given $y = hash(x)$ , can an attacker find $z$ so that $z = hash(f(x))$. Here $f()$ might be the addition of a suffix to the message, an XOR operation, or any other mathematical transformation.

I know there is one known malleability weakness shared in Merkle-Damgard constructions:

Given $hash(x)=y$, it is trivial to find $hash(x\mathbin\| s)=y'$ in which $\mathbin\|$ denotes concatenation. The attacker does not need to know what $x$ is. This is also known as a length extension attack.

Are there any other known examples of SHA256 hash malleability aside from the length extension attack? For instance, given $hash(x)=y$, can I find the output of hash($x \oplus s$) without knowing what $x$ is?

EDIT:
A fellow contributor provided me with this link: What type of hash functions provides non-malleability of hash digests?
But I don't think this answers my question in detail......


texts: What’s the difference between a secret key and a seed?

texts:
I always hear that if you have the seed then you can easily obtain the key. So, is the secret key just typically an expanded version of the seed? If so, via some key derivation algorithm?

Also, if you can easily obtain the key when you have the seed, why don't we just use the seed as the secret key instead?


texts:
I want to create a file that I could give to 3 trusted friends, and allow any two of them to decrypt it when together (or in sequence when not physically in the same place).  This is similar to a multi-signature crypto wallet, but I just want to do it with a file.

The use case is to create a document that would contain my sensitive passwords, bank accounts, life insurance etc... in the event of death or illness.  I would give it to three people in advance.


texts: What is the exact purpose of length padding in Merkle–Damgård hash functions?

texts: Is a length padding technique in a hash function used to avoid length extension attacks ?


texts: Alternative block cipher design paradigms to SP-networks and Feistel-like ones?

texts:
Before I familiarized myself with the type of cryptography that became popular with the rise of the information age, I was very much into what the community seems to call "classical" ciphers: Caesar shift ciphers, the Vigenère cipher, grilles, scytales, the Playfair cipher, the Enigma machine, and a few other techniques that might not qualify as ciphers. There were two kinds of ciphers, substitution and transposition (there was also a distinction between codes and ciphers). Still, I saw much more variety among cipher designs during that period of my life than after learning the classifications of information age algorithms used by modern cryptographers, like SP-networks and Feistel designs.
After understanding what a Feistel cipher—and all Feistel-like designs—is and what a substitution-permutation network is (before learning this one, I could actually see a little more variety), it seems like all I could up with were designs that fell into either category. Maybe three years ago, I discovered the ARX classification, and I figured that most ciphers that wound up in that those would always be Feistel-like ciphers. Later, I learned of Speck, which has a really unorthodox design (no swapping of the halves after each round). I didn't think of it as a different kind of structure until I saw that the CryptoLUX article on lightweight block ciphers lists it (ARX) as one. It also lists "generalized Feistel network" and "generalized Feistel structure", but I think those can be relabeled as "Feistel-like". And looking back on Speck, it seems like it cannot be classified as either a Feistel-like cipher or an SP-network.
So, my questions are:

Are ARX block ciphers considered there own class of block cipher separate from SPNs and Feistel-like ones?
Are there other schemes out there besides Feistel-like designs, SPNs, and ARX?


texts:
I am studying for a test and I don't seem to understand the Block Cipher and its different modes of operations especially when it comes to encrypting and decryption. Could anyone please help solve these questions?
Block Cipher Mode of Operations. Please refer to the image attached for a diagram of PCBC, a similar mode of operation to CBC.
Input
000
001
010
011
100
101
110
111
Output
111
110
101
100
011
001
000
010
a. Decrypt Ciphertext 001001001001 without using any mode. Your answer:
b. Decrypt Ciphertext 001001001001 using CFB and IV=000. Your answer:
for (a) I am getting 110 110 110 110
and for (b) I am getting 110 001 110 001
But I am not sure if that is correct. My confusion is do I decrypt the ciphertext with the key, XOR it with the IV giving me the Plaintext(PT1)- and then for the next step; I XOR the Plaintext(PT1) with the first ciphertext which will then be used as the input to be XORed with the decrypted ciphertext2? You then basically repeat the process?


texts: Is part of an output of secure PRNG also cryptographically secure?

texts:
Lets say I generate 192 bits using some secure PRNG. If I now take first 128 bits is it equivalent of generating 128 bits in the first place?

P.S. More practical application for me is that I need a machineKey for the ASP.NET, I use IIS UI for it and it generates a string that corresponds to 192 bit key used for AES, but since AES 128 is good enough as well, but faster, I want to take only the first 128 bits.


texts: Shamir's Secret Sharing - Proactive and dealer-free

texts:
I recently started studying about cryptography and I tried to search the internet but I can't find much about these subjects. I want to see the proof of Shamir's Secret Sharing being Proactive and dealer-free .

Later Edit: I found the proof of it being proactive, however I still struggle with the 2nd thing. Basically, if the users know (k,n,p) , how can they compute a secret with none of them knowing it ?


texts: Signature to prove of ownership of arbitrary sized data

texts:
I am familiar with public key signatures, but I was wondering if there is a method to accomplish the following.

Suppose I publish a file (say a PDF article) on a peer to peer network. How can I generate some sort of public key or signature which will allow one peer to prove to another peer that they have a copy of this file? Something like a signature that treats the full data as a private key, and for which I can put the public key on e.g. my website.

The best method I can come up with is using a hash of the file as the private key in a standard signature scheme. However this is suboptimal because a peer might not actually have a copy of the file anyore, it might just have stored the hash but deleted the file itself.

I am looking for a method that I can wrap up in some challenge-response scheme that allows a peer to prove that they have access to a full copy of the file that belongs to a particular public key.


texts:
I want to implement Homomorphic scheme from the paper Fully Homomorphic Encryption over the Integers with Shorter Public Keys.

I successfully implemented key generation by taking $\lambda = 2, \beta = 4, \eta = 4$.

But I am not getting the correct bit after decryption. I think there is problem in encrypting the bit and I am not able to understand how this $2$-dimensional array of $x$ produces $\beta^2$ integers in the encryption function:

$$c = m + 2r + 2 \cdot \sum_{1 \le i, j \le \beta} b_{i,j}\cdot x_{i,0}\cdot x_{j,1} \mod x_0$$

This is code for encryption in which I take an array of 2 rows and $\beta$ columns. Here r is a BigInteger representing a random noise with $4\lambda = 8$ bits, m1 is message, x0 and x[][] are public keys. The random vector b1 is $1$.

Here is the code ---

import java.math.BigInteger;
import java.security.SecureRandom;
public class Encrypt{
    public BigInteger encrypt(BigInteger x0,BigInteger[][] x,int m)
    {
        SecureRandom rnd=new SecureRandom();
        BigInteger r=new BigInteger(8,rnd);//noise 4*λ
        BigInteger two=new BigInteger("2");//constant biginteger of value 2
        BigInteger c=new BigInteger("0");//ciphertext biginteger
        BigInteger summation=new BigInteger("0");//summing x[][] values
        BigInteger b=null,m1=null;//b is random vector and m is message
        int beta=4;//it is  β=√τ
        BigInteger sign = BigInteger.valueOf(new SecureRandom().nextInt(2) * 2 - 1);//used to generate random noise between (-2^ρ1,2^ρ1).
        r=r.multiply(sign).multiply(two);

        for(int i=0;i<beta;i++)  //2 d array with 2 row and beta columns
        {
            for(int j=0;j<beta;j++)
            {
                b=new BigInteger(2,rnd);
                BigInteger b1=BigInteger.ONE;
                b1=b1.multiply(x[0][i]).multiply(x[1][j]);//x[0][0]*x[1][0]+x[0]  [0]*x[1][1]+x[0][0]*x[2][0]+ and so on

                summation= summation.add(b1);

            }
        }
        summation=summation.multiply(two);
        m1=m1.valueOf(m);
        c=c.add(m1).add(r).add(summation);//c=m+2r+2∑x

        //System.out.println("c value "+c);
        c=c.mod(x0);//c=c mod x0
        return c;

    }
}

Any Help Thanks.


texts: Hash chain based secret revealing using homorphic princples?

texts:
I have recently been looking into Homomorphic encryption and I am looking for a specific hash-based encryption/decryption scheme.

I don't need a full implementation but I am not sure if what I want is even possible at all. So I am looking for some direction or explanation on why this is impossible (which is my gut feeling).

So let me explain.
There a third party that generates a merkle tree(MT=root) with N leaves(L).
The encrypting party encrypts a secret(T) with enc(T, MT, Lx) = CT + Decrypt function

The decrypting party publishes CT or a Helper.

Other random parties publish random data that (indirectly) have Hash(CT) in them, creating a hash chain.

Creating HC(Hash(data, Hash(data, Hash(data, Hash(CT))))). The hash chain can be of arbitrary length.

The decryption function should decrypt CT if the leaf is present in the hash chain that is higher then Lx but part of the Merkle tree's root.

So HC(Hash(Lx+N, Hash(data, Hash(data, Hash(data, Hash(CT))))))

In short it means, decrypt if the hash chain, where your 'request' is part of,  contains a reveal with an index higher then when then the secret was encrypted.

The idea is to force the publication of the request data.

Is this even remotely possible or are there components in here that are just straight-up impossible?

Cheers


texts: Malicious KGC attack in the identity-based authenticated key exchange protocol

texts:
There are two users $A$ and $B$ who are in different domain. Let's assume that $A\in KGC_1$ and $B\in KGC_2$. If they want to establish secure session, then they must run an  identity-based authenticated key exchange protocol to get a shared secret key.

To users, they can authenticate each other i.e $A$ is assured that only the user $B$ can learn the session key and vice versa. However, as the domain that the user is in can not authenticate each other(Actually I'm not sure about this), so there may exist a malicious KGC(denoted as $KGC_{\mathcal{M}}$) that will attack the session.

My question are :

Is it possible for $KGC_{\mathcal{M}}$ to impersonate $A$ or $B$ to
communicate with $B$ or $A$ ?
Is there any practical meaning to consider the attack of a malicious
KGC?

P.S As a matter of fact, recently I'm doing something research about this aspect, so I will really appreciate that if someone could do me a favor or offer me some related literature to read further.


texts:
In cryptography, what does the Top notation mean? It resembles a capital T: T

In particular, I saw it in the follwing context:

$c = (c_1,c_2)^\top$

where $c_1$ and $c_2$ are homomorphic ciphertexts


texts: suitable programming language for cryptography algorithms

texts: I know as programming languages C and java , and I know that java is slow so for this reason it is not suitable for cryptography applications espacially low level programming (manipulating bits) , so for this reason I turned to C as programming language but C is difficult in some how especially for GUI (graphical interfaces) , inaddition to this there is no byte type . My question is can we integrate C to java . it means when preparing GUI I use java and when programming the application I use C it is my first suggestion for asking you if it is possible and if we will not have a slow runtime. secondly using delphi ruther than C and java so , please advice me I am in adeadline ,and i must take a decision.


texts: How do I safely encrypt a file for transport and storage?

texts:
So I need to encrypt a file server-side for transport from server to client and storage on client-side. I'm quite confused as to what I have to watch out for, as it seems like it's insanely easy to screw up really bad.
The files I need to encrypt

Are binary
Sometimes contain big areas of null bytes.
Are of medium size, usually < 1gb.
Usually start with the same or similar header, so plaintext will often be the same.
Dont need to be encrypted often, but decrypted often, as they will not be stored decrypted.
Should remain very secure for a long time.

What I thought I could do is to use AES-256 in OCB3 mode, as it seems to provide both authentication and encryption.
I'm however not very sure about how I would go about generating a suitable key from a password.
Is using a simple hash function like SHA-256 secure?
I'm assuming I'll have to store the IV along with the file. Is that correct?
Would AES-256 in OCB3 mode be suitable for this sort of task or is there a better way of doing this?
By the way, I am aware that it's quite easy to read the decrypted file from memory when it's decrypted at client-side, but I'm afraid there's not much I can do about it.
Edit: Both server and client programs are written in c++. I also want to be able to encrypt and decrypt the files just in memory at runtime, so a lot of file encryption tools don't really fit the task.


texts: Simple digital signature example with number

texts:
I've been looking for a simple which signs a number with some randomly generated key and then verified(decrypts the original number) with the public key, which is generated by the private.

All the examples I've found does not feature an example with real numbers, and all the keys/numbers described with a single letter, which is not really that clear.


texts: Show How to Efficiently Solve the Computational Diffie-Hellman Assumption given an Algorithm that Solves the Square-DH Problem

texts: Let $q$ prime number, $G$ a cyclic group with order $q$ and let $g \in G$ be a generator of $G$. Suppose that you have an algorithm $A$ who takes input the element $g^a$ of $G$ and gives as output the element $g^{a^2}$ (i.e., it solves the Square-DH problem). Describe a fast (polynomial time) algorithm who takes as input the elements $g^a$,$g^b$ and gives as output the element $g^{a \cdot b}$ (namely an algorithm that solves the Computational Diffie-Hellman Problem).


texts: Single string producing two different hash results with SHA-256

texts: Is it possible that a single string produces two different hash results after going through the same SHA-256 hash function? The code I'm working on right now is doing this, and I assumed this should not be possible. Any help?


texts:
I was browsing the Wikipedia article on Merkle signature schemes and noted that it says:

The number of possible messages must be a power of two[…]

Why is that? If the nodes of tree are formed by hashing two public keys together by concatenation, why can't three or four be concatenated to form nodes? Also, since the structure does not take the form of certificates that contain a set of public keys signed by another public (root or otherwise), how can new keys be added?


texts: Substitution Cipher vs. Permutation Cipher

texts:
What is the difference between Substitution Cipher and Permutation Cipher?

In a substitution cipher I have seen that there is a random choice of 26 alphabet characters for encryption and decryption and that it can't be broken by brute force attacks because the sample space for key encryption is 2**88 which is very large. Hackers can use frequency analysis to get the encrypted message.

What about permutation cipher, then? What is this and why it comes under poly-alphabetic and substitution comes under mono-alphabetic?


texts: Is it necessary to encrypt nonce in cryptographic communication?

texts:
Server and client have a pre-shared key K. Assuming that that pre-shared key is safe, so nobody other than server/client can encrypt/decrypt.

Client sends a nonce N to server, server then sends back message M in encrypted form AES_CBC_Encrypt(M+N, K, IV) to client. So client can verify if there is a replay attack trying to send an expired message.

Is it necessary for client to send N in encrypted form AES_CBC_Encrypt(N, K, IV) or it is OK to just send N in clear.

M and N are 16-byte array, M+N means concatenation of M and N).


texts: Why is ((m^e mod n)^d mod n) = (m^ed mod n) in RSA?

texts:
$$RsaPrivate(RsaPublic(m)) = (m^e \bmod n)^d \bmod n = (m^e)^d \bmod n$$
$$RsaPublic(RsaPrivate(m)) = (m^d \bmod n)^e \bmod n = (m^e)^d \bmod n$$
why is this always true?


texts: Compromise between HMAC and Digital Signature, by encrypting and sending secret key?

texts:
For achieving stateless authentication tokens (like JWT), is there a compromise between the performance of HMAC, and public key distribution of Digital Signature?

Scenario:

Sender is a centralized authentication server.
Receiver is an
distributed/elastic pool of stateless web services.
The issue I have with HMAC alone is distributing the secret key to the receivers.
Receivers only store Public Key in long-term storage.
The issue I have with Digital Signature alone is the performance for
large messages.

Could the sender somehow generate the HMAC secret key dynamically for each token, and then encrypt it using Private Key?
That way receiver could decrypt HMAC secret key with the Public Key, and then verify the signature.

Something like:

JWT = BASE64(header).BASE64(M).BASE64(HMAC(K,M))
M = Claim || Encrypt(K)

What are the drawbacks?
What are the other approaches to distributing the HMAC secret key with receivers?


texts: Why can ECC key sizes be smaller than RSA keys for similar security?

texts:
I understand how ECC is based on the discrete log problem and RSA on integer factorization. I've read several references that show how a solution to either of these problems can typically be adapted to solve the other - for example, one reference claims:

  The asymptotic running time of the best discrete logarithm algorithm
  is approximately the same as that of the best general-purpose
  factoring algorithm. Therefore, it requires about as much effort to
  solve the discrete logarithm problem modulo a 512-bit prime as it does
  to factor a 512-bit RSA modulus.

Now, I suspect that this isn't true, but I'd like to get a feel for why it isn't true.

For instance, as I understand it, the generalized number field sieve can be applied both to solve integer factorization and to solve discrete log. Why is it that it gives such an extreme speed up in integer factorization compared to brute-force, and less so in improving discrete log?

If the asymptotic running times for both applications are approximately the same, then I'm completely confused. I suspect that I'm comparing the wrong parameters, but how is it that ECC key-sizes can be so much smaller that in RSA?


texts: ECC Curve25519: How to generate this kind of private key? / Strange key exchange mechanism

texts:
I'm currently reverse engineering a program that uses Curve25519 key exchange in network communication. I have only a basic understanding of ECC, so maybe this thing just seems strange to me.

The client generates a private key, derives the public key from it, and sends it to the server. So far, that seems like a normal key exchange for me.

However, the server does not generate a simple public key and sends it to the client. The server generates a key pair and sends the public part to the client.

The client uses this public key and calculates a strange mechanism:

(Uses 25519ref10 - simplified pseudocode)

// The public key the server send to the client
ge_p3 pubkey = ge_frombytes_negate_vartime(THE RECEIVED PUBLIC KEY FROM SERVER);

// Scalarmult the sha512 with the public key from server.
// This seems very strange to me... but its getting stranger.
ge_p1p1 res = ge_scalarmult(THE SHA512 OF THE PUBLICKEY FROM THE SERVER + 8 EXTRA BYTES, pubkey);

// Okay
ge_p3 r = ge_p1p1_to_p3(res)

// This is a hardcoded byte constant in the client binaries.
// The private part of this can also be found in the server binaries.
ge_p3 parkey = ge_frombytes_negate_vartime(A CONST PUBLICKEY);
pargrp = ge_p3_to_cached(parkey);

// Now this parkey const is getting added to the calculated scalarmult from hash & pubkey
ge_p1p1 a = ge_add(r, pargrp);
ge_p3 r2 = ge_p1p1_to_p3(a);

// r2 will now converted to a byte array and the last byte is XOR'd with 0x80
result = ge_p3_tobytes(r2);
result[31] ^= 0x80;

This result is now used as the server public key.

So the server has to know the private key of "result" (and indeed, while this exchanging is happening, the private key of this calculation is in the memory of the server). But I cannot reverse this part of the calculation from the server binaries.

The only thing that I know, is that the public key is  scalar (a hash of public key, public key) + const.
Of course the server cannot calculate the private key from this special publickey.
Does anyone have any idea how this private key could be generated?


texts:
Especially in relation to stream ciphers, I frequently read about (sometimes theoretical, sometimes practical) attacks that are able to "distinguish a ciphertext from a truly random stream".

What's logical to me is that - just because a ciphertext looks random, it isn't necessarily random. Looking around, the general consensus is that "ciphertext needs to be indistinguishable from a stream of truly random bits".

This got me thinking: what exactly is "true randomness"? According to (cryptographically related) definitions I found, "true randomness is unpredictable". So far, so good... but that's also marks the exact point where I've lost it.

"Unpredictable" would practically mean that we have nothing to compare the ciphertext with, because we can not predict what output "true randomness" might produce. Also, there is a (minimal) chance that "true randomness" might output the exact same series of bits as a ciphertext. Meaning: a ciphertext might read 63F1t49X43 and there's a (minimal) chance "true randomness" might produce exactly the same output 63F1t49X43. No one can tell, because "true randomness is unpredictable".

Not being able to predict any true randomness, how can we compare, distinguish, or even claim that a ciphertext is not truly random? Obviously not by comparing it with "true randomness" as that would be impossible due to "true randomness being unpredictable".

Now, I'm pretty sure cryptography is not philosophy and — as a result — I'm absolutely sure I'm missing something obvious in relation to the cryptographic meaning of "true randomness". I'm guessing the details are to be found in the cryptographic definition of "true randomness", which leads to my question:

How exactly is "true randomness" defined in the realms of cryptography?

Practically, I guess you could say that I'm not really sure I correctly understand how someone can provide (cryptographically sound) proof to the claim that a series of bits is truly random when "true randomness" is considered to be unpredictable. So, if you think it's not the definition that might be confusing me here, please feel invited to set my head straight by pointing me to whatever I might be interpreting incorrectly.

EDIT

To avoid misunderstandings: when talking about "true randomness", I'm thinking along the lines of "True Random Number Generators" and not "Pseudo Random Number Generators". That's why I'm asking about "true randomness" and not pseudo-randomness.


texts:
A related question has been asked and answered here.  My question is specifically about figuring out C for very large J.  I have searched the web and found many scholarly articles on "jump ahead" and how to efficiently do so, but I am looking for a more "layman's" algorithm.

Here is the background information.  I am working through understanding the areas of weakness in using LFSR in cryptography.  To proof the concept, I have an encrypted message from a stream cipher using an N-bit LFSR.  The plain-text is ASCII, so I know the plain-text bits recurring at a specific interval (8), call it m.  From that, I get a set of non-consecutive key bits.  I have used the Berlekamp-Massey on the first 128 such bits at index multiples of m, then used the resulting coefficients and the first 64 bits passed to BM to initialize an LFSR.  I've run through the rest of the message proving to myself that the bits at multiple m are all predictable.

Now I would like to prove the remaining piece to myself, namely to get back the LFSR coefficients for the message, with only having a subset of the key bits and an associated LFSR for those bits.  In the question I made reference to, I am stuck trying to figure out $b_i=c_{(i\,m^{-1}\bmod p)}$.  In other words, $c_{(i\,m^{-1}\bmod p)}$ is a hugh jump forward with the LFSR, too large to just step to that point in the state.  As, I said, I found articles that discuss LFSR "jump ahead", but I think I need something more explicit on the approach.

For instance, a simple method (and slow), is to precompute the matrix power $A := F^J$(A Fast Jump Ahead Algorithm for Linear Recurrences in a Polynomial Space).  But I find no information on how to create the matrix $A$ from the coefficients.  To prove the concept, I don't need a fast algorithm, just something I can apply to close the loop.

An algorithm (Python, C, Java, et al), or implementation would be most helpful.  But even an article that give more complete details on the approach could serve the purpose.  Can you recommend something?

Here is a specific example using Fibonacci mode to establish conventions:

Coeffients: 1111100000010100101010001111110101111100110010110011101111001001
State:      0000111101011011011000011101100111001010000011001001100100011110
Output:     000011110101101101100001110110011100101000001100100110010001111010110011001100101111011110110001010001001110010011101010110101001001110000000101111110001001110001000010100111110111001001100001111001010011110110110010010110010001101000100001111101110011101100011001110100010111101111010101101001001000011100011001010110100010001111011110000110010100000000011100011111011110011111100110010110001100011101001111010101101101100010100110110110100000100011111001011111001111000010011011101000111110111101001111001101011101101001111110001111011111100100101010011000101011001010111001001001..

Shortened; see here for the origin.


texts: Does ShaCrypt have the properties which make BCrypt slow on GPUs?

texts:
Sha256Crypt / Sha512Crypt are designed based on ideas of BCrypt but use SHA instead of Blowfish because of political requirements.

The Sha*Crypt algorithms have the advantage that they are used in /etc/shadow on all common Linux distribution.

Do the Sha*Crypt algorithms have the same properties concerning memory use which slows BCrypt down on graphic cards?


texts:
2 hours ago I thought I had this figured out, but now I am doubting myself and want someone to validate my algorithm.

I want to take a stream of k trusted random bits and convert it to groups of 5 digits in a uniformly distributed range from 0-99999. To do this I take k and truncate to a multiple of 32, let's say the result now has n bits where n = k - k % (4*8). To create one group of 5 digits we load 32 bits into a variable we'll call var_i. The result will be stored in var_e. To get 5 digits from 0-99999 takes 17 bits, so we perform the loop:

    for (int i = 0; i < 17; i++)
      var_e += ((var_i >> i) % 2) << i

this way we preserve only the first 17 bits. Then we perform var_e = var_e % 100000 to truncate var_e to 5 digits. var_e is now one complete block of 5 digits.

An alternative algorithm could be to just take a 32 bit number var_e and perform var_i = var_e % 100000. This would take just the last 5 digits of the 32 bit number, which fall into the range 0-99999.

These algorithms both waste nearly 50% of the input data, but it would be fairly easy to change the first one to accept 17 bits of input.


texts: Why is the internal chacha20 permutation vulnerable to attacks if used in a sponge construction?

texts:
The user Forest in here claims that the internal chacha20 permutation is "vulnerable to attacks if it were used in a sponge construction". My question is as follows:

What are these attacks?
Would these attacks still be an issue if we assume that we are using a modified version of the chacha20 that does not have a trivial to find fixed point?


texts: Is there a feasible way to generate an RSA key manually the same way as it is for an ECC one?

texts:
In elliptic curves, a private key is just a random number, and one relatively small compared to other crypto systems (256 bits for ECC vs 4096 bits for RSA for example).

Suppose I don't trust hardware random number generators (electronic ones) and I want an auditable way to generate a private key. For elliptic curves, it's feasible to flip a coin 256 times and annotate the results to form a 256 bits random number. You can switch that by an n-sided dice to speed up the process.

Now, for RSA, the key is not just simply a random number. It's a product of two random primes. I don't know the details of how these random primes are found. Are them generated by a random number? If so, how long is this number?

If this number is still long, do you know a feasible way to generate a 4096 bits RSA key manually?

PS: I know it'd take years to do the public key math manually from the private key in both cases. I just want to manually generate the key (in the case of ECC) or key seed (in the case of RSA), so I can plug into 2 completely different air gapped computers and see if the public keys match, which would be a very good signal.


texts:
The definition of pseudo randomness that leads to pseudo random function talks about indistingishability of a key-ed function and a random function.

i.e. The key-ed function family $\{F_k\}$ is PRF if $|Pr[D^{F_k}(1^n)=1] - Pr[D^{f}(1^n)=1]|$ is negligible for $k\leftarrow\mathcal{K}$ and $f\leftarrow\mathcal{F}$.

Informally the output of both the function $F_k$ and $f$ at polynomial many points follows same distribution. Since $f$ is a random choice of random function family, $\{f(x)\}$ is uniformly random.

So can I use output $F_k(x)$ as the key to same PRF in next iteration?
i.e. say $k1=F_k(x)$ and I can compute $k2=F_{k1}(x)$. But will $\{F_{k1}\}$ still be a PRF?


texts:
Why use an Initialization Vector (IV)?

How are IV's used?
What are the advantages/disadvantages of using an IV?
Why use an IV instead of a longer key in which some section of the key is public?
What happens to various security properties if an IV is insufficiently random?
Are IV's always public knowledge? If so is this the property that distinguishes an IV from a Key?
Given that IV are often public are there any attacks that involve a man-in-the-middle attack that alters the IV?


texts:
I'm looking to fill in the gaps of my knowledge of lattices. Can anyone point me towards papers or books that introduce lattice crypto assuming a fairly solid math background?

Mods: Feel free to close this if it's not the proper format. I'm not exactly clear on the literature request policy.


texts: RSA: If I know n, e, p, and q, how do I calculate d using the extended euclidean algorithm?

texts:
After doing a good amount of research, it's become fairly obvious that I ought to be using the extended Euclidean algorithm to calculate d from the data that I already have.

However, this isn't an area of mathematics I'm very familiar with, and the algorithm both takes and outputs multiple integers instead of just one.

So, my question is: Which of the numbers that I already have to I need to input into the algorithm, and of the several numbers it outputs, which is the one I'm looking for?


texts:
I'm trying to study a simplified TLS-style protocol, including verifying RSA signatures. It's an attempt to verify using only a valid certificate. However, I can't manage to get anything to verify properly. I have a modulus, exponent, signature, and hash of the message. With the following parameters:

  modulus = 28459 = n
  exponent = 7 = e
  signature = 5128 = s
  hash(m) = 4085 = x

As I see it, I should be able to take the following

  s^e mod n = 5128^7 mod 28459

and see if it equals

  x mod n = 4085 mod 28459

If the equations are equal, I'm all set. However, they're not equal! I get 18044 != 4085. Am I missing something here?


texts:
The STARKs paper states

  Third, and most important, ZK-PCPs are transparent (or “public
  randomness” ), which means that the randomness used by the verifier is
  public; in particular, setting up a ZK-PCP requires no external
  trusted setup phase

as one of its main advantages over SNARKs.
This statement is not fully clear to me.
Which properties rely on this "common random string"?
Does the verifier only "trust" a received proof if he/she trusts that the public random string was chosen uniformly at random?
If not, why can't the prover simply pick a random string itself and send it along with the proof if the setup does not need to be trusted?
This way there would be no setup at all.


texts: In a RLWE setting where you are given a secret key $s$ and an associated public key $pk = (p_0,p_1) = (-(p_1s+e),p_1)$, is it possible/easy to forge a new secret key $s'$ such that $p_0+p_1s'$ has a small infinity norm? In other words is it possible/easy to forge a different secret key generating similar public keys?


texts: Which characters to take into account when calculating unicity distance?

texts:
I need to calculate the unicity distance of a block cipher. Assuming I know that the plaintext is an English message I considered using 53 as the size of the alphabet, since the message could contain lowercase ans uppercase letters from the english alphabet, as well as whitespace.
Would this be the right way to approach this calculation?

Thanks in advance.


texts:
Every single PRNG attack I could find during my research depends on knowing the PRNG algorithm(s) as well as having definite output.

Suppose you have the following scenario: nothing is known about the PRNG design and the output you get is filtered through an application such that you only get $A,B,C,D$ where each symbol has some 'probability'. To simplify this you can assume that the output of the PRNG is between 0 and 100 and that it is arbitrarily divided such that each symbol in $A,B,C,D$ has its own range. You do not actually get to see the PRNG output at any point.

What kind of attack is possible on this $A,B,C,D$ output stream? The only one I can think of is if the PRNG cycle is short and it starts repeating.


texts: Why does AES ciphertext entropy always close to 8?

texts:
I have three binary files: 31744 byte length (1), 5712980 byte length (2) and 10806008 byte length (3).

The alphabet is all 256 symbols from 00 to ff. I compute the shannon entropy, replacing probability with frequency.

(1) H = 4.291334237835409

(2) H = 7.999155088532762

(3) H = 7.993862849926811

Then I encrypted all three files with AES. Alphabet is still the same. I computed the shannon entropy.

(1)' H = 7.255697988479884

(2)' H = 7.999970021706294

(3)' H = 7.999829860973214

Ok, I see the difference and the entropy of encrypted data is higher, it is expected.

But why entropy of encrypted data close to 8 and doesn't grow up? Entropy of plaintext bytecode is growing up with the size of data, but entropy of encrypted bytecode doesn't grow up with the size of data. Please, give me answer and some links if they exsist.


texts: Effective security of block cipher – equal the key size, or half the key size?

texts:
The Wikipedia “Key Size” article states:

  The security of an algorithm cannot exceed its key length (since any algorithm can be cracked by brute force), but it can be smaller. … … … Most symmetric-key algorithms in common use are designed to have security equal to their key length.

(emphasis mine)

The book “Secure Programming Cookbook for C and C++: Recipes for Cryptography, Authentication, Input Validation & More” by John Viega and Matt Messier states (on page 161, 2nd half of 4th §):

  The general rule of thumb is that the effective strength of a block cipher is actually half the key size, assuming the cipher has no known attacks that are better than brute force.

(emphasis mine)

Now…

To avoid nit-picking, let’s keep it simple and assume that an individual block cipher does not use an algorithm that loses some of the effective security a key provides. Also, let’s assume that no known attacks exist.

Would it be more correct to claim that the effective security of that cipher is equal the key size, or is it half the key size? Simpler asked: which of the two quoted statements is correct, and why?


texts: What are some of the alternatives to password based file encryption?

texts:
With the ever increasing risk of attackers compromising password based encryption by brute forcing or guessing passwords, are there alternatives to this traditional scheme of deriving encryption keys from passwords. I realize that there are memory hard hash functions like Argon2 that creates derived keys from passwords, and because of the memory hardness slows down brute forcing to some extent. But still, if the password is weak in the first place and if the salt is known to the attacker, then brute force becomes trivial, considering ever increasing rate of computational power, provided by GPUs, ASICs etc.
Further more, when considering the problems associated with file encryption,  where it is required to generate a key (256 bits) to use in a symmetric encryption algorithm like AES, there is not a better user friendly method than asking the user for a password or a passphrase. Also, if we consider biometric methods like fingerprint detection, it is almost impossible as of now, to derive the same encryption key from biometric data all the time.
But are there, other methods, most preferably software techniques that I'm not aware of?


texts: Why is the salt used only once in PBKDF2, while the password is used often?

texts:
The purpose of PBKDF2 is to create a derived key (DK) from a master password (PW) and a salt, often using a function like HMAC-SHA256.  I have read that the salt should be as random as possible.  But if that's the case, why does it play such a minor role?

I'll let the equations speak for themselves, starting with HMAC-SHA256:

$$\def\op{\operatorname}\def\0#1#2#3{\text{0×#2#3}}
\op{HMAC-SHA256}( PW, m ) = \op{SHA256}( K_o ∥ \op{SHA256}( K_i ∥ m ) ) $$
where
$$\begin{align*}
K &= \begin{cases}
    PW &\textrm{if } \op{bytes}( PW ) = 64 \newline
   \op{SHA256}( PW ) ∥ [\0x00]_{32} &\textrm{if } \op{bytes}( PW ) > 64 \quad \textrm{ (32 zero bytes)} \newline
 PW ∥ [\0x00]_{64-\op{bytes}(PW)} & \textrm{if } \op{bytes}( PW ) < 64
\end{cases} \newline
K_i &= K ⊕ [\0x36]_{64} \newline
K_o &= K ⊕ [\0x5c]_{64} \newline
\end{align*}$$

Now PBKDF2:

$$
\begin{align*}
DK &= T_1 ∥ T_2 ∥ ... ∥ T_{\op{len}(DK)/\op{len}(T_i)} \newline
T_i &= U_1^i ⊕ U_2^i ⊕ ... ⊕ U^i_{\text{iterations}} \newline
U^i_1 &= \op{HMAC-SHA256}( PW, \op{salt} ∥ \op{INT32}( i ) ) \newline
U^i_n &= \op{HMAC-SHA256}( PW, U^i_{n-1} )
\end{align*}
$$

But watch what happens if the two are combined:

$$\begin{align*}
 U^i_1 &= \op{SHA256}( K_o ∥ \op{SHA256}( K_i ∥ \op{salt} ∥ \op{INT32}( i ) ) ) \newline
U^i_2 &= \op{SHA256}( K_o ∥ \op{SHA256}( K_i ∥ \op{SHA256}( K_o ∥ \op{SHA256}( K_i ∥ \op{salt} ∥ \op{INT32}( i ) ) ) ) ) \newline
& \dots
\end{align*}$$

Or in pseudocode:

$$\begin{align*}
&T[i] = 0 \newline
&U = \op{salt} ∥ \op{INT32}(i) \newline
&\text{for } n = 1 \text{ to }c: \newline
&\qquad U = \op{SHA256}( K_i ∥ U ) \newline
&\qquad U = \op{SHA256}( K_o ∥ U ) \newline
&\qquad T[i] = T[i] ⊕ U \newline
&\text{next }n \newline
\end{align*}$$

So the salt is used only once per output block, while the master password is used twice per iteration (in the forms $K_o$ and $K_i$).  I understand that the avalanche effect means a slight change in the initial hash input will have a significant impact on the hash output, but wouldn't it make sense to introduce as much entropy into the final result as possible?


texts:
I am aiming to find out if this problem/puzzle can be solved with cryptography at all. Say there are these two parties:

Subject S which has a master private/public key pair (MPriv, MPub) and a set of key pairs derived from MPriv. Each of the derived pairs has its own public ID, and the private keys are merely the concatenation of MPriv and the ID (this appears to be achievable);
Trusted party T which issues proofs/certificates to subjects like S. These proofs are linked to the subjects' public keys and are used to demonstrate to the whole world that whoever has the corresponding private key is such-and-such-and-such (which T would have verified by appropriate means before issuing the proof; let's call this proof content).

So, say S has obtained a proof from T for one of his public keys (either MPub or one of the derived ones). Is there a way for S to "relay" the proof to another derived key from the same set? That said, could S, without going to T again, somehow use the proof he has already got to derive a proof of the same content for another key in the same set? From the point of view of the public, the original proof and the derived proof would appear unrelated — apart from that they have the same content and are issued by T.


texts: RSA enc/decryption with multiple prime modulus using CRT

texts:
Every information I found on internet about RSA-CRT encryption/decryption uses only two primes. I'm interested in my project in doing that using multiple (up to 8) primes.

The general idea is to calculate $d_p = d\bmod(p-1)$, $d_q = d\bmod(q-1)$, and $q_\text{inv} = q^{-1}\bmod p$, where $p$ and $q$ are primes.

Encryption and decryption is based on "logical relations" between $p$ and $q$ and I'm unable to expand it to more than two primes.

Any help appreciated.


texts: Randomness in Trichina's secure AND operation

texts:
In this paper, Elena Trichina introduces a way to compute a masked AND operation.
The principle is the following:

Having two operands $a$ and $b$ masked with random boolean shares $x$ and $y$ ($\tilde{a} = a \oplus x$ and $\tilde{b}=b \oplus y$), how to securely compute $\tilde{a} \cdot \tilde{b}$ where $\cdot$ refers to bitwise AND.

In the paper, the solution is first introduced for single bit operands but here I consider the case where operands can be of any size.

In section 4.2, the author underlines the fact that
\begin{equation}
\tilde{a} \cdot \tilde{b} = (a \cdot b) \oplus (x \cdot \tilde{b}) \oplus (y \cdot \tilde{a}) \oplus (x \cdot y)
\end{equation}
Hence, the mask of $\tilde{a} \cdot \tilde{b}$ is equal to $(x \cdot \tilde{b}) \oplus (y \cdot \tilde{a}) \oplus (x \cdot y)$, which does not manipulate unmasked data.

So far everything, is clear.

However, it is further said that if we only use two masks $x$ and $y$ to mask $a \cdot b$ then

  in order to obtain a robust mask, we would have to XOR the result of
  computations on masked data with the new mask ($x \oplus y$), which
  can be achieved while computing the terms of the ''mask correction''.
  Far better solution is to use a third random, $z$, as a new mask computing a
  ''masked'' AND operation, for example, as follows
  \begin{equation}
((\tilde{a}\cdot \tilde{b}) \oplus ((x \cdot \tilde{b}) \oplus ((x \cdot y) \oplus z))) \oplus (y \cdot \tilde{a})
\end{equation}

I don't understand why is it necessary to introduce randomness to compute masked AND operation.

In other terms:
What is wrong when computing $c = \tilde{a}\cdot\tilde{b}$ and considering the corresponding mask $(x \cdot \tilde{b}) \oplus (y \cdot \tilde{a}) \oplus (x \cdot y)$?


texts: Default RNG used by openssl for certificate generation

texts:
I have generated a certificate using openssl with the below command.

openssl ecparam -out <output_file> -name secp256r1 -genkey

What would be the RNG used in this case? and is it cryptographically secure?


texts: Which type of non-basic cipher works better with microcontroller which has no interface and keyboard connected to it?

texts:
Did a C++ code on Caesar Cipher to do encryption and decryption with my XMC4500 microcontroller but my lecturer said that Caesar Cipher is too simple. He wants me to use a non basic type of cipher and to include size of bit length of plain text and cipher text, secret and public message number and key. And the problem is no keyboard or display interface will be connected to my microcontroller so i could not use printf, scanf, cout and cin to input any of those values. Any ideas on what Cipher I should use and how I could do it?

UPDATE: Thank you for all the suggestions but my supervisor finally told me to use ASCON instead.


texts:
Is there a way to setup a hierarchical encryption using public key encryption?

Let's say a higher level user can decrypt messages encrypted by lower level users. Is that possible?

I guess it is only possible to do with hierarchical key management, like the higher level users have access to the lower level user's keys.

Is there any other option to do something like this?


texts:
I'm having a difficult time trying to solve this problem.

  Suppose Alice uses the Elgamal signature scheme with  $(\alpha,
 \beta, p) = (2, 33384, 65539)$.   She publishes the two signed
  messages: $(m_1, r_1, s_1) = (809, 18357, 1042)$ and $(m_2, r_2,
 s_2) = (22505, 18357, 26272)$. Find $a$ by setting up and solving
  appropriate linear congruences. (I.e., don't compute the discrete
  logarithm of beta directly)

I know that $\beta = \alpha^a \bmod p$, which in this case would be $33384 = 2^a \bmod 65539$.  However, I have no idea how to use the messages to set up congruences to solve for $a$. Any help is appreciated.


texts: Max size for exponent and modulus in RSA and for y, p, q, g in DSS

texts:
I'm writing a method in Java to read SSH public key in RFC 4253 format, which, in my case, can be either RSA, or DSS.

What I really need is to read exponent and modulus for RSA key and y, p, q, g values for DSS key, which, according to the standard are of type mpint (multiple precision integers).

So basically, what I'm doing, is reading an integer first (that becomes "length"), then reading as many bytes as this integer is, then converting this byte array to Java's BigInteger.

It works perfectly well for valid keys. But the problem appears if there's a malformed key where this first integer is some extremely big number (let's say Integer.MAX_VALUE). Then such an approach results in Requested array size exceeds VM limit exception or some other Java errors related to memory. What I want to do to solve this issue is pre-checking if the length-integer is in a valid range (smaller then some max value).

And here comes the question: what are the max values for exponent, modulus, y, p, q and g? Is there even any maximum for them?


texts: Encrypting documents through a proxy key

texts:
Suppose I'm developing an app to secure a lot of documents. These documents were encrypted (say, using AES) with a key X.

This key X is basically the password that the user enters before wanting to view any particular document, because that doc need to be decrypted using X.

If the user wishes to change the key X to something else (maybe his password got compromised), then he'll have to decrypt all the documents, and then re-encrypt all of them using the new value of X.

What if, instead, I have a key Y, which is used to decrypt/encrypt the documents. However, Y itself is a key that is stored on the system, encrypted using X, which is what the user enters.

I'm thinking that the advantage of this would be when the user wants to change his password, he only needs to decrypt and re-encrypt Y, without having to decrypt/re-encrypt all the documents.

Are there any possible weaknesses that I'm missing with this method, or is it sound?


texts: Why is it so hard to make longer hashes?

texts:
I was reading this answer about why there is no such thing as a SHA-1024 hash:

SHA-2 was built with state and word sizes to meet the security requirements on commodity computers (x86 and Alpha), which use 32 and 64-bit maximum CPU word sizes for general purpose registers. This meant that the state was built with 8-words to meet the 2 most common security requirements.
Support of a larger digest would either require the core compression function to be different (as there would need to be more word inputs) or a larger word size, which did not exist (and still does not) except in specialized processors or SIMD registers (without appropriate instructions).

Why can't SHA-512 or SHA-256 simply be reused instead to create a longer hash, eg. by concatenating hash(string) and hash(string + 1)? Does this pose a security concern, speaking of hashes in general?
I have little knowledge of the internals of hashing algorithms, but I think that if it takes an average time T to find a collision on hash(string), it should take an average time T^2 to find a collision on hash(string) concat. hash(string + 1).


texts: Computational trapdoor where the problem is tractable for both parties but easier for one

texts:
Usually the sort of trapdoors which are talked about are designed such as to make the computation intractable for one party and tractable for the other.

But what if one party merely has a big advantage in computation over the other? Can you use it to create a construct in cryptography?

For example, suppose you have a way to construct a large number such that using it as an operand in multiplication is very cheap for you: O(kN) for a k you can somewhat control (by randomly trying many primes looking for such a quality and then multiplying them masking the quality). The best others can do seems to be O(N*logN*loglogN) nowadays.

How can you use this computational trapdoor? The multiplication is tractable for both parties but one has an advantage.

Is there a way with multiplication to amplify a linear advantage into an exponential or polynomial one?


texts: Are chosen-prefix collisions for SHA-1 a major threat?

texts: GPG signing of Git commit tags relies on the collision resistance of SHA-1, which is weak.  However, the attacker does not get to choose the prefix.  How much does this translate to an actual vulnerability?


texts: Generic group model: use of polynomials in the proof of the master theorem

texts:
I've been looking at the paper of Boneh, Boyen, Goh Hierarchical Identity Based Encryption with Constant Size Ciphertext
which contains a general theorem (Theorem A.2) about the advantage of an attacker in the generic group model. It seems to be based on the idea that in the generic bilinear group model, we can only compute things that are linear combinations of the given inputs as well as multiply linear polynomials once when computing a pairing. What they argue is that if the randomly sampled inputs are $x_1,\ldots,x_n$ and we have computed two (at most quadratic) polynomials $L_i(x_1,\ldots,x_n)$ and $L_j(x_1,\ldots,x_n)$, then the equality check for

$$L_i(x_1,\ldots,x_n)=L_j(x_1,\ldots,x_n)$$

can be replaced by an equality check

$$L_i(X_1,\ldots,X_n)=L_j(X_1,\ldots,X_n),$$

i.e. we check for equality as polynomials, not as evaluated polynomials.

The general idea of the proof is then that we may afterwards check what the probability is that the adversary could have seen a difference between these two cases. This seems to be based on the idea that for random polynomials, we have an upper bound for the probability that a randomly sampled point is a root.

My issue with this proof is that since the polynomials that show up in the computation depend on information the adversary has gained from previous oracle queries, the list of polynomials $L_1,\ldots,L_q$ has been adaptively constructed. Therefore, the list is not independent of the sampled values $x_1,\ldots,x_n$. I don't see how this is taken into account in the proof? Anyone care to explain this in more detail, since all later papers with similar theorems seem to sidestep this issue too.


texts:
I am studying the Winternitz signature and I describe its algorithms in the next

W-OTS Key Generation. Select the parameter $w\geq 2$ that is the bit size of the partitions of the message to be signed. Compute the number of  partitions

$$t_1 = \Big \lceil \dfrac{r}{w} \Big\rceil,$$
and parameter
$$t_2 = \Bigg\lceil \dfrac{\lfloor \log_2 t_1 \rfloor + 1 + w}{w}\Bigg\rceil,$$
The signature key is $X=(x_0, x_1 \cdots, x_{t-1}) \in \{0,1\}^{r,t}$, where the bit-strings $x_i$ with $0 \leq i \leq t-1$  are randomly chosen. The verification key $Y$ is computed by applying   ${\mathcal{H}}$ $2^w-1$ times in each bit-string $x_i$ of the signature key, i.e. $Y=(y_{0},\cdots, y_{t-1})$ with $y_i = {\mathcal{H}}^{2^w-1}(x_i)$.

W-OTS Signature Generation. Compute the digest $d$ of message $M$ to be signed using $g$, i.e., $g(M) = d = (d_0, \cdots, d_{r-1})$. Add zeros to $d$ until it is divisible by $w$. The partition of $d$ into $t_1$ $w$-sized parts is
$$d = b_0|| b_1|| \cdots || b_{t_1-1}.$$
Note that each element $b_i$ can be transformed into base-$10$  representation and identified with integers $\{0,\cdots, 2^w-1\}$.

Calculate the checksum
$$c=\sum_{i=0}^{t_1-1} 2^w - b_i.$$
The maximum number of bits representing $c$ in binary base is $\lfloor \log_2 t_1 \rfloor + w + 1 $. Indeed, note that $c = t_1 2^w - \sum_{i=0}^{t_1-1}b_i \leq t_1 2^w$ and the number of bits required to represent $t_1 2^w$ is $\lfloor \log_2 t_1 2^w \rfloor + 1 = \lfloor \log_2 t_1\rfloor + w + 1.$

Similarly, split the binary representation of $c$ into $t_2$ $w$-sized parts, i.e.,
$$c = c_0|| c_1|| \cdots || c_{t_2-1}.$$
Finally, computing the signature as
$$\sigma_{\text{W-OTS}} = (\sigma_0,\cdots,\sigma_{t-1})=({\mathcal{H}}^{b_0}(x_0),\cdots,{\mathcal{H}}^{b_{t_1-1}}(x_{t_1-1}),{\mathcal{H}}^{c_0}(x_{t_1}),\cdots, {\mathcal{H}}^{c_{t_2-1}}(x_{t-1})).$$

W-OTS Verification. To verify the signature $\sigma_{\text{W-OTS}}$ of the message $M$, compute the values $b_i$ and $c_i$ in the same way as above described, then compute
$$y'=({\mathcal{H}}^{2^w-1-b_0}(\sigma_0),\cdots,{\mathcal{H}}^{{2^w-1-b_{t_1-1}}}(\sigma_{t_1-1}),{\mathcal{H}}^{2^w-1-c_0}(\sigma_{t_1}),\cdots,{\mathcal{H}}^{2^w-1-c_{t_2-1}}(\sigma_{t-1})),$$
 and compare $y'$ with $Y$. The signature is valid only if $y'_i=y_i$,  $\forall i$. \

I need to understand why this present resistence against adaptative chosen message attack. According my knowledge the adaptative chosen message attack works as follow: an attacker can choose a message on which he learns a signature. Afterwards that attacker can choose the message he wants to forge a signature for. This is called the standard model for secure signatures.

My question is why winternitz signature is secure in the standard model?  I make this question because using the fact that

"an attacker can choose a message on which he learns a signature"

an attacker can choose the message 00000..0000 and then He learn $\mathcal{H}(x_i)$ for $i \leq t_1$. With these value he can obtain all next values of the form $\mathcal{H}^v(x_i)$, that is he can forge partially any signature because each $\sigma_i$ his obtained using that form.


texts: What is the purpose of key strengthening?

texts:
I recently came across this term and after some research found this article which states the following:

  An alternative approach, called key strengthening, extends the key with a random salt, but then (unlike in key stretching) securely deletes the salt. This forces both the attacker and legitimate users to perform a brute-force search for the salt value

That made me wonder, what's the point of using such an approach rather than the traditional key stretching?
Are there any real applications employing this method?


texts:
I have an encryption scheme that uses a 256-bit master key, from which 2 separate keys (one for AES-256-CTR encryption and one for a HMAC-SHA256) are derived using HKDF. However, I'm not sure exactly how to utilize HKDF without screwing it up, so straight to my concerns:

Is it safe to just use SHA-512 as the hashing algorithm to get a 512-bit output and split it in 2?
I know that using salt is not mandatory, but does using it actually improve security?
I know this might be a dumb idea, but still ... can the salt be the IV used for encryption?


texts:
As I understand, if two users have a shared key, it is possible to encrypt a message using symmetric key encryption.

So when a secret key is shared through Diffie-Hellman asymmetric key exchange, it means that the users have their shared key. So why can't AES keys be generated from shared keys, and why not use only AES for message encryption after this point?

Actually I am confused about this: if there is a shared key from a DH key exchange, why are we still talking about ElGamal asymmetric message encryption, isn't it confusing for a learner like me, to study that , firstly a secret key is sufficient to do encryption using faster symmetric encryptions and also talking about an asymmetric encryption that is based on shared secret key. Isn't learning Elgamal unnecessary and confusing? If not, is there any particular application that uses elgamal, because I do not find any solid application.


texts: Is there any progress towards a SHA-1 distinct chosen prefix collision?

texts:
The currently known collision attacks on sha1 are relatively difficult to practically exploit because the two colliding files must have mostly the same content. This limits attacks to file formats where garbage can be easily hidden and where conditional logic based on the value of a small block of garbage can be used to switch that apparent content of the file.

A distinct chosen prefix collision would be far more dangerous. A small block of garbage would still be needed but it could be towards the end of a potentially large pair of files and the rest of the content could be totally different. There would be no need for both files to contain all of the content and use clever tricks to hide half of it. The two files could have totally different formats if desired.

For MD5 a distinct chosen prefix attack showed up fairly soon after the first simple collision attack and was successfully exploited against a certification authority.

Is there any progress towards a distinct chosen prefix collision attack on SHA-1?


texts: How to put the hash of a PDF file in the PDF file?

texts:
I know it sounds strange.. but, are there any ways in practice to put the hash of a PDF file in the PDF file? And after geting the hash in the PDF file - if someone would do a hash check of the PDF file, the hash would be the same as the one that is already in the PDF file? :) maybe with MD5, since it's known to have weaknesses? Example:

[user@notebook ~] wget -q http://renyi.hu/~csirmaz/nws06/xajanlo.ps -O Md5-xajanlo.ps; wget -q http://renyi.hu/~csirmaz/nws06/xutasit.ps -O Md5-xutasit.ps; md5sum Md5-xajanlo.ps; md5sum Md5-xutasit.ps; sha512sum Md5-xajanlo.ps; sha512sum Md5-xutasit.ps; rm Md5-xajanlo.ps Md5-xutasit.ps
583bdceb34826c38ac7f1fdac3aca807  Md5-xajanlo.ps
583bdceb34826c38ac7f1fdac3aca807  Md5-xutasit.ps
c82d26f77ccd4597622fc985d4220aedad6f866555c6db82db2d6d17e22016268a3e88d0b0cd89a8e536ae7d666c446edeb77edef2fca783739e4bff9d7032be  Md5-xajanlo.ps
205c18b396bee84995d8c325787600ca88ca3d9758c4dfe89cdaa242ab9513710057c5fce55afb2c6ef3117703be7c31266a1fa6fbac1f369b82f0719587c60c  Md5-xutasit.ps
[user@notebook ~]


texts: What is th purpose of m and q in elliptic curve cryptography protocols?

texts:
In crypto protocols that contains calculus on elliptic curves I can often see $\dfrac{m}{q}$$Q$ where $m$ stands for order of EC points group and $q$ is the order of corresponding subgroup of $m$. $Q \in q$.

What is the possible sense of this multiplication speaking mathematically?

It's possible that protocol example will be needed.
Here it is:


texts:
I have a few questions relating to threshold signatures: a scheme where $n$ participants hold a key share and any $t$ of them can conduct a protocol using their shares that results in a valid RSA or DSA signature being applied to a known message.

Questions

Several techniques exist for threshold RSA (1,2) that seem reasonably efficient. Is there any impedance to using these protocols with a standards-compliant version of an RSA signature (such as RSA as used in X.509 for SSL/TLS certificates)?
Are there any techniques for threshold DSA (aside from this 2-out-of-2 case)?
Are there any tools available that implement a threshold signature scheme? A tool that would allows each participant to contribute to the DKG, and would later generate their contribution to the final signature on a shared message given their key share?

It is my belief that (1) is standards-compliant as padding can be done prior to signing without reference to the signing key, (2) does not exits, and (3) does not exist either. But now that this site exists, I figure why not ask?

EDIT: Regarding (2), there are techniques for DSA. I missed them because they are proposed for "DSS" instead.


texts: Advanced Encryption Standard Algorithm Secret Key

texts:
just a follow up question with this question..

How does the key schedule of Rijndael looks for keysizes other than 128 bit?

A 256-bit key can still encrypt a block of plaintext in 128 bit?

but in this tutorial, to encrypt 128-bit plaintext, It need 128-bit of secret key also..

can someone provide me a clear explanation about using of 192, 256 bit key to encrypt a 128-bit block of plaintext?

The only thing that I can understand is that If you will encrypt a 128-bit of plaintext, it need to use 128 bit of secret key, to encrypt a 192 bit of plaintext, it need to use 192 bit of secret key, to encrypt a 256 bit of plaintext, it need to use 256 of secret key.. that is the only thing that I know based on my research..


texts: Lemma KL-Divergence (Differential Privacy)

texts:
I am studying differential privacy and I got stuck again in proof of a lemma. Which is:

$D_{\infty}^\delta(Y||Z) \leq \epsilon$ if and only if there exists a random variable $Y'$ such that $\Delta(Y,Y') \leq \delta$ and $D_\infty(Y||Z) \leq \epsilon $.

I have a problem understanding the reverse proof.
Definitions:
Be $Y, Z$ two random variables.

$\Delta (Y,Z) \overset{def}{=} \underset{S}{max} \ \ \ | \Pr[Y\in S]-\Pr[Z\in S]|$
$D_{\infty}(Y||Z)=\underset{S\subseteq Supp(Y)}{max}\Big[ln\frac{\Pr[Y\in S]}{\Pr[Z \in S]}\Big]$, which is the KL-Divergence between two distributions $Y,Z$
$D_{\infty}^\delta(Y||Z)=\underset{S\subseteq Supp(Y):\Pr[Y\in S]\geq \delta}{max}\Big[ln\frac{\Pr[Y\in S]-\delta}{\Pr[Z \in S]}\Big]$

Proof:
Suppose that $D_{\infty}^\delta(Y||Z) \leq \epsilon$. Sea $S=\{y:\Pr[Y=y] > e^\epsilon \cdot \Pr[Z=y]\}$. Then
\begin{equation*}
    \sum_{y \in S}(\Pr[Y=y]-e^\epsilon \cdot \Pr[Z=y]) = \Pr[Y \in S]-e^\epsilon \cdot \Pr[Z \in S] \leq \delta
\end{equation*}
(I understand until here)
Moreover, if we let $T=\{y:\Pr[Y=y] \leq \Pr[Z=y]\}$, then :
\begin{equation*}
\begin{split}
    \sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) &= \sum _{y \notin T}(\Pr[Y=y]-\Pr[Z=Y]) \ \ \ \text{//I got stuck here} \\
    & \geq \sum _{y \in S}(\Pr[Y=y]-\Pr[Z=Y])\\
    & \geq \sum _{y \in S}(\Pr[Y=y] > e^\epsilon \cdot \Pr[Z=y])
\end{split}
\end{equation*}
I don't' understand why:   $$\sum_{y\in T}(\Pr[Z=y]-\Pr[Y=y]) = \sum _{y \notin T}(\Pr[Y=y]-\Pr[Z=Y])$$
Thus we can obtain $Y'$ from $Y$ by lowering the probabilities on $S$ and raising the probabilities on $T$ To satisfy:

For all  $y\in S$, $\Pr[Y'=y]=e^\epsilon \cdot \Pr[Z=y] < \Pr[Y=y]]$
For all $y \in T$, $\Pr[Y=y]\leq \Pr[Y'=y]\leq \Pr[Z=y]$
For all $y\notin S \cup T$, $\Pr[Y'=y]=\Pr[Y=y] \leq e^{\epsilon} \cdot \Pr[Z=y]$

Then $D_{\infty}^\delta(Y'||Z) \leq \epsilon$ by inspection
Reference:
Dwork, C. & Roth, A. (2014). The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science, page 45.


texts: What is the best way to forge a tag for a determined message?

texts:
Assume a PPT adversary wants to forge a tag for a message. The adversary has oracle access to a verification function. The adversary knows that tags are generated by HMAC-SHA-256 with 128-bit key. I think the best way for the adversary is to randomly choose a key, calculate the HMAC of the message with the chosen key , and check the result with its oracle. Am I right? If so, what is the probability of his success if he tries $m$ different keys? I think it must be:
$$\Pr[forgery]=\sum_{n=0}^{m-1} \frac{1}{2^{128}-n} $$
if I am right, can anyone simplify the sigma better than the following?
$$\Pr[forgery]=\sum_{n=0}^{m-1} \frac{1}{2^{128}-n} < \frac{m}{2^{128}-m} $$


texts: Cryptanalysis of an OTP RFID tag transmission using multiple transmissions

texts:
A scanner encrypts a 32 bit message 'x' using a secret 32 bit key 's1' and sends the resulting cipher y= x XOR s1 to an RFID tag. The Tag decrypts the message 'x' ,and then encrypts the message 'x' using its secret 32 bit key 's2' and sends the resulting cipher z= x XOR s2 back to the Scanner.

Assuming that I know what the hexadecimal values for the ciphers y and z are during every transmission. How can I find out what the keys s1 and s2 are using this limited information, but having access to the 'y' and 'z' values from multiple transmissions?

I understand that, because there are two different keys, but that the keys remain the same during multiple transmissions, that there is maybe some way to figure out the value of the keys.

I know that if I XOR y and z I get: 'y XOR z = s1 XOR s2'. I am not sure how to use this information or if it is relevant.

Sorry for any misused terms, I am new to cryptanalysis.


texts: How to glean info from a message that simply has the letters shuffled?

texts:
Suppose someone had published a several hundred page (sensitive) book, but had randomized all of the letters in an order known only to them (e.g. with a vector of random numbers of the same length as the book's characters).

This initially strikes me as relatively riskier than something of comparable simplicity (like a one time pad) since the letters are all in the clear.  But, I can't quite see how an attacker would benefit much from that information.  Are there known attacks on this sort of thing to learn things about the text?  What could be learned?  Could one maybe at least tease out an idea of what the book was about?  At what message lengths (if not all) could it be a big problem?

Hopefully this doesn't qualify as asking the community for "peer review of a cryptographic scheme"!


texts: I am working on a cryptography application which is to be used in my country. I tried looking up to see if there are any algorithms that support the Cyrillic alphabet, but I found none. Do you know of any? Can mainstream algorithms (Like AES) work with Cyrillic letters?


texts: Can timestamping provide evidence of absence before a certain time?

texts:
Normally trusted timestamping proves that certain information existed at or before a certain time. However, sometimes there is a need to prove the opposite; that something did not exist before a certain time.

Consider that I want to prove by photographs that my house is in a good condition before I rent it out to someone else, i.e. I want to be able to prove that the photos were not taken before the day when i rent it out. The old-school way of doing this is to include for example today's newspaper in the photographs, but now with the emergence of advanced graphic editors it seems like this is not enough for a proof beyond reasonable doubt.

Is there any way to do this cryptographically utilizing a trusted third-party timestamping service?


texts: Is using 7-8 random words from all words of a language as password a good idea?

texts: The Bitcoin Bip-39 dictionary has 2048 words. And a random 24 of them are pretty secure together. What if the source is bigger (all words in the language) but there are only about 7-8 words? These words will be totally randomly selected by their index.


texts: Zero-knowledge authentication to commercial VPN

texts:
For VPNs which only connect to the greater internet (as opposed to a VPN for accessing a private network), it is only necessary for the server to know that the client is a paying customer. It doesn't need to know which customer.

How could such a system be made? One method is to use Chaum's digital cash method, but have the "cash" instead be a claim ticket for data transfer.

However, if you know of any other methods, please post them.


texts: iOS Data Protection: What is the Input of the LFSR?

texts:
Every time a file on the data partition is created, Data Protection creates a new 256-bit
  key (the “per-file” key) and gives it to the hardware AES engine, which uses the key to
  encrypt the file as it is written to flash memory using AES CBC mode. The initialization
  vector (IV) is the output of a linear feedback shift register (LFSR) calculated with the
  block offset into the file, encrypted with the SHA-1 hash of the per-file key.

Regarding the iOS-Security whitepaper (excerpt from pg. 8) when a file is written to the data partition a AES-Key is created which is used by the AES engine to encrypt the file using the AES-CBC mode. AES-CBC does need an initialization vector which is the output of a linear feedback shift register.

What is the exact input of the LFSR?
What exactly does "block offset" mean?

Does it work like this:

  encrypt(LFSR(block-offset),SHA-1(perfile-key)) ---> result stored
  inside the files meta data


texts: What is total key space in transposition algorithms

texts: How we can measure key space in transposition algorithms? Should we specify the method, like rail fence?


texts: Does anyone still use BAN or GNY logic in practice?

texts:
I want to implement a simple protocol, and I'd like to verify it through BAN or GNY logic.  I would assume that if these logics are still used that there would be some programs available that would automate this.  In fact I found one paper on how to automate GNY logic, and another mentioning a tool called SPEAR that automates BAN and GNY logic, but in no case could I actually find these tools.

All of these references are pretty old, and it looks like these logics are only used academically.  Are there any examples of more modern or practical use of these, and are there any tools that are available for automating them?


texts: What is the major difference between FIPS 186-2 and FIPS 186-4?

texts:
Can anyone please tell me the major difference between FIPS 186-2 and FIPS 186-4?

I know with FIPS 140-2 they want the DSS standard to be FIPS 186-4, but what difference does it make?


texts: Why are stream ciphers based on linear-feedback shift registers so popular?

texts: I was conducting research on stream ciphers and LFSRs was a subtopic of my research and I was wondering why are LFSRs so popular?


texts: Why do $\alpha$ and the private key value in diffie-hellman should be from $2$ to $p-2$

texts: I just started learning Diffie-Hellman Key Exchange. I couldn't get the reason of making $\alpha$ and private key for Alice and Bob constrained between $2$ and the prime number generated minus $2$ (=$p-2$). Why should it be $2$ less than the prime? Is there a specific reason for this?


texts: Updating values authenticated by Merkle Tree

texts:
Assume we have 4 values: $v_1,v_2,v_3$ and $v_4$. We construct a Merkle tree on top of them such that the values are leaves of the tree.

I send the values and the tree to an untrusted server. But I keep the root of the tree locally.
Later on I want to modify (or replace) $v_4$ with new value $v_5$. Note that I Do NOT want to insert or delete any node. So I first verify the correctness of $v_4$
 and then replace $v_4$ with $v_5$ and generate the corresponding values (to update the tree). The update operation may take many times

Question: Would regular Merkle tree suffice to check the correctness of the values and the update operation?

In other words, can the server do any replay,... attack in the above scenario?


texts: Asymmetric Cryptography Confusion - 'Sign' a file to guarantee its source

texts:
What I want to do is use asymmetric crypto to guarantee that a file comes from a source. I have software that runs on lots of wireless devices, and each of those has a license file with an encrypted date that they expire. I'd like to be able to encrypt it in the office and have the devices decrypt/read the date. The purpose of using asymmetric crypto is so someone can't pull the key out of the software and encrypt their own license file. We want to be the only ones who can generate a license file.

I'm mildly familiar with RSA asymmetric cryptography. My understanding is you encrypt with the public key and decrypt with the private key. I read on https://stackoverflow.com/questions/6352023/rsa-can-you-create-a-public-key-from-a-private-key that the private key comes with the public key by RSA Specification, so I can't just reverse it and keep the private key on the devices and the public key at the office, or is there a way for me to get around this?

What sort of encryption should I use for what i'm trying to accomplish?


texts: message with small order in RSA signature

texts:
It is know that elements from $[1..N-1]$, where $N$ is RSA modulus can have different orders. So some of the elements can have very small order generating subgroup of only few elements.

Now, if the adversary for a message chooses $m$ that has small order, the adversary does not have to know the private exponent $d$ to forge the signature for this $m$, since the same signature can be produced using smaller exponent $x$ $(d \equiv x \mod ord(m))$, which can be found easier than the private exponent $d$.

Why is this not a concern in RSA signature scheme?

Update:
The cyclic attack does not depend on the order of $m$. The answer should be related to the distribution of orders for elements in $[1..N-1]$. Since the order of element divides $\phi(n)$, the choice of $p$ and $q$ should have some effect on the feasibility of this attack.


texts: Combining multiple symmetric encryption algorithms - implications?

texts:
I was just wondering if I add more security by combining two or more symmetric encryption algorithms on a plain text.

For example: Plaintext → AES → Twofish → Serpent

Of course a different key and IV (produced with a cryptographic secure prng) is used for each algorithm. Speed fortunately is not important.

Or does this form of combination has other implications I do not see?

There is a question like that here at Crypto.SE (Is TrueCrypt's multiple/cascading encryption safe?) but it focuses on using the same key.


texts: Efficient fields over arithmetic circuits

texts:
What sort of fields is efficient over an arithmetic circuit?

Efficient meaning that given a field $\mathbb{F}_p$, reduction (modulo) does not require many multiplications and preferably inversion was cheap.


texts:
What is the need for two private/public keys in twin elgamal?
I'm relatively new and would need some help.


texts: We are given a variant of DESX, where $ENC(M)= DES_k(M \oplus k_1)$ (keys are 64bits). In DESX effective key length is $119-lb(M)$ according to wikipedia, but I have not found how this is calculated. I know that the effective key length should be less than that, but how do we find the exact length?


texts: Symmetric : Generate new key from old ones

texts:
Symmetric keys should be refreshed regularly.

Is is terribly wrong to first agree on $N$ independent keys and then generate the key $k_j$ with $j>N$ by computing some form of hash on the keys $k_{j-100},k_{j-99},...,k_{j-2},k_{j-1}$? The idea being that an attacker would need to know the previous 100 keys to also be able to generate keys.

If it is not wrong, it is at least a little bit useful?


texts: What kind of attack does the current brokenness of SHA-1 allow?

texts:
I understand that the following is becoming feasible, or already is:

Find any 2 data (d1 and d2), for which SHA1(d1) = SHA1(d2)

However, it is not entirely clear to me if there is evidence of the feasibility of:

Find d2 for a specific d1, such that SHA1(d1) = SHA1(d2)

My difficulty in understanding the available literature is that I typically see the attack referred to as "seeking collisions" rather than "seeking a collision"; implying that what is being identified is two data that happen to share a SHA-1, rather than finding a datum which shares the same SHA-1 as a specific target datum.

EDIT: My question is partially redundant to, though more specific in purpose than, this question Second pre-image resistance vs Collision resistance


texts: Are there some problems to use pseudo-random number generator in Smart Card?

texts:
A Smart Card is a kind of secure device, with limited storage capacity and
computational resource.

If we use a Pseudo-Random Number Generator to generate random numbers in a Smart Card, then is there any problem?


texts: How to look for implementations of universal hashing?

texts:
Being a physicist, I know very little about cryptography. In fact, the main two practical aspects I've learned so far are: Unless you're an expert, 1. Don't try to invent new cryptosystems and 2. Don't implement cryptographic algorithms yourself if you can avoid it.
I need an implementation of information-theoretically secure authentication. For this, I intend to use a Carter-Wegman type scheme and thus need an implementation of a $\epsilon\text{-almost strongly universal}_2$ family of hash functions.
Many of the well-known published ways to construct such families seem reasonably straightforward to implement using (perhaps not in the most efficient way possible). However, I'm assuming it's a fundamentally bad idea for a non-expert to start implementing cryptosystems. My question: How do I find and select an implementation of information-theoretically secure authentication that I can use?
I'm looking for an open source solution that I can use from C and or C++ and possibly even squeeze into an embedded system as well. The final goal is not a commercial system (i.e. nobody will ever actually try to hack it) but should demonstrate best practices where ever possible.
Are there standards for this? I was assuming OpenSSL or similar well-known libraries must certainly have it but so far the official documentation has not helped me in this respect. How can I find out?
Disclaimer: If I understand correctly it is a site policy to not recommend concrete implementations of cryptosystems. Although I wouldn't mind such suggestions if the policy allows it, that is not the essence of my question. Rather, I am asking for general principles how a non-expert should approach implementing/finding and using cryptosystems, in the particular case of universal hashing.


texts: Clarification on Hill Cipher crib dragging technique

texts:
--- this has been edited as I realised the question was silly. replaced with helpful information ---

I want to confirm the following:

Given ciphertext "AGHTDIX... [cont.]" (C)

and crib (a word which I know exists in the plaintext) "WITH" (P)

I am attempting to find the key (K) by shifting "WITH" one spot down the text each time like so:

A   G   H   T   D   I   X
W   I   T   H   .   .   .
.   .   .   .   .   .   .
.   .   W   I   T   H   .
.   .   .   .   .   .   .

And calculating it using the formula (multiply the ciphertext matrix by the modular inverse of the plaintext/crib - sorry, I don't know how to insert proper formulas here):

[K] = [C] x [P]-1 (mod 26)

My question -- was -- really silly as I forgot that the Hill cipher encrypts in pairs. Crib dragging should then adapt to include letters which could come before or after the known plaintext.

A   G   H   T   D   I   X
W   I   T   H   .   .   .
[?  W]  [I  T]  [H  ?]  .
.   .   W   I   T   H   .
.   .   .   .   .   .   .

Answer below explains in better detail. Thank you :)


texts: What are the inputs of the AES key wrap algorithm?

texts:
I have trouble understanding inputs for AES key wrap algorithm as it is explained in section 2.2.1 of RFC3394.

Context:

I have a data encryption key (DEK) for AES-128 with CTR, which is used to encrypt a database file on a mobile device. DEK is device specific and has limited lifetime (1 year) as key rollover is applied. DEK is generated with help of salt and secret values generated on the server when authenticated user provides some random value (constant as long as mobile application is installed).
I have a key-encryption key (KEK, AES-128), that is derived from user's passphrase and is used to encrypt the DEK (encrypted DEK is stored in plaintext).
DEK and KEK never leave the device.

Above scheme helps me keep DEK unchanged in case user changes her passphrase and allows users working with the application in offline mode (correct passphrase recreates KEK which decrypts DEK which next allows working with database).

My question is how should I apply AES key wrap? The RFC states:

  The inputs to the key wrapping process are the KEK and the plaintext
     to be wrapped.  The plaintext consists of n 64-bit blocks, containing
     the key data being wrapped.

What are plaintext and KEK here? My DEK is plaintext and my KEK is the KEK? Or it should be passphrase (plaintext) and my DEK as KEK? I'm pretty confused and would appreciate any guidance here. Thanks!


texts: Variable length variable output encryption with out any padding?

texts: I would like to know if there is any encryption algorithm with variable input variable output with out any padding? For example if I give 16(17,18,67,117,..any size) bit plaintext, my ciphertext is also 16(17,18,67,117,..any size) bits.


texts:
I don't know if the IV in CBC mode is equal in both sides of the encryption and decryption operations.

I know that the IV must be unpredictable, but has it to be MACed in the encryption side to be deMAC and "rebuilt" to use it in the decryption side ?

So you need to "transport" the IV along with the cypher-text to use it in the decryption ?


texts: How does the user check whether $y < M$ without knowing all shares?

texts:
CRT-based Verifiable Secret Sharing Scheme

In this paper, section 4 Verifiable Secret Sharing Scheme, the dealer phase and the combiner phase are as follows:

Dealer Phase

To share a secret $d \in Z_{m_0}$ among a group of $n$ users with
verifiable shares, the dealer does the following:

1) The dealing procedure of the Asmuth-Bloom SSS to obtain the shares
$y_i = y \mod m_i$ for each $1 \le i \le n$ where $y = d+ Am_0 < M$.

Note that the $m_i$'s are large primes where $p_i = 2m_i + 1$ is also a prime for $1 \le i \le n$.

2) Let $N$ be an integer whose prime factorization is not known by the users and the dealer.

Compute $E(y) = g^ y mod P N$ .Send $y_ i$ to the $i^{th}$ user
secretly for all $1 \le  i \le n$

3)The $i^{th}$ user checks $g^ { y_{i} }≡ E(y) \mod p_i$

to verify $y_i = y \mod m_i$ . Then he checks the validity of the range proof to verify $y < M$.

Combiner Phase

Let $S$ be a coalition gathered to construct the secret.

The share $y_i$ of user can be verified by the other users by the
verification equation

$$g^ { y_{i}} ≡ E(y) \mod  p_i$$

If all shares are valid then the coalition $S$ can obtain the secret $d$

In this scheme $y$ is private. So, after knowing all shares of $y_i$, users reconstruct the secret.  But how to verify $y_i = y \mod m_i$  user checks the validity of the range proof to verify $y < M$  without knowing all shares of users.

Could you please explain how user can verify range


texts: Permutation for which an inverse is a hard problem

texts:
Is it possible to construct (even if we don't know how) a permutation for which an inverse must exist but is difficult to find (brute force required)? The one way permutation contains no hidden information (keys) or state - it's public.

Or can it be proven that such a construct is not possible?

In case I'm not specific enough in what I'm asking, such a construct would allow for a sponge construction with no hidden state because no inverse permutation for it can be found.


texts: AES CBC: how shall i get to know with AES CBC method, the received Cipher Text is padded or not

texts:
Algorithm: AES - CBC mode with PKCS7 padding

KeyValue:

10a58869d74be5a374cf867cfb473859

IV:

00000000000000000000000000000000

Plaintext:

00000000000000000000000000000000

Expected ciphertext:

6d251e6944b051e04eaa6fb4dbf78465

Three steps are used to compute the CBC Encrypt as mentioned below:

CBC_Start(Key,IV)
CBC_Update(Plaintext, plaintext length, Ciphertext, Ciphertextlength)
CBC_Finish(Ciphertext, Ciphertextlength)

Ciphertext is obtained when the update is finished, but when finish is completed, the ciphertext obtained is different from what is expected.

Why is this happening?


texts:
I have a question. For example I have text: "The quick brown fox jumps over the dog!"

It has 32 letters. If I encrypt the first 16 letters with key: "11111111111111111111111111111111" and nonce: "1111111111111111" and next 16 letters with the same key and nonce will it be secure?


texts: Are there asymmetric cryptographic algorithms that are not based on integer factorization and discrete logarithm?

texts:
In the computer security class (in which cryptography is a big chapter) that I took, I remembered the professor said about current asymmetric cryptography algorithms are based on integer factorization (i.e. prime numbers) and discrete logarithm.

So my question is, are there any asymmetric cryptographic algorithms that are not based on these two mathematical fields? Is it that hard to come up with a strong algorithm without using prime numbers and logarithm?


texts: What is the most secure/reliable CSPRNG currently available?

texts: In terms of period length, uniformity/distribution, what is the most secure/reliable CSPRNG currently available?


texts: Is there any cryptosystem that works on floating point real number?

texts: I see that all cryptosystems are work on finite field. But i consider that have any cryptosystem that works on real number (do not consider the round step and it also can be an estimate cipher)


texts: Why don't table lookups run in constant time?

texts: The Wikipedia article on big O notation says that performing a lookup is a constant time operation. So why are lookup tables susceptible to timing attacks?


texts:
According to Wikipedia, CMAC is based on a variation of CBC-MAC and fixes some security deficiencies in it.  However, I could not find a simple and clear explanation of what the differences between the two algorithms actually are, so I thought I'd ask here:

How does CMAC differ from CBC-MAC, and why?


texts: Timestamping services authorities, utilizing Linked, hybrid and other than PKI schemes

texts:
What are well respected Cryptographic Timestamping authorities utilizing more sophisticated than just PKI (RFC 3161) schemes, like Linked, Linked and signed, distributed hash trees (maybe P2P?), hybrid ?

Is there any good resource (better than googling, what does not give information about how well service is respected).

I would love to use Keyless Signatures (different thank PKI schemes), preferably remaining reliable if PKI would be compromised (e.g. Linked and signed, distributed, hybrid, etc).

I know about such interesting approach:
http://www.guardtime.com/signatures/technology-overview/ ,
but I would like to used a few (for better reliability - to achieve tens of years reliability) different approaches.

Preferably those well respected timestamps to be legally respected (e.g. Securo "Conforms to EU and US federal standards)


texts: Bit commitment, two blobs with same bit, without revealing it?

texts:
Suppose we have bit commitment scheme:
$n=p*q$ and $t \in QNR_n$, with Jacobi $(\frac{t}{n})=1$

Commitment(P), random $x\in \mathbb{Z}_n$, $y=x^2t^b$, where $b$ is bit.

Ok, suppose we have $y_1$ and $y_2$ blobs containing same $b$

How P can prove that both blobs contain same bit without revealing it?


texts: Is there a reason that the N value in scrypt is limited to powers of two?

texts:
I have been looking at the scrypt hashing algorithm and am confused as to why the N value, which determines the overall cost, is limited to powers of two. There are only 3 things that the N value actually affects

The amount of times to mix with salsa (via two loops with N being the count)
The amount of memory required to compute a hash
And one seemingly minor portion of mixing:

The mixing that relies on N is this:

for (i = 0; i < N; i++) {
    j = 32 * (X[16] & (N-1));
    for (k = 0; k < 32; k++)
        X[k] ^= V[j + k];
    xor_salsa8(&X[0], &X[16]);
    xor_salsa8(&X[16], &X[0]);
}

Would using N values that aren't a power of two compromise this mixing in some way?


texts: CSPRNG unique seeds and proving uniform output

texts:
I have two related questions concerning cryptographically secure pseudo random number generators.

My first question is as follows: are there conditions on the definition of cryptographically secure pseudo random number generators that require distinct seeds to generate distinct (periodic) sequences?  What if a generator has the property that two distinct seeds generate the same sequence, but the generator is provably secure?  Can this property be ignored then or is it a requirement that distinct seeds generate distinct pseudo random sequences?

My next question concerns the paper by Blum, Blum, and Shub introducing the $x^2 \mod N$ Generator.  After reading the paper and learning about the generator, it is clear that the outputs of the generator pass statistical tests for randomness, but it is unclear to me how the authors proved the output of the generator is uniformly random.  Would anyone be able to walk me through a sketch of the proof showing the output of the generator is uniformly random (backwards secure)?


texts: Looking for books and non-paywalled websites about Enigma "rapid analytic machinery"

texts: I am by now perfectly aware that "Bletchley Park had much more available to them than 'Bombes,'" but I'm finding it difficult to find on-line explanations of their many other types of "rapid analytic machinery" which are not shielded by "paywalls."  No, I really am not interested in paying $75.00 (USD) for access to a single article.  Therefore, what books and/or article sources might you recommend?


texts:
currently I am working on some secure accounting application. I have few requirements:

Application should store items which can be searched by name.
Every item has price and tax.
Every invoice contains arbitrary amount of different items.
Every invoice has gross and net sum of items

My idea is to use rsa or ElGamal schema for multiplication and Pailler for addition. Calculating net sum is pretty easy I can just use pailler for doing it. Problem is with gross sum. In my solution for each item I am doing multiplication: price*tax using RSA and here I am stucked.
I have only one solution in my mind: adding another trusted proxy to my system which will receive result of each multiplication, decrypt it and encrypt using Pailler scheme and than send it back to my server (which now can sum gross values of each item). That solution requires a lot of communication between server and proxy and client has to give his private keys to the proxy. Do you have any idea how can I improve it?
Thanks in advance!


texts: How does Twofish avoid weak keys if it uses key-dependent S-boxes?

texts:
From section 7.2.2 of the Twofish paper, the four S-boxes for the 128-bit cipher are generated with:

$$\begin{align}
s_0(x) &= q_1[q_0[q_0[x] \oplus s_{0,0}] \oplus s_{1,0}]\\
s_1(x) &= q_0[q_0[q_1[x] \oplus s_{0,1}] \oplus s_{1,1}]\\
s_2(x) &= q_1[q_1[q_0[x] \oplus s_{0,2}] \oplus s_{1,2}]\\
s_3(x) &= q_0[q_1[q_1[x] \oplus s_{0,3}] \oplus s_{1,3}]
\end{align}$$

Here, $q_0$ and $q_1$ are fixed 8-bit permutations, and $s_{i,j}$ are bytes derived from the keys indirectly via a Reed–Solomon matrix. They claim that this scheme does not produce any weak S-boxes:

  Few or no keys may cause the S-boxes used to be “weak,” in the sense of having high-probability differential or linear characteristics, or in the sense of having a very simple algebraic representation

Why is this? How can Twofish avoid weak keys while using key-dependent S-boxes?


texts: Why to try get key out of white box crypto? How can one protect WBC itself?

texts:
Help me understand the following. With WBC the question is mainly being stated as can one try to break WBC to identify the key. My question is: Why would one ever want to do that anyways?

If one can locate the WBC itself it should be enough to enc/dec anything she wants with the embedded key. To me it comes to chicken and egg problem where now one would need to "hide" WBC itself within the code to make it any practical.