Wikipedia

User:SelimLakhdar/sandbox

Human interaction proof (HIP), also known as CAPTCHA, or reverse Turing test, is a system used to tell human and computer bots apart, semi-automatically.

HIP mainly relies on unresolved AI problems to generate challenges that are easily solvable by humans, while remaining too hard for computer bots. This challenge depends on the fact that some calculations are still too hard to solve for a bot, so theoretically if a bot succeed on the test it could be used for solving AI problems.

Designing such systems requires a trade-off between security and accessibility.

Many other implementations can be found, especially when the accessibility is more important than the security. Designing an accessible HIP is a new major concern.

Many HIPs have been released over the years; this intense activity is due to different attacks that have broken most of them. Machine learning is the most advanced and most used attack.

History and evolution

edit
 
Turing Test

In the 1950s, Alan Turing was the first who was wondering about how to differentiate between human and machine behavior. He was trying to determine if a computer can think.[1] He invented the Turing Test which consists in trying to differentiate between human and robot by a challenge–response test. This first consideration was not meant to be automatized. In fact, the test was administrated and verified by a human.

With the growth of Internet users and the apparition of the first web services, the necessity of automatically distinguish between normal human actions, and automated actions through bots was necessary.[2]

The first attempt lights up to different attacks to break the system which light up new ways to build a strong HIP. This revealed that building a HIP is not an easy task.[3] The generated challenge has to be as easy as possible for humans to pass, and hard as possible for computers to solve it.[4]

 
Text based CPATCHA

Over the years, the most common representation of a HIP is visually distorted images of a string of letters and numbers that can be understood by human but not by bots.[5]

This approach was criticized due to its negligence for disabled persons. Other alternatives were introduced like, the audio based CAPTCHA, the puzzle based CAPTCHA.[6][7]

One of the main idea behind building new HIPs systems is using unsolved AI problems for generating and verifying the challenge. Indeed, using problems that cannot be solved effectively/efficiently by any feasible machine could be a great progress in that field if hackers could break it. This idea was also encouraged by the popularizing of the 1024 integer factoring problem for cryptographic protocols.[8][9][10]

Usage and utility

edit

HIPs systems are used to secure services from automated attacks. Generally, they are deployed in the front-end layer, where the interaction of the user is checked to perform a request to the server. This point shows that HIPs are used as a preventive method to control access to the back-end layer.

Some notorious usages are :[11][12]

  • Preventing comment spam.
  • Protecting website registration.
  • Protecting email addresses from crawlers.
  • Preventing dictionary attacks (Brute-force attack).
  • Traking online bots: interactions of social networks.
  • Search Engine Bots.

CAPTCHAs are also used to mitigate the risk of password eavesdropping attack to discourage password phishing from some malwares. Specifically, in the TLS protocol to counter the MITM attack.[13]

Usability/accessibility

edit

Designing a HIP is a complex problem. In fact, it's a trade-off between security and accessibility.[14][15][16] Finding the right equilibrium between accessibility and strength against attacks is difficult. The HIP has to be difficult to solve for a computer, while remaining easy for a human.[17][18] An automated script should not be successful more than 1 in 10,000 tries or have success rate of 0.1%, and that a human should be successful at least 90% of the time.[19]

Samaras et al. leaded a study in the human recognition field to understand how the human brain analyses and understands an image.[20] Various researchers attempted to explain the functioning of the human mind in terms of more basic processes, such as speed of processing, controlled attention and working memory capacity to build more resistant HIPs.[21]

The CAPTCHA is the most used system despite it doesn't provide an acceptable trade-off between security and accessibility.[22][23] According to a survey led in the US, 37 millions users are blind and that's an important concern about text-based CAPTCHA. Indeed, CAPTCHA is the greatest security-related problem for users with disabilities, especially for blind users.[24] Even the new audio-based CAPTCHA are still inaccessible for certain users.[25][26][27][28]

Security

edit

The security aspect in a HIP system is very important. It's the key to prevent computer bots from bypassing the system, while remaining timely resolvable for humans. The properties that make a problem hard to solve, and resistant to bot attacks, are discussed by Bergadano et al.[29] A CAPTCHA is considered robust to attacks if the success rate of attacks is less than 0.01%. However, it is also desired that the CAPTCHA be usable, i.e. the human success rate should be at least 90%.[30] Other studies revised the value of robustness of CAPTCHA to bot attacks from 0.01% to 1%, citing it as more meaningful.[31]

AI usage

edit

Through the time, using AI to build such systems was explored. Using hard unsolved AI problems to generate challenges was also a way to advance in that field.[32][33] But, finding a suitable AI problem that can automate the generation of the challenge is not an easy task.[34][35] Text recognition is a field of interest in AI, well-oriented (aligned) text is already recognized by computer programs, researchers worked on the distorted text, or more commonly the handwriting text recognition. The difficulty of recognizing distorted text came from the segmentation problem, the challenge for AI is to break the interlacing between words,[36][37] but this seems to not be relevant anymore.[38][39]

Segmentation resistance

edit

The most used technique to bypass a text-based CAPTCHA is segmentation.[40] The more effects for designing a strong HIP are combined, more the HIP is secured.[41]. Adding noise, lines, random arcs, rotation, scaling and distortion are common used techniques[42][43]

Challenge generation

edit

The capability of generating many instances of the problem is also an aspect of interest for scalability.[44] Another concern is trying to avoid parallel attacks (Brute Force[disambiguation needed]).[45][46]

Public Sources

edit

Beyond the preceding rules to design a strong HIP system, publishing the source code seems to be the most effective way to improve the system against attacks. CAPTCHAs systems which rely on private databases or algorithms to generate their challenges are prohibited. This rise a risk of an adversary generating all possible tests and using a hash function to look up the answer in a pre-computed database or trying to do reverse engineering.[47][48]

CAPTCHAs

edit

First implementation of CAPTCHA (/kæp.tʃə/, an acronym for "completely automated public Turing test to tell computers and humans apart") was trying to achieve some goals like an easy generation of multiple instance of the challenge and an easy usage.[49] The most wide used HIP scheme is the CAPTCHA, which was introduced in 2000.[50] It relies on the gap between human and robot for analyzing visual information. It uses text/image deformation and distortion to build the challenge.[51]

Since then, HIPs evolved and many other implementations appeared. Many fields were studied, like gender recognition, facial expression understanding, body parts finding, nudity deciding, naive drawing understanding, handwriting understanding, speech recognition, filling in words.[52]

We can classify CAPTCHAs in different categories : [53]

  • Visual CAPTCHA

CAPTCHA that relies on the generation of a visual challenge. They are not adapted for disabled persons.

  • Text-Based CAPTCHA

It relies on text deformation, distortion, adding noise like arcs, to generate the challenge. This scheme is the most used one because it uses alphanumeric symbols which are directly accessible with the keyboard. Some notorious implementation are Pessimal Print, BaffleText, ScatterType, GIMPY, EZ-GIMPY.

  • Image-Based CAPTCHA

It relies on image recognition. Indeed, it based on the difficulty for bots to understand images. This is usually performed through recognizing some aspects of an image, or grouping same images. Implementation of such CAPTCHAs are Bongo, ESP-Pix, Asirra, Imagination, and ARTiFACIAL.

  • Moving Objects CAPTCHA

This kind of CAPTCHAs is recent. It uses animation to display CAPTCHA, where users are asked to type what they have seen or perceived. The generation of challenge remain hard to implement.

  • Non-Visual CAPTCHA

Those CAPTCHAs were introduced for disabled users. The challenge relies on sound recognition or semantic understanding.

  • Semantic CAPTCHA

It relies on the gap in sentence understanding between humans and bots. Example of generated challenge can be a simple question like "What's the color of the sky ?". Those CAPTCHAs are vulnerable to attack using a computational knowledge engine, such as Wolfram Al-pha or even a search engine.

  • Audio CAPTCHA

Use sound deformation of a sentence. Adding noise.

  • Others approaches

Other approaches can be done by combining those different technique to come with a hybrid one. One example of this type is HIPUU CAPTCHA which uses image and audio-based CAPTCHA.[54]

Attacks on HIPs

edit

The security is a continuous game between hackers/researchers and security engineering.[55][56] We can quote the PWNtcha project " PWNtcha stands for "Pretend We’re Not a Turing Computer but a Human Antagonist", as well as PWN capTCHAs. This project’s goal is to demonstrate the inefficiency of many captcha implementations. "[57]

Work was also done on automatically recognize HIPs scheme to build a generic way to broke CAPTCHAs.[58][59]

OCR

edit

Optical character recognition is used to recognize/identify a content of a document. It relies on multiple techniques, like binarization to removes noise pixels.[60] After pixel cleaning, edge detection is more effective. Another important technique is the segmentation to separate and detect letters.[61] If those techniques aren't efficient to break the HIP, Using the segmentation result with an SVM for character recognition can work.[62]

Machine learning

edit

Machine learning is a widely used technique to break CAPTCHA. It consists in designing an automated solver. Most HIPs are pure recognition tasks that can easily be broken using machine learning.[63]

The use of machine learning based attacks is a concern in building HIPs.[64] In August 2014, Bursztein et al. presented the first generic CAPTCHA-solving algorithm based on reinforcement learning and demonstrated its efficiency against many popular CAPTCHA schemas. They concluded that text-distortion-based CAPTCHAs schemes should be considered insecure moving forward.[65]

Stealing cycles (redirection)

edit

One of possible attacks on a CAPTCHA system is to redirect the challenge to another user to solve it. This technique was firstly used on pornographic websites.[66][67]

References

edit
  1. ^ Ahn, Blum & Langford 2004, p. 1
  2. ^ Kumar et al., p. 2
  3. ^ Ahn et al. 2003, p. 2
  4. ^ Sauer et al. 2010, p. 1
  5. ^ Sauer et al. 2010, p. 3
  6. ^ Moradi et al. 2015, p. 1
  7. ^ Samaras et al. 2013, p. 1
  8. ^ Ahn et al. 2003, p. 3
  9. ^ Ahn et al. 2004, p. 1
  10. ^ Ahn et al. 2004, p. 4
  11. ^ Moradi et al. 2015, p. 3
  12. ^ Ahn et al. 2003, p. 1
  13. ^ * Enhancing the Security of On-line Transactions with CAPTCHA Keyboard
  14. ^ Sauer et al. 2010, p. 3-4
  15. ^ Sauer G et al. 2010, p. 4
  16. ^ Sauer G et al. 2010, p. 8
  17. ^ Moradi et al. 2015, p. 2
  18. ^ XXX 2020, p. 2
  19. ^ Sauer G et al. 2010, p. 5
  20. ^ Samaras et al. 2013
  21. ^ Samaras et al. 2013
  22. ^ Samaras et al. 2013
  23. ^ Sauer et al. 2010, p. 2
  24. ^ Sauer et al. 2010, p. 1
  25. ^ Sauer G et al. 2010, p. 1
  26. ^ Sauer G et al. 2010, p. 6
  27. ^ Sauer G et al. 2010, p. 3
  28. ^ "Inaccessibility of CAPTCHA". www.w3.org. Retrieved 9 January 2019.
  29. ^ Bergadano et al. 2010, p. 1–26
  30. ^ Chellapilla K. et al. 2005, p. 1–26
  31. ^ Jalwana et al. 2014, p. 1
  32. ^ Ahn et al. 2003, p. 3
  33. ^ Ahn et al. 2003, p. 15
  34. ^ Ahn et al. 2003, p. 6
  35. ^ Ahn et al. 2003, p. 9
  36. ^ Ahn et al. 2003, p. 9
  37. ^ Zhu et al., p. 2
  38. ^ Sauer G et al. 2010, p. 5
  39. ^ Nishigaki et al. 2014, p. 1
  40. ^ Sauer et al. 2010
  41. ^ Sauer et al. 2010, p. 13
  42. ^ Sauer et al. 2010, p. 12
  43. ^ Jalwana et al. 2014, p. 8
  44. ^ Zhu et al., p. 2
  45. ^ Ahn et al. 2004, p. 4
  46. ^ Chellapilla et al. 2005, p. 2
  47. ^ Zhu et al., p. 1
  48. ^ Sauer G et al. 2010, p. 5
  49. ^ Ahn et al. 2004, p. 2
  50. ^ Ahn et al. 2003, p. 4
  51. ^ Moradi et al. 2015, p. 2
  52. ^ Ahn et al. 2004, p. 4
  53. ^ Moradi et al. 2015
  54. ^ Sauer G et al. 2010, p. 1
  55. ^ Jalwana et al. 2014, p. 9
  56. ^ XXX 2020, p. 1
  57. ^ "PWNtcha - captcha decoder".
  58. ^ XXX 2020, p. 3
  59. ^ Jalwana et al. 2014
  60. ^ Jalwana et al. 2014, p. 4
  61. ^ Jalwana et al. 2014, p. 9
  62. ^ Jalwana et al. 2014, p. 9
  63. ^ Simard & Patrice Y. 2019, p. 1
  64. ^ Zhu et al.
  65. ^ Bursztein, Elie; Aigrain, Johnathan; Mosciki, Angelika; Michell, John C. (August 2014). The End is Nigh: Generic Solving of Text-based CAPTCHAs. WoOT 2014: Usenix Workshop on Offensive Security.
  66. ^ *"Porn rewards users to get past anti-spam Captchas. Available at: http://yro.slashdot.org/story/04/01/28/ 1344207/porn-rewards-users-to-get-past-anti-spam- captchas [accessed March 2013]
  67. ^ *How lazy Cryptographers do AI - Stealing Cycles From Humans

Bibliography

edit
Retrieved from "https://en.wikipedia.org/w/index.php?title=User:SelimLakhdar/sandbox&oldid=1092057244"