knotty problems
[ arguably cryptanalysis-like ] Computer analysis provides Incan string theory * 19:00 11 August 2005 * NewScientist.com news service * Will Knight Computer analysis reveals that information is collated from some Khipu into high level ones The mystery surrounding a cryptic string-based communication system used by ancient Incan administrators may at last be unravelling, thanks to computer analysis of hundreds of different knotted bundles. The discovery provides a tantalising glimpse of bureaucracy in the Andean empire and may, for the first time, also reveal an Incan word written in string. Woven from cotton, llama or alpaca wool, the mysterious string bundles - known as Khipu - consist of a single strand from which dangle up to thousands of subsidiary strings, each featuring a bewildering array of knots. Of the 600 or so Khipu that have been found, most date from between 1400 AD and 1500 AD. However, a few are thought to be about 1000 years old. Spanish colonial documents suggest that Khipu were in some way used to keep records and communicate messages. Yet how the cords were used to convey useful information has puzzled generations of experts. Now, anthropologist Gary Urton and mathematician Carrie Brezine at Harvard University, Massachusetts, US, think they may have begun unravelling the knotty code. The pair built a searchable database containing key information about Khipu strings, such as the number and position of subsidiary strings and the number and position of knots tied in them. The pair then used this database to search for similarities between 21 Khipus discovered in 1956 at the key Incan administrative base of Puruchuco, near modern day Lima in Peru. Superficial similarities suggested that the Khipu could be connected but the database revealed a crucial mathematical bond - the data represented by subsidiary strands on some of Khipu could be combined to create the strands found on more complex ones. This suggests the Khipu were used to collate information from different parts of the empire, which stretched for more than 5500 kilometres. Brezine used the mathematical software package Mathematica to scour the database for other mathematical links - and found several. "Local accountants would forward information on accomplished tasks upward through the hierarchy, with information at each successive level representing the summation of accounts from the levels below," Urton says. "This communication was used to record the information deemed most important to the state, which often included accounting and other data related to censuses, finances and the military." And Urton and Brezine go a step further. Given that the Puruchuco strings may represent collations of data different regions, they suggest that a characteristic figure-of-eight knot found on all of the 21 Puruchuco strings may represent the place itself. If so, it would be the first word to ever be extracted from an Incan Khipu. Completely deciphering the Khipu may never be possible, Urton says, but further analysis of the Khipu database might reveal other details of life. New archaeological discoveries could also throw up some more surprises, Urton told New Scientist. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Number of rounds needed for perfect Feistel?
On Fri, 12 Aug 2005, Tim Dierks wrote: > I'm attempting to design a block cipher with an "odd" block size (34 > bits). I'm planning to use a balanced Feistel structure with AES as the > function f(), padding the 17-bit input blocks to 128 bits with a pad > dependent on the round number, encrypting with a key, and extracting the > low 17 bits as the output of f(). > > If I use this structure, how many rounds do I need to use to be secure (or > can this structure be secure at all, aside from the obvious insecurity > issues of the small block size itself)? I've been told that a small number > of rounds is insecure (despite the fact that f() can be regarded as > "perfect") due to collisions in the output of f(). However, I don't > understand this attack precisely, so a reference would be appreciated. IIRC the starting point was M. Luby and C. Rackoff, ``How to construct pseudorandom permutations from pseudorandom functions,'' SIAM Journal on Computing, vol. 17, nb 2, pp. 373--386, April 1988. Unfortunately, I was not able to quickly find it online, so you can try any other paper which mentions Luby-Rackoff construction, e.g., http://www.wisdom.weizmann.ac.il/%7Enaor/PAPERS/lr.ps -- Regards, ASK - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Number of rounds needed for perfect Feistel?
Barney Wolff wrote: > On Fri, Aug 12, 2005 at 11:47:26AM -0400, Tim Dierks wrote: >> I'm attempting to design a block cipher with an "odd" block size (34 >> bits). I'm planning to use a balanced Feistel structure with AES as the >> function f(), padding the 17-bit input blocks to 128 bits with a pad >> dependent on the round number, encrypting with a key, and extracting the >> low 17 bits as the output of f(). > > Pardon a dumb question, but how do you plan on avoiding collisions in > the encrypted values, independent of the number of rounds? Seems to me > that even if the 128-bit encryption is guaranteed to be 1-to-1 with the > plaintext, there is no such guarantee on any subset of the 128 bits. A Feistel network doesn't depend on lack of collision in f(). The Handbook of Applied Cryptography, http://www.cacr.math.uwaterloo.ca/hac/about/chap7.pdf describes it pretty well. - Tim - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: webcast of crypto rumpsession this year?
At this time I believe the answer is no. I set it up last year and have not this year. I take it that there is interest? I will send an email to the group if this changes. Thanks jim On Aug 12, 2005, at 9:07 AM, Mads Rasmussen wrote: Anyone knows whether there will be webcasts from this years Crypto conference? -- Mads Rasmussen Security Consultant Open Communications Security +55 11 3345 2525 - 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: The summer of PKI love
James A. Donald wrote: > -- > From: Stephan Neuhaus > <[EMAIL PROTECTED]> > >>So, the optimism of the article's author aside, where >>*do* we stand on PKI deployment? > > > PKI's deployment to identify ssl servers is near one > hundred percent. PKI's deployment to sign and secure > email, and to identify users, is near zero and seems > unlikely to change. PGP has substantially superior > penetration. I would rank it closer to 0% myself. Don't get me wrong, we have plenty of PK deployment with SSL servers, just no I. Anyone doing revocation checking? How do you even do it? CRL? Delta CRL? OSCP? Do any browsers really support these things? For those that do does any user actually know how to do it? PKI is a massive undertaking that many seem to confuse with just public key cryptography. Public key crypto is just one component of PKI, and frankly I know VERY few groups that are actually doing PKI and doing it right. What we have are a couple dozen certificate authorities that were deemed trustworthy by Microsoft that do not pop up warnings, and the rest that do pop up warnings that most people blissfully ignore. HTTPS is really good for encryption, absolutely sucks in practice for trust. -- Mark Allen Earnest Lead Systems Programmer Emerging Technologies The Pennsylvania State University KB3LYB smime.p7s Description: S/MIME Cryptographic Signature
Re: The summer of PKI love
-- From: Stephan Neuhaus <[EMAIL PROTECTED]> > So, the optimism of the article's author aside, where > *do* we stand on PKI deployment? PKI's deployment to identify ssl servers is near one hundred percent. PKI's deployment to sign and secure email, and to identify users, is near zero and seems unlikely to change. PGP has substantially superior penetration. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG 5l+2/VgKKsZ7L2MtEJUMxtB3jqOuld2RYZgm3QcV 4HS67bQDIU6jSwHy8CH7u3qvqnY5XGqLUbRMG5mgy - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: [Clips] The summer of PKI love
-- From: "Stefan Kelm" <[EMAIL PROTECTED]> > The usage of X.509 certificates and related PKI > techniques is getting more and more common. It enables > users to sign and encrypt messages, to use secure > communication channels for internet communication and > to authenticate themselves to all kind of network > services. The overall level of security for the usage > of public key cryptography depends heavily on that of > the private key, which is usually installed on the > local host of the user. This poses not only a security > risk but it does also restrict the increasing user > demand for mobility. A solution to these problems can > be smart cards and USB-tokens, which store private > keys in such a way that they cannot be retrieved from > these If the token has no user interface, or minimal user interface, and the mobile user uses the token to log on to a corrupted computer, then the adversary has control of the token, even though the rightful user retains physical control of the token. --digsig James A. Donald 6YeGpsZR+nOTh/cGwvITnSR3TdzclVpR0+pr3YYQdkG k8jT9lI+qnD2l9zmgoEnD1dREI6nEAq21MKjTBy2 4l82lryIH7nTP4rjhCMmKYcuZkd3xQSd8Mtpt1S8d - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: How much for a DoD X.509 certificate?
John Saylor wrote: > as i understand it, the problem here was that credentials were issued by > an untrustworthy agent. you can have this scenario both online and off. > how does being online solve the problem of a compromised issuing > authority? the justification for having offline credentials typically has been because 1) the technology isn't available for doing an online infrastructure for accessing the real data or 2) the value of the operation doesn't justify the cost & expense of having a real online infrastructure. the statement was that most modern day infrastructures have gone to real online operations where the real information is accessed rather than substitute offline credential this transition has been 1) the online technology to access the real information is becoming more ubiquitous, 2) the cost of doing online access to the real information has been dropping, 3) many of the security sensitive infrastructures realize that they now can easily justify any incremental expense of full online operation (including the additional benefits of being able to analyze activity across multiple sequences of security related events ... rather than each individual security event occuring in offline isolation purely based on the contents of the offline credential). I've frequently explained the analogy that offline credentials are basically a read-only cache of the real information stored in a repository some place. they are a direct analogy (modulo possibly the read-only characteristics) of distributed cpu cache/memory, distributed databases, ... any kind of distributed operation where specific activities go on referencing in isolation the local read-only copy. so if you physically compare direct access operation to the real information (including the ability to have a global view of operations across individual events and be able to re-act and correct in real time) ... vis-a-vis offline, isolated, distributed operation involving the copies there are a significantly larger number of places that directly touch the distributed read-only copies which can possibly result undetected corruption (compared to direct accesses to the real information). it isn't that there aren't touch points that can corrupt the real information ... it is just that there possibly are several orders of magnitude fewer touch points that can corrupt the real information. in a PKI, certification authority operations ... 1) the "real information" is the authoritative agency responsible for the actual information. 2) typically a certification authority then will create its own repository operation duplicating the real information 3) it creates a certificate containing some subset of the real information which is relatively freely released to the world. the issue is that in the real respository #1 and possibly any certification authority's shadow #2, the possible value of criminal corruption of the real information is a lot higher ... but there tends to be significantly larger number of security countermeasures against there being any sort of corruption. the individual certificate copies released into the wild tends to have much fewer countermeasures and a much large number of infrastructure attack points. in the case of the original ... the information is either correct or it is not correct. in the offline credential copy ... the offline credential copy can 1) be a copy of incorrect information (from the original) or 2) possibly be one of many counterfeit copies containing fraudulent information. so the online infrastructure is not concerned about there being counterfeit copies of the information or ficticious counterfeits (of information that doesn't even exist at the original) ... because copies don't exist. online infrastructure, however is concerned about valid authentication and the counterfeiting of valid authentication information. i contend that this is a much narrower exposure than the exposure of having generalized counterfeit information floating around random locations in the infrastructure. furthermore, the online infrastructure has much greater capability for tracking and potentially recognizing counterfeit authentication operation and furthermore, being able to react to it in real time. So somewhat after I was making statements about online infrastructure having much fewer and narrower corruption points, having more capability for recognizing compromises (being able to analyze patterns across multiple security related events) and doing real-time re-acting ... there started appearing things like OCSP. However, i claim that if you can do an a real-time, online operation ... you are incurring the majority of the expense of doing a real-time, online operation ... and therefor you would have much higher integrity simply transitioning to a real-time, online operation ... and eliminate the offline information that is floating around out in the wild. slightly related recent posting regarding sanity c
Number of rounds needed for perfect Feistel?
I'm attempting to design a block cipher with an "odd" block size (34 bits). I'm planning to use a balanced Feistel structure with AES as the function f(), padding the 17-bit input blocks to 128 bits with a pad dependent on the round number, encrypting with a key, and extracting the low 17 bits as the output of f(). If I use this structure, how many rounds do I need to use to be secure (or can this structure be secure at all, aside from the obvious insecurity issues of the small block size itself)? I've been told that a small number of rounds is insecure (despite the fact that f() can be regarded as "perfect") due to collisions in the output of f(). However, I don't understand this attack precisely, so a reference would be appreciated. Thanks, - Tim - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: How much for a DoD X.509 certificate?
hi > Peter Gutmann wrote: > > http://www.wjla.com/news/stories/0305/210558.html > > http://www.wjla.com/news/stories/0105/200474.html ( 05.08.11 12:55 -0600 ) Anne & Lynn Wheeler: > one might claim that part of this is the lingering affinity to offline > credentials ... when most really secure operations have gone to online > and realtime operations ... as i understand it, the problem here was that credentials were issued by an untrustworthy agent. you can have this scenario both online and off. how does being online solve the problem of a compromised issuing authority? -- \js oblique strategy: imagine the music as a moving chain or caterpillar - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
webcast of crypto rumpsession this year?
Anyone knows whether there will be webcasts from this years Crypto conference? -- Mads Rasmussen Security Consultant Open Communications Security +55 11 3345 2525 - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: [Clips] The summer of PKI love
> On the token front, we're still unfortunately waiting for the ideal key > storage device. USB tokens, smart cards, and cell phones are all > candidates, and the pros and cons of these options form a complex matrix. > Universities tend to prefer the USB approach because the tokens work with > PCs and Macs that can't easily be outfitted with card readers. On that subject I highly recommend a report very recently published by DFN-CERT and SurfNET. http://www.dfn-pca.de/bibliothek/reports/pki-token/ : Abstract The usage of X.509 certificates and related PKI techniques is getting more and more common. It enables users to sign and encrypt messages, to use secure communication channels for internet communication and to authenticate themselves to all kind of network services. The overall level of security for the usage of public key cryptography depends heavily on that of the private key, which is usually installed on the local host of the user. This poses not only a security risk but it does also restrict the increasing user demand for mobility. A solution to these problems can be smart cards and USB-tokens, which store private keys in such a way that they cannot be retrieved from these. Instead data can be send to these devices and is being processed, decrypted or signed, by the device itself and only then the results are provided by these devices for further processing. These devices are very promising for the widespread usage of PKI. In a PC- dominated world the USB-tokens have the advantage, that no additional reader is necessary to use them even on foreign hosts. Both types of devices, smart cards and USB-tokens, still need support by the underlying operating systems and by the used applications. This makes it very difficult to decide which token may be successfully used in any given environment and will meet the demands of the applications and indented usage. This report tries to ease the decision process when selecting a token for a particular environment and platform. For this purpose a number of the available tokens were tested together with the most common applications on the most commonly used operating systems. A reproduceable test framework was established to ensure the comparability and re-usability of these tests. Overall it is safe to say in a homogenous environment with commonly used applications the tested tokens perform well. Nevertheless rolling out tokens on a large scale is still not something to be undertaken on a friday afternoon. [snip] Cheers, Stefan. --- Stefan Kelm Security Consultant Secorvo Security Consulting GmbH Ettlinger Straße 12-14, D-76137 Karlsruhe Tel. +49 721 255171-304, Fax +49 721 255171-100 [EMAIL PROTECTED], http://www.secorvo.de/ --- PGP Fingerprint 87AE E858 CCBC C3A2 E633 D139 B0D9 212B - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: The summer of PKI love
Anne & Lynn Wheeler wrote: http://www.infoworld.com/article/05/08/10/33OPstrategic_1.html The page goes on to say: "One reason for PKI's slow uptake has been the lack of two kinds of portability. It hasn't been easy to move cryptographic keys from one machine to another, or to use credentials issued by one institution at another. But as we learned at the summit, there's been progress on both fronts." If I remember correctly, portability is not necessarily a thing to strive for here, because it means that not only your certificates will be transported from A to B, but also the corresponding private information will have a tendency to leak all over the place. Also, cross-certification (mentioned later in the article) is probably hard to do right because it is an extension of trust that needs to be carefully managed, if it can be done at all. So, the optimism of the article's author aside, where *do* we stand on PKI deployment? Fun, Stephan begin:vcard fn:Stephan Neuhaus n:Neuhaus;Stephan org;quoted-printable:Universit=C3=A4t des Saarlandes;Department of Informatics adr;quoted-printable:;;Postfach 15 11 50;Saarbr=C3=BCcken;;66041;Germany email;internet:[EMAIL PROTECTED] title:Researcher tel;work:+49-681/302-64018 tel;fax:+49-681/302-64012 x-mozilla-html:FALSE url:http://www.st.cs.uni-sb.de/~neuhaus version:2.1 end:vcard
Re: Motorist wins case after maths whizzes break speed camera code
Looking at the article and the links that were posted here, 1. It appears that the defense won only because the prosecution did not come up with an expert to refute the defense expert. He could have argued based on Goedel's Theorem or the Heisenberg Uncertainty Principle and the case would have gone the same way. 2. "The NRMA has called for a full audit of the way the state's 110 enforcement cameras are used ..." Note that NRMA is a motorist association, like the AAA in the US. This is not a government body nor anyone with authority calling for an audit. 3. The expert may not have outright lied by saying that the MD5 collision result "theoretically" means that RTA could change the speed without changing the hash, but his definition of "theoretically" has to include "leaving it in the realm of theory by not trying to think the problem through". This is not a situation where you can throw some random looking bits in to make the hash come out right. Actually reading the article again I don't see it made explicit that the person quoted was the expert used by the defense or if he is just someone the reporter went to for a comment on the story. For all we know the defense lawyer made the claim that "People have shown it [MD5] has been hacked and it's open to viruses," and without a prosecution rebuttal that was enough. 4. The marketing speak that Aram linked to is not all that bad for marketing people making a hash of technical jargon they have been given. My assumption is that they sign the time, date, place, numberplate and speed record using RSA/MD5. Trying to explain that to a non-techie and they will hear the words public key, encryption, and MD5 hash, so it is not unreasonable for them to write "public key authenticated using MD5 encryption to ensure information is authentic and tamper free". 5. Back to point #3, the attack on MD5 doesn't seem to cast doubt on the signed data from the speed camera, as long as one can trust that the private key is safely hidden in the camera. As Aram pointed out it is easy to show that no possible speed, time and date will hash with the same numberplate to get the same value. -- Sidney Markowitz http://www.sidney.com - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
