sujeet / yess-key Goto Github PK
View Code? Open in Web Editor NEWAn efficient implementation of S/KEY authentication in JavaScript. (CS255 Project)
An efficient implementation of S/KEY authentication in JavaScript. (CS255 Project)
Yess-Key ======== An efficient implementation of S/KEY authentication in JavaScript. 1. Briefly describe your implementation and its design choices. e.g. What algorithm did you use? How did you structure your code? Did you do something interesting in "save" and "load"? Justify the space/time used by your implementation. --> NOTE: Our impletemnation works irrespective of whether the number of iterations is power of two or not. ALGORITHM: The algorithm was guided by the hint given in the problem sheet. We started off with the pebble structure mentioned in the hint. "log(n) space" was what guided the design of the algorithm. We tried to answer the question "Now that m number of pebbles have been discarded, how to use the space that was used up by them?" Example: initial pebbles : [1 129 193 225 241 249 253 255 256 current pebbles : [1 129 193 225 241 249 want to find : hash at 249 We have it at the top of the stack, get it, pop. current pebbles : [1 129 193 225 241 want to find : hash at 248 We have 4 places freed up in our storage space, can we a create structure of less than 4 pebbles similar to [253 255 256], but ending with 248 on the top of the stack? yes! consider : [1 129 193 225 241 245 247 248 (it is like fitting the structure so far popped into the space just below) SAVE AND LOAD: As the state we were keeping wasn't really something very complex, we just decided to store the JSON representation of the state as such. SPACE: As we saw in the description of the algorithm, the log(n) bound on space is obvious. TIME: Experimental verification: We slightly modified the hash function so that we could keep track of how many times it was invoked. We modified the "Test the entire chain" part of the test to print the total hash count divided by number of iterations to get average number of hashes calculated per `advance` invocation. We verified that it grew linearly with N where num_iter = 2^N Proof outline: We observe that once we store a pebble in the storage, it's hash is never calculated again. Consider the hash chain numbered in a slightly different format... [256 128 64 32 16 8 4 2 1 ... (Initial pebble structure) --> How many times are hashes of the above calculated? Only once. How about 17, 19? Once for calculating initial pebble structure. Not calculated until 16 was popped. After 16 was popped, hashes from 31 to 17 will be recalculated. [256 128 64 32 24 20 18 17 --> Thus 17 was calculated twice. See that 19 isn't still there in the storage. It will be calculated after 17 and 18 are popped. At that time, it will be stored. --> Thus 19 was calculated thrice. We observe that the hash at N will be calculated exactly M times where M is the number of 1s in its binary representation. We know M is bounded above by ceil (log (N)) 2. If you were designing an authentication mechanism for a hot new startup that wants to protect its users, how would you decide whether/where to use S/KEY? --> For S/KEY, seed needs to be stored on the client which might turn out to be a hassle for web-based apps. On the other hand, it will be a good idea when the app is a native app (android/iOS/desktop). Another thing that might work against S/KEY is if we plan to support a large number of devices. (Each device would have its own chain). To sum it up, if the startup isn't a website, but more like a native app, we would go with S/KEY. If it is a website and we want our users to be able to use the site from any computer, S/KEY isn't the thing we would go ahead with. In the later case where we have a website, but main focus is native apps, we could provide all the non critical functions via website, but for crucial things like trasactions, account management and password change etc, we would require a dual-authentication, (which, would be on the native apps). This, to us, seems to be a reasonable middle ground. 3. How long did you spend on this project? --> Less than 2 hours for actual coding. Way more time agonizing over "Why am I not able to think of any amortized constant time implementation"
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.