Cloud computing presents an innovative technique to deliver computing as a set of services that can be consumed and utilized over the Internet. This technology breakthrough opens new doors for cybercriminals. The process of authenticating a new breed of cloud users who connect to cloud resources from anywhere, using any Internet-enabled devices and at any time complicates things more. This paper presents an innovative strong and risk-based authentication system. This is to deal with the rising issue related to unauthorized access of cloud hosted resources as a result of inadequate or weak authentication or even stolen user credentials. The proposed solution makes use of a risk engine which monitors user behavior in order to authenticate users based on specific risk indicators. Furthermore, this paper also makes use of an innovative encryption algorithm that takes chaotic random noise as input to generate encryption algorithms to help encrypt user authentication data at rest, in use and transit. The encrypted authentication data is then stored in multiple storage locations to improve its resiliency to cyber-attacks. This forms a key part of our contribution. The usage of multi-factor authentication systems can be argued to improve the overall system security by monitoring users interacting with a system and modifying defensive strategies to handle malicious behavior in a proactive manner. Our main goal for this architecture is to try and reduce cyber-criminal activities that are normally caused by weak authentication or stolen user credentials. The proposed solution has already been implemented as a proof-of-concept prototype to evaluate its applicability and suitability to achieve its goals. Despite a 7% of reported false positives or negatives, this solution is guaranteed to take strong risk-based multi-factor authentication on the cloud to the next level.