Re: New result in predicate encryption: disjunction support

2008-05-06 Thread Ariel Waissbein
Jonathan Katz wrote:
 On Mon, 5 May 2008, Ariel Waissbein wrote:
 
 [Moderator's note: Again, top posting is discouraged, and not editing
 quoted material is also discouraged. --Perry]

 Hi list,

 Interesting. Great work! I had been looking *generic* predicate
 encryption for some time. Encryption over specific predicates is much
 older. Malware (e.g., virus) and software protection schemes have been
 using some sort of predicate encryption or trigger for over two
 decades in order to obfuscate code. For example, an old virus used to
 scan hard drives looking for a BBS configuration files in a similar
 manner and some software protection schemes have encrypted pieces of
 code that are decrypted only if some integrity checks (predicates) over
 other pieces of the program are passed.

 Triggers/predicates are very promising. Yet, they are only useful in
 certain applications, since eavesdropping one decryption is enough to
 recover the keys and plaintext.

 I co-authored a paper were we used this same concept in a software
 protection application ([1]) and later we formalized this concept, that
 we called secure triggers, in a paper eventually publised at TISSEC
 ([2]). We were only able to construct triggers for very specific
 predicate families, e.g.,
  - p(x)=1 iff x=I for some I in {0,1}^k
  - q(x,y,z,...)=1 iff x=I_1, y=I_2, z=I_3,...; and finally
  - r(x)=1 iff x_{j_1}=b_1,...,x_{j_k}=b_k for some b_1,...,b_k in {0,1}
and indexes i_1,...,i_k (|x|=k).
 While these predicates do not cover arbitrary large possibilities, they
 are implemented by efficient algorithms and require assuming only the
 existence of IND-CPA secure symmetric ciphers. In [2] we came up with
 more applications other than sofprot;)

 [1] Diego Bendersky, Ariel Futoransky, Luciano Notarfrancesco, Carlos
 Sarraute and Ariel Waissbein. Advanced Software Protection Now. Core
 Security Technologies Tech report.
 http://www.coresecurity.com/index.php5?module=ContentModaction=itemid=491


 [2] Ariel Futoransky, Emiliano Kargieman, Carlos Sarraute, Ariel
 Waissbein. Foundations and applications for secure triggers. ACM TISSEC,
 Vol 9(1) (February 2006).

 Cheers,
 Ariel
 
 Predicate encryption sounds very different from the work you are
 referencing above. (In particular, as we discuss in the paper, predicate
 encryption for equality tests is essentially identity-based encryption.)
 I refer you to the Introduction and Definition 2.1 of our paper, which
 should give a pretty good high-level overview.
 

Hi Jonathan,

and thanks for taking your time to answer. I had already read the
Introduction and had a quick --i admit-- read over the paper before
posting to the list. I think that the main difference are the
applications we are looking at (and I know Sahai's earlier work in
obfuscation). Take a look at the first three sentences of our article:

 Fix a bitstring, that we regard as a secret. Let be given a family of 
 predicates, and
 secretly draw a predicate from this family according to a known distribution. 
 Think
 of predicates as functions with range in {true, false}. We consider 
 algorithms that
 return the secret if their input evaluates to true on the chosen predicate, 
 else they
 return nothing.

Of course, the main difference is that one must hold SK (and f) in order
to decrypt messages according to the predicate encryption scheme. Note
that if the adversary is given the algorithm i\mapsto SK_{f_i} then
predicate encryption turns out to be similar to generic secure triggers.
However, we didn't cover predicates evaluating inner product so that's
what caught my interest, why I want to analyze how your work applies to
other problems (and why I think that the schemes are similar).

Cheers,
Ariel

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: New result in predicate encryption: disjunction support

2008-05-05 Thread Ariel Waissbein
[Moderator's note: Again, top posting is discouraged, and not editing
quoted material is also discouraged. --Perry]

Hi list,

Interesting. Great work! I had been looking *generic* predicate
encryption for some time. Encryption over specific predicates is much
older. Malware (e.g., virus) and software protection schemes have been
using some sort of predicate encryption or trigger for over two
decades in order to obfuscate code. For example, an old virus used to
scan hard drives looking for a BBS configuration files in a similar
manner and some software protection schemes have encrypted pieces of
code that are decrypted only if some integrity checks (predicates) over
other pieces of the program are passed.

Triggers/predicates are very promising. Yet, they are only useful in
certain applications, since eavesdropping one decryption is enough to
recover the keys and plaintext.

I co-authored a paper were we used this same concept in a software
protection application ([1]) and later we formalized this concept, that
we called secure triggers, in a paper eventually publised at TISSEC
([2]). We were only able to construct triggers for very specific
predicate families, e.g.,
  - p(x)=1 iff x=I for some I in {0,1}^k
  - q(x,y,z,...)=1 iff x=I_1, y=I_2, z=I_3,...; and finally
  - r(x)=1 iff x_{j_1}=b_1,...,x_{j_k}=b_k for some b_1,...,b_k in {0,1}
and indexes i_1,...,i_k (|x|=k).
While these predicates do not cover arbitrary large possibilities, they
are implemented by efficient algorithms and require assuming only the
existence of IND-CPA secure symmetric ciphers. In [2] we came up with
more applications other than sofprot;)

[1] Diego Bendersky, Ariel Futoransky, Luciano Notarfrancesco, Carlos
Sarraute and Ariel Waissbein. Advanced Software Protection Now. Core
Security Technologies Tech report.
http://www.coresecurity.com/index.php5?module=ContentModaction=itemid=491

[2] Ariel Futoransky, Emiliano Kargieman, Carlos Sarraute, Ariel
Waissbein. Foundations and applications for secure triggers. ACM TISSEC,
Vol 9(1) (February 2006).

Cheers,
Ariel

Ivan Krsti? wrote:
 This is fairly interesting: AFAIK the first generalization of predicate
 encryption to support disjunctions. I find the result mostly interesting
 mathematically, since I expect we won't be seeing predicate encryption
 in widespread use anytime soon due to complexity and regulatory
 concerns. --IK
 
 
 
 Predicate Encryption Supporting Disjunctions, Polynomial Equations, and
 Inner Products
 Jonathan Katz and Amit Sahai and Brent Waters
 
 Preprint: http://eprint.iacr.org/2007/404
 
 Abstract: Predicate encryption is a new paradigm generalizing, among
 other things, identity-based encryption. In a predicate encryption
 scheme, secret keys correspond to predicates and ciphertexts are
 associated with attributes; the secret key SK_f corresponding to the
 predicate f can be used to decrypt a ciphertext associated with
 attribute I if and only if f(I)=1. Constructions of such schemes are
 currently known for relatively few classes of predicates.
 We construct such a scheme for predicates corresponding to the
 evaluation of inner products over N (for some large integer N). This, in
 turn, enables constructions in which predicates correspond to the
 evaluation of disjunctions, polynomials, CNF/DNF formulae, or threshold
 predicates (among others). Besides serving as what we feel is a
 significant step forward in the theory of predicate encryption, our
 results lead to a number of applications that are interesting in their
 own right.
 
 -- 
 Ivan Krsti? [EMAIL PROTECTED] | http://radian.org
 
 -
 The Cryptography Mailing List
 Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
 

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


WEP's dead-er: The Final Nail in WEP’s Coff in

2006-08-20 Thread Ariel Waissbein
IMHO, an interesting read:

tapir.cs.ucl.ac.uk/bittau-wep.pdf

The Final Nail in WEP’s Coffin

Bittau, A.   Handley, M.   Lackey, J.
University College London;

This paper appears in: Security and Privacy, 2006 IEEE Symposium on
Publication Date: 21-24 May 2006
On page(s): 386- 400

Authors present an attack that allows you to send arbitrary
data on a WEP network after having eavesdropped a
single data packet!! Next, communicate with every host in the router's
LAN. And finally decrypt packets in real-time.


Ariel


-- 
Ariel Waissbein
CORE SECURITY TECHNOLOGIES

http://www.coresecurity.com/corelabs






-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Solving systems of multivariate polynomials modulo 2^32

2006-08-14 Thread Ariel Waissbein
Hi Danilo,

Maybe you should use some other function in Mathematica. Symbolic
solving polynomial equations is a very difficult task (e.g.,
doubly-exponential worst case time complexity). But in this case it
shouldn't take that much time.


Let me notice that Z_{2^32} is not the same as F_{2^32} the field of
2^32 elements. I presume that you mean the former, which is not a field!
If you mean the latter, then you are using the wrong domain
specification in Reduce.

If you meant the field of 2^32 elements, then you should check how to
specify this in Mathematica.

For option Z_{2^32} you could try to solve the system (with elimination)
over the rationals, and once you eliminated variables look at
everything in the integers (multiplying by the LCM of the denominators)
and then simply take modulo 2^32 over all the solutions! If the system
of 3 polynomials in 3 variables is generic-enough it should have only
finite solutions.

If you want to continue using Mathematica, you can try your luck with
functions such as Solve or GroebnerBasis. There exist alternatives to
Groebner basis which I prefer personally, such as the Kronecker solver
(http://www.math.uvsq.fr/~lecerf/software/kronecker/) which comes as a
Magma package.

I hope this helps.

Cheers,

Ariel


Danilo Gligoroski wrote:
 Hi,
 In order to solve a system of 3 polynomials of order 3
 with 3 variables x1, x2 and x3 in the set Z_{2^32} and
 coeficients also in Z_{2^32} I used the Mathematica
 5.1 function Reduce[...,{x1,x2,x3},Modulus-2^32]. It
 is giving the solutions but it is not very fast. I
 wanted to programe a procedure in C in order to get
 more speed in the computation.
 
 I was trying to figure out what algorithms are used in
 the Reduce function of Mathematica (reading Wolfram
 web pages) but I couldn't find any specific
 information for the algorithms they are using for
 solving multivariate polynomials modulo 2^32.
 
 I found several papers that are dealing with solving
 univariate or multivariate polynomials in finite
 fields such as:
 
 1. Lauder :
 http://www.maths.ox.ac.uk/~lauder/papers/LauderManyVarSept16.pdf
 2. van de Woestijne :
 http://www.math.leidenuniv.nl/~cvdwoest/maths/ober.pdf
 and 
 http://www.math.leidenuniv.nl/~cvdwoest/maths/issac2005.pdf
 3.  Barreto and Voloch:
 http://www.ma.utexas.edu/users/voloch/Preprints/roots.pdf
 4. Ding, Gower and Schmidt:
 http://eprint.iacr.org/2006/038.pdf
 
 but the algorithms there are for soving polynomials
 over finite fields GF(p) or GF(p^n) which is different
 than just solving polynomials (univariate or
 multivariate) modulo 2^32.
 
 I will appreciate any hint or coment.
 
 Regards,
 Danilo Gligoroski
 
 -
 The Cryptography Mailing List
 Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
 



-- 
Ariel Waissbein
RESEARCHER
CORE SECURITY TECHNOLOGIES

Tel./Fax: (54-11) 5556-2673
Humboldt 1967, 2do piso
Capital Federal,
Argentina

http://www.coresecurity.com/corelabs




-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: [IP] more on Can you be compelled to give a password?

2006-08-07 Thread Ariel Waissbein
Hi,

Please notice that a second distress password becomes useless if the
would-be user of this password has access to the binaries (that is, the
encrypted data), e.g., because he will copy them before inserting the
password and might even try to reverse-engineer the decryption software
before typing anything. So I'm not sure what is the setting here.

Cheers,
Ariel

Ed Gerck wrote:
 List,
 
 the Subject says it all. This might be of interest
 here, for comments.
 
 
 The answer is definitely NO even for the naive user,
 just requiring the tech-savvy for set up. Several
 examples are possible.
 
 John Smith can set two passwords, one for normal use
 and the other when in distress. The distress password
 may simply announce that the data is expired or, more
 creatively, also make the data unreadable.
 
 John Smith can also set two passwords, one of them
 unknown to him but known to a third-party (that
 John S does not have to trust) that is subject to
 a different jurisdiction /or rules /or is in another
 place. John Smith may comply with any demand to
 disclose his password but such a demand may not be
 effective for the third-party.
 
 John Smith can have the data, encrypted with a key
 controlled by his password, sitting on some Internet
 server somewhere. John S never carries the data
 and anyone finding the data does not know to whom it
 belongs to.
 
 John Smith can also use keys with short expiration
 dates in order to circumvent by delay tactics any
 demand to reveal their passwords, during which time
 the password expires.
 
 Of course, this is not really a safe heaven for
 criminals because criminal activity is often detected
 and evidenced by its outside effects, including
 tracing.
 
 Cheers,
 Ed Gerck
 
 -
 The Cryptography Mailing List
 Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
 

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: MD5 trick

2006-04-19 Thread Ariel Waissbein
Hi Vlastimil and group,

Gera Richarte has done some interesting work with executable files that
have the same MD5 hash. Take a look at
http://www.coresecurity.com/corelabs/projects/research_topics.php
to see his talk at PacSec `05 and Two executable files with the same
MD5 hash, crc32, checksum32 and checksum16.

Regards,
Ariel

vlastimil.klima wrote:
 The trick could be shortly expressed as follows:
 Give me three files and I will give you another three with the
 same MD5 hash
 


-- 
Ariel Waissbein
RESEARCHER
CORE SECURITY TECHNOLOGIES

http://www.coresecurity.com/corelabs






-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: solving, simplification and factorization of boolean equations

2005-11-18 Thread Ariel Waissbein
Dear Travis,

simplification can be reduced to elimination, which is indeed
intractable in the general case (for real-sized problems). (I am
assuming that you need to simplify a big system; however if you only
want to simplify a small SBox, then brute forcing might do.). The
standard citation on itnractability is [E. Mayr and A. Meyer. The
complexity of the word problem for commutative semigroups. Adv. in
Math., 46:305–329, 1982.] or Philippon et al.'s article. A more
comprehensive approach can be found in [D. Castro, M. Giusti, J. Heintz,
G. Matera, L.M. Pardo. The hardness of polynomial equation solving.
Found. Comput. Math.  3  (2003).]; see also the citations in their
Intro). The intractability of elimination is well known at least since
Grete Hermann (http://en.wikipedia.org/wiki/Grete_Hermann), and most
probably since the end of the 19th century.

In my opinion simplification is a means and not an end, and indeed a
very intractable mean. On the other hand, form your email I gather that
your end is to solve these equations.

In polynomial equation solving, special cases are what counts. There is
a lot of debate on what are good options for elimination, today there
are different approaches presenting families of algorithms that are
efficient on certain problem instances. Briefly I would classify the
options as:

1-rewriting techniques (ie Groebner bases),

2-path-following techniques (e.g., [L. Blum, F. Cucker, M. Shub, S.
Smale, Complexity and Real Computation, Springer, New York Berlin
Heidelberg, 1998.], [B. Huber, B. Sturmfels, A polyhedral method for
solving sparse polynomial systems, Mathematics of Computation 64 (112)
(1995).]),

3-numeric techniques (e.g., [W. Rheinboldt, Methods for solving systems
of nonlinear equations, vol. 70 of CBMS-NSF Regional Conf. Series in
Appl. Math., SIAM, Philadelphia, 1998.),

4-an algorithms family based on flat deformations (e.g., [M. Giusti, K.
Haegele, J. Heintz, J.E. Morais, J.L. Monta~na, L.M. Pardo, Lower bounds
for Diophantine approximation, J. Pure Appl. Algebra 117,118 (1997)] and
its predecessors; see http://tera.medicis.polytechnique.fr)

There are also many ad hoc constructions (e.g., in crypto) that can be
used on very specific problems. I think this is all. I might be
unwittingly omitting some other option. Im sorry if I am.

I can only speak for the latter technique (4), in which I have
contributed; in fact, together with other coauthors we will be releasing
a paper which attacks the problem of polynomial equation solving as
applied to public-key schemes based on polynomial equations. I have not
analyzed block ciphers, which yeild higher degree equations (as compared
to the quadratic equations of typical public-key schemes).

I hope that this helps, and feel free to mail me on any other questions.

Best,
Ariel


Travis H. wrote:
 Does anyone have any references on how one would go about creating
 manipulating the boolean equations that govern symmetric ciphers?

 I know that most of the time ciphers describe an algorithm, often
 using tables (S-boxes and E-tables) in lieu of providing equations,
 and I'm wondering how one goes about generating the equations for each
 bit of the output.

 One thing I've always been curious about is the minimum amount of work
 (in terms of a primitive boolean gate such as NAND) necessary to
 compute the output values.  Could there be tables derived from
 equations so cleverly arranged that brute forcing is very simple once
 you know the original equations, but their exact structure is not
 evident from the tables themselves?

 Once you have some equations, how would you go about simplifying them?
  I suspect that finding the simplest form is probably NP-hard, but I'm
 not certain and don't quite know where to start reading on the
 subject.
 --
 http://www.lightconsulting.com/~travis/  --
 We already have enough fast, insecure systems. -- Schneier  Ferguson
 GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B

 -
 The Cryptography Mailing List
 Unsubscribe by sending unsubscribe cryptography to
[EMAIL PROTECTED]


-- 
I was scared. Petrified. Because (x) hearing voices isn't like
catching a cold, you can't get rid of it with lemmon tea (y)
it's inside, it is not some naevus, an epidermal blemish you
can cover up or cauterise (z) I had no control over it. It was
there of its own volition, just stopped in and (zz) I was going
bananas.
-Tibor Fischer ``The Thought Gang


Ariel Waissbein
RESEARCHER
CORE SECURITY TECHNOLOGIES

http://www.coresecurity.com/corelabs




-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Cryptography Research wants piracy speed bump on HD DVDs

2005-01-04 Thread Ariel Waissbein
Is there really that much space for marking? Any substantial number of
marked bits will become obvious in the output stream, no?

Is the watermarking system robust? Is it public? And how long ago has 
it been published?
If they are only modifying some bits (in the standard representation), 
then one might probably
be able to alter them. Also notice, that this may harm the quality of 
the image. Intuitively, one
is expected to have a low quality of image if lots of bits are used for 
watermarking, and a low
security if a few bits are used for watermarking.

Regarding blacklists, where are they stored? If they are included in 
every new DVD, then one
doesn't need to buy a new DVD but simply simulate an ID (which is not 
in the blacklist)
for the DVD. So this opens another place where designers may screw up. 
Another attack
is to attempt to delete this blacklist from the DVD.

In another respect, closed p2p communities that exchange movies through 
secure channels
would never get into this revocations lists. So here is another 
inconvenience for this DRM
scheme.

Regards and (almost) merry christmas,
Ariel
-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]