Methods, systems and computer program products for providing video-based authentication are provided. Aspects include receiving a master video comprising a recording of a first plurality of objects. Aspects also include identifying each of the first plurality of objects using image recognition techniques. Aspects also include receiving a user selection of a plurality of authentication objects, where the plurality of authentication objects are a subset of the first plurality of objects. Aspects also include receiving a user authentication request comprising an authentication video. The authentication video is a recording of a second plurality of objects. Aspects also include identifying each of the second plurality of objects using image recognition techniques. Aspects also include authenticating a user associated with the user authentication request in response to determining that identifications of a subset of objects of the second plurality of objects match identifications of the plurality of authentication objects.