17
May

Privacy Preserving Auctions - Part 1

   Posted by: CRYPTOcrat   in Crypto Application, Encryption

Author:

Sujit P Gujar a long time CRYPTOcrat. More information about Sujit on this link.

Abstract:

In this article, I will talk about what are auctions, what are important issues in online auctions and why cryptography plays an important role in it. I will also provide pointers for technical details n privacy preserving auctions.

Auctions are popular mechanisms used for buying or selling different items through a bidding process. Before going into detail about privacy issues in auctions, I will explain what are two important types of auctions are available. Consider a case where there is a seller who wishes to sell a single unit of an indivisible (that is, the item has to be allocated single piece). There are multiple buyers for this item. For example, auction for an antique painting, auction for oil drilling rights over a region. Each bidder/buyer has maximum willingness to pay. This is referred as valuation or type information of an agent. This information is private to the agents. The auctioneer has to specify what are allocation rules and payment rules. Though there exist plenty of varieties of auctions, the most popular are:

First price auction

Potential buyers submit sealed bids and the highest bidder is awarded the item. The winning bidder pays the price that he or she has bid.

Second Price Auction

This is also called the Vickrey auction. Potential buyers submit sealed bids and the highest bidder is awarded the item. The winning bidder pays a price equal to the second highest bid (which is also the highest losing bid). In first price auction, intelligent bidders, will not bid their valuations. But, Vickrey has shown that in second price auction everybody should bid there maximum willingness to pay.

Online Auction

With the advent of the Internet era, on line auctions are widely used. As the security of the servers is continuously being challenged by hackers and malicious users, some of the players may be able to breach the security and gain some knowledge of the private information of the other players. This type of manipulation is possible by both sellers and buyers. A seller can profitably cheat by examining bids before auction clears and submitting an extra bid under false identity. This type of bidding is called shill bidding. In the case of first price auctions, the seller does not have any advantage to report shill bid as either shill bid wins and trade does not happen or winner pays whatever he has bid. In the case of the second price auction, submitting true type information (that is true bid) is a dominant strategy, irrespective of others’ bids. So if the buyer gets access to the other bids in Vickrey auction, his strategy is not going change. Thus, there is no need to study cheating by the seller in the first price auctions and the cheating by the buyer in the second price auction. However, cheating is possible in the following two scenarios:

1. Manipulative Seller in second Price Auction
2. Manipulative Buyers in first Price Auction

The Case of a Manipulative Seller in Second Price Auction

A seller can profitably cheat in a second price auction. For example, if the bidders in an eBay auction each use a proxy bidder (essentially creating a second-price auction), then the seller may be able to break into the eBay’s server, observe the maximum price that a bidder is willing to pay, and then extract this price by submitting a shill bid just below it using a false identity.

Here is an example to explain this case

Cheating by the seller

Cheating by a seller

Refer to the illustration above. Suppose Mr. C announces an online second price auction for selling an indivisible item. Ms. H participates in this auction and bids her valuation $1000. Mr. C breaks the server before auction is closed and finds out the highest bid by Ms. H and places a shill bid of $999. Ms. H has no option but to pay $999.

The Case of Manipulative Buyers in a First Price Auction

We now consider the case in which the seller is honest, but there is a chance that some of the buyers will cheat and examine the others’ bids before submitting their own (or, alternatively, they will revise their bid before the auction clears).

Here is an example to explain this case

Cheating by a buyer

Refer to the illustration above. Mr. A announces an online first price auction for selling an indivisible item. Ms. H participates in this auction. She has a valuation $1000 for the item and bids $700 in anticipation of maximizing her utility. Ms. C, her competitor who has valuation $730, breaks the server before the auction is closed and finds out the highest bid by Ms. H and places her own bid as $701. Ms C. will win the object, though she has lower valuation.

The above discussion clearly highlights the importance of security and particularly cryptography in auction design. Cryptography can play a bigger role than just solving the problems mentioned above.

Let’s break here for now and we shall continue this discussion in the next part of this article.

To be concluded…

15
May

OpenSSL RNG problem discovered on Debian!

   Posted by: Amit   in Encryption

Well.. Ok.. I promise this will be a short-n-quick one and we SHALT have the article series as planned..

However, this NEWS just shocked me so could not resist of sharing with you all. It won’t be wrong to say most of us would have used OpenSSL package at least once during their professional life as a security developer. It is as good as a cult for many. (If you haven’t and don’t know don’t miss out on the opportunity to do so now. Here is the link to know more OpenSSL.)

I for one have been using openssl since the days it used to be called SSLeay, so that should be far back as 1997. It’s a masterpiece really! One of the most widely used and well supported packages in the Security/Crypto community.

Returning from my strong sentimental attachment to OpenSSL back to the reason for this post. Here is the link that describes the OpenSSL Random Number Generator issue. Friends at SecurityFocus.com has some more details about who is affected by this vulnerability. Here is the link. The issue seriously affects the uniqueness of the keys generated on Debian making them predictable.

I think this brings us back to one of the earlier topics about Personalization of Private Keys.

Did any of you get affected? Any thoughts? Do write in your experiences in the comments section.

In this article, the Author will talk about what are auctions, what are important issues in online auctions and why Cryptography plays an important role in it. He will also provide pointers for technical details in privacy preserving auctions.

The article is authored by Sujit P Gujar who is a long time CRYPTOcrat (http://www.linkedin.com/pub/5/401/925) and he is currently a research scholar at Indian Institute of Sciences, Bangalore, India.

You can find more information about Sujit on his website here: http://people.csa.iisc.ernet.in/sujit

For easier reading this soon to be published article is split into two parts.

Gnidaer yppah ;) 

12
May

DRM Technologies - CPRM

   Posted by: Abhishek   in DRM

Maintaining the DRM thread here is my primer on CPRM;

In this era of computers, Digital Media (data, audio, video and other digital contents) storage and safety had never been so important be it for the users of personal computer or for other digital consumer devices such as Pen drives, USB disc, Personal Media devices. As for the Personal Media Devices (PMD) such as Personal Media Players (PMP) the requirement is the ability to store and move the legitimate content across systems. And with more popular techniques this move-ability is linked to the media and the content. From the users perspective he needs this unlimited and unrestricted access to his digital media content. However, many a times implementing a perfect scheme which will provide a seamless play-anywhere and play-unlimited capability is infeasible. Besides, while there is an expected legitimate use of this content there are various new ways devised everyday to break these content protection schemes to enable free use of protected content. The economics behind digital content protection/playback is huge and easily falls in the figure of multi-billion dollars every year. The copyright holders and publishers own the large portion of this multi-billion dollar pie and look up to the Crypto/Security enthusiast community to help them countering the problems of piracy. Various standardized and proprietary content protection (Digital Rights Management - DRM) schemes have been proposed on this topic which have been successful a large extent. One of them is “CPRM - Content Protection for Recordable Media”.

CPRM is simply a hardware based technology which controls copying, moving and deletion of digital media on computers and digital players. CPRM imposes restrictions through built in mechanisms in storage media. CPRM was developed by The 4C Entity consisting of IBM, Intel, Matsushita and Toshiba. The 4C Entity, LLC, Licensor of Content Protection for Recordable Media has defined the CPRM specifications. These specifications contain all cryptographic methods to protect digital media or entertainment content when recorded on physical media. The current cryptographic methods presently used are Cryptomeria cipher (C2) algorithm for symmetric encryption. CPRM specification is based on key management for interchangeable media, content encryption and how digital media is being renewed. C2 is a block cipher. The 4C Entity has defined it and has the license. C2 is successor to CSS (Content Scramble System) and mainly designed for CPRM for DRM restricted digital media and devices. The C2 symmetric key algorithm is a 10-round Feistel cipher. It has a key size of 56 bits and a block size of 64 bits.

The 4C Entity provides development or facsimile keys for the product which uses CPRM technology. CPRM is mainly implemented in Secure Digital Card and used to incorporate digital tags into storage media viz. recordable CDs (CD-R, CD-RW) and flash memory cards for MP3 players, etc. CPRM specifications have been mainly defined for DVD drives, portable ATA storage and Secure Digital (SD) memory cards. CPRM requires a table of secret device keys which should be embedded into every licensed device and media key block (MKB) which should be stored on every recordable media. CPRM complaint devices can also generate a media key by performing operations on MKB. In the case of a DVD/CD the MKB is permanently burnt into the control data area hidden within the disc’s lead-in area. Lead-in area is normally near the center of the disc and usually not accessible by users. This will prevent users from deleting or modifying MKB. Generally, disc manufacturers embed a media identifier or media ID into each piece of recordable media, which can not be deleted. Media ID specifies the type of media and it’s manufacturer and also includes a 40-bit serial number that uniquely identifies the disc. This helps to uniquely identify the disc which helps CPRM to bind the data to the media on which it is recorded. Each volume of content is also identified by a secret 64-bit title key that is stored on the disc in encrypted form. This key can only be decrypted by a 56-bit disc specific media unique key that in turn is calculated from the media key and the media ID. The title key which is needed in order to read or write content is thus bound to both content and media. Media ID doesn’t need to be kept secret as it can not be physically altered.

In nutshell, CPRM mainly binds copyrighted materials to the physical media. It allows discs to be recorded and played back on different devices but doesn’t let protected content to be copied to another piece of media. As for how successful CPRM has been could make a good debate, however, it still widely adopted by hardware manufacturers. For now I shall leave you with this much.

- Abhishek Anurag

8
May

Article series on DRM Technologies

   Posted by: Amit   in DRM

DRM is like someone instructing me what I do with my own money!

The DRM debate resumed again at the Embedded System conference and it appears that the arguments this time were quite heated. Imagine Hollywood studio representatives taking on attorneys. For more on that refer to this link.

One of the interesting analogies came from Dean Garfield, executive VP and chief strategy officer for the Motion Picture Association of America. Garfield related the DRM techniques adopted by Hollywood to security barriers faced by bank customers using ATMs. These customers gladly accept the necessity of password to get their own money which is similar to the DVD buyers accepting constraints such as water marks and copy restrictions placed on the media they purchase. He referred to them as business rules and not actually the technology. So it’s the business rules that irritate and anger both consumers and IP attorneys. In response to this comment Fred von Lohmann, senior IP attorney for the Electronic Frontier Association responded “Of course they don’t mind the password at the ATM. What I would mind is a set of restrictions on what I can do with my money after I’ve received it from the bank”. He said that such constraints are the essence of DRM.

Jim Barton, CTO and senior VP of R&D for TiVo talked about closing the gap between what the consumers want and the business rules required by the content creators.

Picking up from this thread, we would like to start an article series on DRM & related technologies. We will start with a primer on CPRM and Abhishek happily has taken up the challenge to do that for us.

19
Apr

How personal are the private keys?

   Posted by: Amit   in Encryption

I recently read about this news and thought this could be a good opening article for CRYPTOcrats. To set the context let me borrow few paragraphs from this news that I read and also provide the link to the original news source.

The news talks about the research put together by professors of computer science at UCLA Henry Samueli School of Engineering and Applied Science. The Authors of this research are associate prof Amit Sahai at UCLA, Brent Waters a UCLA alumnus and Jonathan Katz of the University of Maryland.

The research has identified how Americans have become attractive targets for hackers resulting in billions of dollars in losses for US businesses. To get a perspective on the amount of losses check these staggering figures -

“According to a 2007 FBI analysis, Internet crime costs U.S. businesses some $67 billion annually, including the indirect expense of repairing hacked systems. TJX, the parent company of discount clothing chains T.J. Maxx and Marshalls, revealed that during a recent 18-month period, hackers had stolen 45.6 million credit card numbers and other sensitive customer information. For every two Americans, one private record has been stolen through computer data breaches alone.”

The researchers believe that the problem exists because of how this sensitive data is stored on the servers. Even though this data may be stored on secured servers once the hackers break in to these servers the data stored in there becomes vulnerable to misuse. The researchers have devised a method to change the rules of this game on hackers and even out the playing field. The scheme they have devised is called as Functional Encryption. To elaborate the gravity of the current problem here is the example they have given -

“Imagine current encryption technology as a lock and key - the data is locked, and to allow different people access, many copies of the key need to be made,” he said. “One record might need to be accessed by 10,000 people, so you make 10,000 copies of that key. With millions of documents and thousands of keys per document, you can imagine how very, very complicated it gets. It becomes much too complicated to manage. So even though we’ve had very strong encryption technology now for decades, it’s just not used, or it is used incorrectly.”

This brings me to the point I would like to discuss here. How personal are the private keys we use?

Most of the PKI algorithms use random seed in generating large numbers which form the primitives in generating what we call public and private keys. What is missing in this whole process is personalization of these keys to the user. Yes, there are systems available today which use an additional step such as Digital Certificates or Biometric Authentication (figure print recognition/ voice recognition etc) to bind the keys to the end user, however, they still don’t make the basic key material i.e. the Key pairs personalized to the user. Besides, this additional step has merely moved the vulnerability to a new place i.e the place where this binding of Key pairs to Digital Certificate or Biometric authentication is performed. Now with this, doesn’t it sound more relevant to address the root cause of this problem? How about making the cryptographic key generation algorithms more personalized. This is precisely the point the Sahai & his team are making.

The Functional Encryption system proposed in the research provides mechanism to the system to create a “information template of the user”. The mathematical system they have devised produces encrypted data based on this “template” and hence can be decoded only by the user matching the information in the template. This new mathematical system provides some innovative hardening that personalizes the key not merely based on the users personal attributes like his name is.

This way the servers don’t need complex systems to manage huge set of keys and even the servers themselves can’t decrypt the encrypted data. This intern makes the hacker’s attempt of breaking the servers a lost cause since the information will appear gibberish to them. Also even if the hacker is an insider, he is limited by what access he legitimately has, and since keys are personalized, it becomes much easier to trace who accessed and released the information in the first place.

It would be interesting to know the details of this mathematical system and how it really makes these keys more personalized to the user. While I try to dig that more if you have any views, comments, suggestions, additions, inputs on this topic please feel free to post them here….

UPDATE (10:00 am, 20 April 08) :

I just found a poster about Functional Encryption. Providing the link here

Functional Encryption

6
Apr

Launching CRYPTOcrats

   Posted by: Amit   in Launch

Greetings!

It gives me great pleasure to launch CRYPTOcrats.com today when some of us in India are celebrating the festival of Gudi Padwa. This first day of the New Year per the Maharashtrian Calendar is celebrated by hoisting a “Gudi” - a decorated wooden stick outside the house . And for the curious ones this is how the Gudi looks.

CRYPTOcrats Logo

CRYPTOcrats started as a linkedin group and now we have reached a critical mass. The purpose of this group was to bring together the mix of Cryptography/Security enthusiasts, aficionados and experts. While I was sending out the invites to friends and like minded acquaintances we thought why not have our own website. So CRYPTOcrats.com is this initiative where we would like to create forum for the group to discuss and read about Security/Cryptography.
There was a lot of hard work and sincere effort put in to create this and I hope you will use the forum to the group’s benefit to the fullest. There are a lot of people I would like to thank for their continued support. Few names that must be mentioned here are Mr. Ravi Gogte, Mr. Aniruddha Shrotri, Dr. Shridhar Shukla. They all have been encouraging us in the CRYPTOcrats cause.

A lot of thanks to the CRYPTOcrats founding team Mayuresh Bakshi and Abhishek Anurag.

Besides being a good source of information, a blog site, I am sure there are many other roles CRYPTOcrats.com might play and We would like to hear your suggestions about that.

With this I would like to launch CRYPTOcrats.com. Lets all figure out how we want to use CRYPTOcrats more effectively in the time to come.

Thank you.

Amit Chitale